Next Permutation Solutions & Complexity

1. Define the problem

Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. The next permutation of an array of integers is the next lexicographically greater permutation of its integers. If no such arrangement is possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). Rearrange the array into its next permutation, in place, using only constant extra memory. Scan from the right to find the first index i where nums_i < nums[i+1] (the pivot); if found, scan from the right again for the rightmost index j where nums_j > nums_i , swap them, then reverse everything after i; if no pivot is found, reverse the whole array.

Constraints

1 ≤ nums.length ≤ 100
0 ≤ nums_i ≤ 100

Example

Inputnums = [1, 2, 3]

Output[1, 3, 2]

Explanation The permutations of [1,2,3] in order are [1,2,3], [1,3,2], [2,1,3], ... — the one immediately after [1,2,3] is [1,3,2].

2. Know the words first

In plain terms

Permutation: One specific ordering of a set of values — the numbers [1,2,3] have six different permutations, one of which is [2,1,3].
Lexicographically: Compared the way words are ordered in a dictionary — element by element from the left, so [1,3,2] comes before [2,1,3] because 1 < 2 at the first position.

3. Visualize the solution

Find the pivot, swap with the smallest larger value, then reverse the suffix

Statusfind-pivot

Scanning from the right: nums[1]=2 < nums[2]=3, so i=1 is the pivot.

What happens in this step

nums = [1, 2, 3]
start i = n - 2 = 1
check: nums[1]=2 >= nums[2]=3? → false (2 < 3), so the while loop
stops immediately — i=1 is already the pivot, the first "ascent"
found scanning from the right.

Step 1 of 4

Steps to visualize

Scan from the right to find the first index i where nums_i is smaller than nums[i+1] — the pivot.
If no such index exists, the array is in its highest permutation, so just reverse it entirely.
Otherwise scan from the right again for the rightmost index j where nums_j is greater than nums_i.
Swap nums_i and nums_j.
Reverse everything after index i to put the suffix in its lowest order.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Find the pivot, swap with the smallest larger value, then reverse the suffix

Statusfind-pivot

Scanning from the right: nums[1]=2 < nums[2]=3, so i=1 is the pivot.

What happens in this step

nums = [1, 2, 3]
start i = n - 2 = 1
check: nums[1]=2 >= nums[2]=3? → false (2 < 3), so the while loop
stops immediately — i=1 is already the pivot, the first "ascent"
found scanning from the right.

Step 1 of 4

5. Solution

Solution

solution.tsTypeScript

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--;
    }
    const temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }

  let left = i + 1;
  let right = n - 1;
  while (left < right) {
    const temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    left++;
    right--;
  }

  return nums;
}

Time: O(n)
Space: O(1) (in place, excluding the returned array)

6. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 3]`	`[1, 3, 2]`	example from the docstring
`nums = [3, 2, 1]`	`[1, 2, 3]`	the highest permutation wraps around to the lowest
`nums = [1, 1, 5]`	`[1, 5, 1]`	duplicate values among the digits
`nums = [1, 2]`	`[2, 1]`	smallest valid input: only two elements
`nums = [1]`	`[1]`	a single-element array has no next permutation, stays the same
`nums = [1, 3, 2]`	`[2, 1, 3]`	a pivot found further left, with a suffix reversal after the swap

Next Permutation