By Long Luo

This article is the solution Two Pointers Solution with Detailed Explanation of Problem 31. Next Permutation.

Intuition

• How to make a number larger?

Pick a larger number from the lower digit and swap it with the higher digit smaller number.

• How to find the permutation which is just larger than the given number?

The increase should be as small as possible.

Two Pointers

Take a example, \([3,2,1]\) which is decreasing order, there is no next permutation, it is already stable and cannot get larger.

Like \([1,5,2,4,3,2]\), how can it be just larger than the given number?

1. Scanning from right to left, find the first number which is smaller than the right digit, and swap it to the lower digit;
   • For example, \(1 5 (2) 4 3 2\), the \(2\) in the middle is the found one.
2. Scanning from right to left, searching for the first number which is larger than it, and swap them.
   • For example, \(1 5 (2) 4 (3) 2\), after swap: \(1 5 (3) 4 (2) 2\).

However, it’s not over yet!

The magnitude of the increase can be made smaller, the \(3rd\) digit from right has become slightly larger, and the last three can be made smaller.

The last three digits are definitely decreasing, and they are flipped to become \([1,5,3,2,2,4]\), which is what is required.

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
43
44
45
46
47
48
49
50

// Two Pointers time: O(n) space: O(1)
public static void nextPermutation_tp(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return;
    }

    int len = nums.length;
    int left = len - 2;
    /**
     * from right to left, search for the first one which is smaller than the right digit.
     */
    while (left >= 0 && nums[left] >= nums[left + 1]) {
        left--;
    }

    /**
     *  If the one exists, search a one which is larger than it from right to left.
     */
    if (left >= 0) {
        int right = nums.length - 1;
        while (right >= 0 && nums[left] >= nums[right]) {
            right--;
        }
        /**
         * swap them.
         */
        swap(nums, left, right);
    }

    /**
     *  flip the right to make the number smaller.
     */
    reverse(nums, left + 1);
}

public static void swap(int[] nums, int a, int b) {
    int temp = nums[a];
    nums[a] = nums[b];
    nums[b] = temp;
}

public static void reverse(int[] nums, int low) {
    int left = low;
    int right = nums.length - 1;
    while (left < right) {
        swap(nums, left, right);
        left++;
        right--;
    }
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗