Next Permutation

medium array two pointers

Problem

Rearrange numbers into the lexicographically next greater permutation in place. If no such permutation exists (the array is in descending order), rearrange it as the lowest possible order (ascending).

Inputnums = [1, 2, 3]

Output[1, 3, 2]

nums (comma-separated)

def next_permutation(nums):
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i + 1:] = reversed(nums[i + 1:])

function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  for (let l = i + 1, r = n - 1; l < r; l++, r--) [nums[l], nums[r]] = [nums[r], nums[l]];
}

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length, 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--;
            int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
        }
        for (int l = i + 1, r = n - 1; l < r; l++, r--) {
            int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
        }
    }
}

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());
}

Explanation

We want the very next bigger arrangement of the same numbers. The trick is to change as little as possible at the far right of the array, because the rightmost digits carry the smallest weight.

First we scan from the right to find the pivot: the first index i where nums[i] < nums[i+1]. Everything to the right of the pivot is already in descending order, so it is the largest it can be and cannot grow any further on its own.

To make the number just a bit bigger, we find the smallest value to the right of the pivot that is still larger than nums[i] (call its index j), and swap the two. Then we reverse the suffix after the pivot so that part becomes the smallest possible (ascending) order.

Example: nums = [1, 2, 3]. The pivot is index 1 (value 2, since 2 < 3). We swap it with 3 to get [1, 3, 2], then reverse the single-element suffix, ending at [1, 3, 2].

If no pivot exists, the whole array was descending (the biggest arrangement), so we just reverse the entire thing to wrap around to the smallest order.

Time: O(n) Space: O(1)