# Leetcode 31 Solution

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.