Solution for O(n) time and O(1) space and explanation


  • 0
    K

    Hey guys!

    First let's consider the case when all the digits are different:

    1. Let's note that to find the next permutation we only need to change a few last elements. Why? Because If we have {1, 2, 3, 4, 5, 6} the next permutation will be {1, 2, 3, 4, 6, 5}
    2. How do we know how many elements need to be changed? To answer this, let's consider what will be the last permutation. This must be a permutation that is ordered in descending order. Indeed, for a permutation {6, 5, 4, 3, 2, 1}, nothing can be changed to increase lexicographical order. So based on that, we need to change all elements that form descending sequence in the end of the permutation.
    3. Okay, so how exactly to change the elements? Let's assume we found the descending sequence in the tail of the permutation and a first element out of descending order. For {4, 2, 3, 6, 5, 1} the descending sequence will be {6, 5, 4} and the first element out of order will be 3. Now, we can forget about all the beginning elements of the permutation as they don't need to be changed. So let's consider {3, 6, 5, 1}.
      3.1) So, what will be the first element in the next permutation? To keep the order the first digit should be the minimum of the remaining digits that is higher then the first digit. How to find it? Okay, let's remember that the rest of the sequence is ordered in descending way. So if we reverse it and use a binary search, we could easily find the nearest higher element. So, we start with {3, 6, 5, 1}, reverse the tail, {3, 1, 5, 6}, use binary search on {1, 5, 6} to find '3'. It will not be found (all the elements are different, remember?), but we will find the nearest element after '3', which is '5'. So the first element in the next permutation will be '5'.
      3.2) What happens with the rest of the elements? To maintain the lexicographical order, we need to maintain them in ascending order. Because we already reversed the tail of the permutation, the elements are already in the ascending order. So nothing to do here.
      3.3) Okay, so now we need to pick '5' from the tail and sort the remaining elements {3, 1, 5, 6}. But we can avoid sorting if we notice that placing '3' in the position where there was '5' does NOT change the order of the tail. This follows from the method how we chose '5'. We chose minimal number higher then '3', so if we put '3' in the place where there was '5', the ascending order of the tail wouldn't change. Let's assume that putting '3' in the place of '5' will break the ascending order of the tail, but it means that there exists the number lower then '5' that is higher then '3', which contradicts our selection criteria. So we just need to swap '3' and '5'
    4. If the entire array is a descending sequence, this is the last permutation and we need to return the first permutation. To do that it's enough just to reverse the array and we will automatically get ascending-sorted permutation which is the first permutation on lexicographical order by definition.

    In short:

    1. Scan from the end of array for an element n[i] < n[i + 1], once found, store the position of i to pos
    2. if no such a position found, reverse an array and return
    3. reverse the elements from pos+1 to the end of array (inclusive)
    4. Using binary search find the position nearest element higher then n[pos], store the position to nearestPos
    5. Swap n[pos] and n[nearestPos]

    Time complexity analysis: sweep takes O(n), reverse takes O(n), binary search takes O(log(n)), swap is O(1), so the total complexity is O(n)
    Space complexity analysis: we don't use any intermediate arrays or other structures depending on the size of an array, so it's O(1)

    Now let's consider what happens with the short algorithm if we have repeating elements in the permutation:

    1. The inequality becomes partial inequality n[i] < n[i + 1] --> n[i] <= n[i + 1]
    2. No changes
    3. No changes
    4. It's more complex. If previously we could NOT find the head element value in the tail, now we can. This is the problem because swapping the head element with the same element no longer produces next permutation: it produces exactly the same permutation. Now, what to do if we have {1, 3, 1, 1}? We reverse the tail {1, 1, 1, 3}, binary search gives us nearestPos = 2 (or 1). So we need to scan to the right to find the next element higher then '1'. And what is no such element found? Unfortunately, there is nothing we can do with such a tail, so we need to decrement pos. and repeat the binary search and then scan right. If we follow such a pattern, we must find a solution, otherwise the first consition would hold.
    5. No changes

    Time complexity analysis: for step(4) we clearly have n^2log(n) which can be improved to n(log(n))^2 if we use one-sided binary search to scan elements right and this would be the dominating component of time complexity.
    Space complexity is unchanged and is still O(1).

    And here comes the program:

    public class NextPermutation {
    
        public void nextPermutation(int[] nums) {
            if (nums.length <= 1) {
                return;
            }
            // scannong  right-to left find the first number lower then the previous
            int curNum = nums[nums.length - 1];
            int pos = -1;
            for (int i = nums.length - 2; i >= 0; i--) {
                if (nums[i] >= curNum) {
                    curNum = nums[i];
                } else {
                    pos = i;
                    break;
                }
            }
            boolean finished = false;
            while (!finished) {
                // if no such number exists, this is the last permutation, just reverse the array
                if (pos == -1) {
                    reverse(nums, 0, nums.length - 1);
                    return;
                }
                // otherwise it means that the number at poisition pos could be incremented
                // and the reminder is sorted ascendingly
                reverse(nums, pos + 1, nums.length - 1);
                int nextNum = nums[pos];
                int nearestPos = Arrays.binarySearch(nums, pos + 1, nums.length - 1, nextNum);
                if (nearestPos < 0) {
                    nearestPos = -nearestPos - 1;
                    nextNum = nums[nearestPos];
                }
                // TODO: could be improved to use one-sided binary search to reduce complexity from O(n) to O(lon(n))
                while ((nums[pos] == nums[nearestPos]) && (nearestPos < nums.length)) {
                    nearestPos++;
                    nextNum = nums[nearestPos];
                }
                if (nearestPos < nums.length) {
                    finished = true;
                    nums[nearestPos] = nums[pos];
                    nums[pos] = nextNum;
                } else {
                    pos--;
                }
            }
    
        }
    
        private static void reverse(int[] nums, int i1, int i2) {
            if (i1 > i2) {
                return;
            }
            if (i2 - i1 == 0) {
                return;
            }
            int len = (i2 - i1) / 2;
            for (int i = 0; i <= len; i++) {
                int temp = nums[i1 + i];
                nums[i1 + i] = nums[i2 - i];
                nums[i2 - i] = temp;
            }
        }
    
        public static void main(String... args) {
            NextPermutation np = new NextPermutation();
            int[] a1 = new int[]{1, 5, 1};
            np.nextPermutation(a1);
            System.out.println(Arrays.toString(a1));
            int[] a2 = new int[]{2, 1, 2, 2, 2, 2, 2, 2, 1};
            np.nextPermutation(a2);
            System.out.println(Arrays.toString(a2));
            for (int i = 0; i < 10; i++) {
                int[] arr = getRandomPermutation();
                System.out.print("Input = " + Arrays.toString(arr));
                np.nextPermutation(arr);
                System.out.println("; Output = " + Arrays.toString(arr));
            }
        }
    
        private static final Random random = new Random();
    
        private static int[] getRandomPermutation() {
            int[] res = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
            for (int i = 0; i < 10; i++) {
                int pos1 = random.nextInt(10);
                int pos2 = random.nextInt(10);
                int temp = res[pos1];
                res[pos1] = res[pos2];
                res[pos2] = temp;
            }
            return res;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.