LeetCode: 31. Next Permutation

Summary

Find the next permutation.

Rules:

"Next" means the next lexicographically greater permutation of the integer sequence.
If the next permutation does not exist (already at the lexicographically maximum order), return the minimum order.
The replacement must be in place and use only constant extra memory.

Example:

For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. The next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] has no lexicographically larger rearrangement.

Approach

How to find the next permutation?

Find the pivot point from the tail where nums[i] > nums[i-1]. From this pivot to the end, the sequence is in descending order (the maximum arrangement of that suffix). Next, find the first value greater than nums[pivot] from the tail and swap it with nums[pivot]. After that, reverse the suffix after the pivot to make it the minimum arrangement.

Function

Initialization:

pivot = -1

Find pivot: For i from len(nums)-1 down to 1: if nums[i-1] < nums[i]: pivot = i-1 break

Swap: If pivot > -1 (pivot found): find the first value greater than nums[pivot] from the tail, then swap them.

Reverse: Reverse the order after pivot (pivot+1 to the end).

Complexity

Time Complexity: O(N), where N is the size of nums, because we scan from the back and reverse at most one suffix. Space Complexity: O(1).