Leetcode 31 Solution

Leetcode Question Link

https://leetcode.com/problems/next-permutation

Thinking Process

The most straightforward solution would be listing all the permutations, and we can find out the next permutation to the asked one. However, this is very slow. Not desirable.

In order to make it fast, we need to find out patterns or properties of the next permutation. Let’s first list all the permutations of 123 are:

• 123
• 132
• 213
• 231
• 312
• 321

It’s very easy to find that the order of these numbers are based on its value. That being said, an important observation or property here is the next permutation means the next bigger number (if there is any).

To find the next bigger number, we’ll need to find the pivot point first.

• 132 -> 213
• 1243 -> 1324
• 1234765 -> 1235467

The above examples suggest that you can find the pivot point by searching the first non-increasing element from the end. For example, for 132, the pivot point is 1. For 1243, the pivot point is 2. For 1234765, the pivot point is 4.

Next, you’ll need to grab the smallest number after the pivot point that is greater than the number at the pivot point. And then swap it with the pivot point number.

Finally, you just sort the numbers after the pivot point.

Time & Space Complexity

Assuming N is the size of array:

• Time complexity: O(N * lg N))
• Space complexity: O(1)

Solution

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() == 0)
            return;

        int i = nums.size() - 1;

        for (; i > 0; i--)
        {
            if (nums[i] > nums[i - 1])
                break;
        }

        if (i == 0)
        {
            sort(nums.begin(), nums.end());
            return;
        }

        int j = nums.size() - 1;
        for (; j >= i; j--)
        {
            if (nums[j] > nums[i - 1])
                break;
        }

        swap(nums[i - 1], nums[j]);
        sort(nums.begin() + i, nums.end());
    }
};

Learning

• Derive properties first if you can’t solve the problem immediately.