[LeetCode] 31. Next Permutation

Posted on | In

Problem

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

Explanation

  1. First, we can list out all the permuatations. For example, if input array is [1, 2, 3]. Then we have:

    1
    2
    3
    4
    5
    6
    7
    8
     [
 [1,2,3],
 [1,3,2],
 [2,1,3],
 [2,3,1],
 [3,1,2],
 [3,2,1]
 ]

  2. If the input array elements are in decreasing order, we can just return the reverse array.

  3. If the input array elements are not in decreasing order, for example, the input array is [1, 2, 7, 4, 3, 1], then its next permutation is [1, 3, 1, 2, 4, 7].

  4. We can look from the end elment to the beginning of the input array, we find out elements are increasing until we hit the $2$. Then, we still look from the end element to the beginning, we find out $3$ is larger than $2$. Then, we swap these two elements. Finally, we reverse all the elements starts from the index that is equal to the original input $2$’s index plus one.

    1
    2
    3
     [1, 2, 7, 4, 3, 1] //swap 2 and 3 
 [1, 3, 7, 4, 2, 1] //reverse all elements after 3
 [1, 3, 1, 2, 4, 7] //result

Solution

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    
    void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    
    public void nextPermutation(int[] nums) {
        if (nums.length < 2 || nums == null) return;
        int n = nums.length;
        int a = 0, b = 0;
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                a = i;
                break;
            }
        }
        
        for (int j = n-1; j > a; j--) {
            if (nums[j] > nums[a]) {
                b = j;
                break;
            }
        }
        if (a == 0 && b == 0) { //edge case, input array is decrease order
            reverse(nums, a, n-1);
            return;
        }
        swap(nums, a, b);
        reverse(nums, a+1, n-1);
    }
}