Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

[code lang="java"]
class Solution {
    public void nextPermutation(int[] nums) {
        
    }
}
[code]

Idea – 1

Idea is to increase the sequence as little as possible. We index from right to left (lsb to msb). Smallest increase is achieved by swapping two elements a_i and a_j such that i > j and a_i < a_j and a_j is the smallest such number in [i-1..0]. After swapping we decrease [i-1..0] as much as possible. For example, in [1, 2, 4, 3], from right to left since [4, 3] is non-decreasing, we cannot find a_i and a_j that meet the requirements. However, 2 is the best candidate for a_i since anything left of 2 will make the increase bigger. The smallest number bigger than 2 and right of 2 is 3, so we swap 2 and 3 and get [1, 3, 4, 2]. Now we decrease right of 3 as much as possible by just reversing it, since right of 3 is guaranteed to be nondecreasing (right to left). Finally we have the next higher permutation [1, 3, 2, 4]. Time complexity is O(n) and space complexity is O(1). 
[code lang="java"]
class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while(i >= 0)
        {
            if(nums[i] < nums[i+1])
            {
                break;
            }
            
            --i;
        }
        
        if(i < 0) // highest permutation, cannot increase
        {
            reverse(nums, 0, n-1);
            return;
        }
        
        int j = n-1;
        while(j > i)
        {
            if(nums[j] > nums[i])
            {
                break;
            }
            
            --j;
        }
        
        swap(nums, i, j);
        reverse(nums, i+1, n-1);
    }
    
    private void reverse(int[] A, int begin, int end)
    {
        while(begin < end)
        {
            swap(A, begin++, end--);
        }
    }
    
    private void swap(int[] A, int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
[code]

Runtime: 1 ms, faster than 99.58% of Java online submissions for Next Permutation.Memory Usage: 37.2 MB, less than 94.57% of Java online submissions for Next Permutation.

Leave a comment