Problem description:

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,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Solution:

index: 0,1,2,3,4,5
value: 2,3,6,5,4,1

1. from right to left, find the first number which not increase in a ascending order. In this case which is 3.
2. here we can have two situations:

  1. We cannot find the number, all the numbers increasing in a ascending order. This means this permutation is the last permutation, we need to rotate back to the first permutation. So we reverse the whole array, for example, 6,5,4,3,2,1 we turn it to 1,2,3,4,5,6.

  2. We can find the number, then the next step, we will start from right most to leftward, try to find the first number which is larger than 3, in this case it is 4.
    Then we swap 3 and 4, the list turn to 2,4,6,5,3,1.
    Last, we reverse numbers on the right of 4, we finally get 2,4,1,3,5,6.

Time complexity: O(3*n)=O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i, j = len(nums)-1, len(nums)-1
        while i > 0 and nums[i-1] >= nums[i]:
            i -= 1
        if i == 0:
            nums.reverse()
            return
        # Note that in previous while loop, we would stop when nums[i-1] >= nums[i]
        # But we want the first descending element, so we need to take nums[i-1] in the following while loop
        
        while nums[j] <= nums[i-1]:
            j -= 1
        
        nums[j], nums[i-1] = nums[i-1], nums[j]
        l, r = i, len(nums)-1
        while l < r:
            nums[l], nums[r] = nums[r], nums[l]
            l += 1
            r -= 1
        return
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = -1; //for checking whether the array is in descending order
    	for (int i = nums.size() - 2; i >= 0; i--) {
    		if (nums[i] < nums[i + 1]) { //From right to left, find 1st number that is not ascending order
    			k = i;
    			break;
    		}
    	} 
    	if (k == -1) { 
            //can not find the number, this means the array is already the largest type, 
            //so reverse it would have the smallest
    	    reverse(nums.begin(), nums.end());
    	    return;
    	}
    	int l = -1; //From right to left, trying to find 1st number that is greater than nums[k]
    	for (int i = nums.size() - 1; i > k; i--) {
    		if (nums[i] > nums[k]) {
    			l = i;
    			break;
    		} 
    	} 
    	swap(nums[k], nums[l]); 
    	reverse(nums.begin() + k + 1, nums.end()); 
    }
};

Another solution:

Just for info: There’s a library function that does the job, even going from totally reverse sorted to sorted:

1
2
3
void nextPermutation(vector<int>& nums) {
    next_permutation(begin(nums), end(nums));
}

Another Solution

Using library functions for all building blocks of the algorithm. Very nice how they all play together, notice the total lack of +1/-1, it all fits exactly.

1
2
3
4
5
6
void nextPermutation(vector<int>& nums) {
    auto i = is_sorted_until(nums.rbegin(), nums.rend());
    if (i != nums.rend())
        swap(*i, *upper_bound(nums.rbegin(), i, *i));
    reverse(nums.rbegin(), i);
}

Second Time:

The last reverse is because, we need to reverse the order after we swap a smaller element to the back.
For example:

1
2
3
4
5
6
7
8
9
[1,3,2], left= 0, right= 2

after swap
[2,3,1]

we can see that the next permutation should be [2,1,3], which should start with the nums[right] we just swap to the back

Therefore, we need to reverse the order so it could be in the front and make a
[2,1,3]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        /*
        1. find a k such that nums[k]< nums[k+1]
        2. if the k does not exist, reverse the entire array
        3. if exist, find a number right such that nums[k]< nums[right]
        4. reverse the rest of the array, so it can be next greater one
        */
        int left= 0, right= 0;
        for(left= nums.size()-2; left>= 0; left--){
            if(nums[left]< nums[left+1])
                break;
        }
        if(left< 0)
            reverse(nums.begin(), nums.end());
        else{
            for(right= nums.size()-1; right> left; right--){
                if(nums[right] > nums[left])
                    break;
            }
            swap(nums[left], nums[right]);
            reverse(nums.begin()+left+1, nums.end());
        }
    }
};