Back to solutions

Next Permutation

MediumArrays

Rearrange to the next lexicographically greater permutation in place.

Open problem
Constraints
  • 1 <= n <= 100
  • 0 <= nums[i] <= 100

Find pivot, swap, reverse

Time O(n)Space O(1)

Scan from the right for the first index i where nums[i] < nums[i+1]; this is the pivot that can be increased. Find the rightmost element greater than nums[i], swap them, then reverse the suffix after i so it becomes the smallest possible tail. If no pivot exists the array is descending, so reversing the whole thing yields the smallest permutation.

Key terms
lexicographic order:
Dictionary-like ordering of sequences, comparing element by element.
pivot:
The rightmost position that can be increased to get a larger permutation.
void nextPermutation(vector<int>& nums) {
    int n = nums.size(), i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;
    if (i >= 0) {
        int j = n - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin() + i + 1, nums.end());
}
Step by step
  1. From the right, find the first i with nums[i] < nums[i+1]. If none, reverse all and return.
  2. From the right, find the first j with nums[j] > nums[i].
  3. Swap nums[i] and nums[j].
  4. Reverse the suffix from i+1 to the end to make it ascending (smallest).