Next Permutation

Imagine listing every arrangement of the numbers in nums in dictionary (lexicographic) order, comparing arrangements element by element from the left. For example, the arrangements of [1, 2, 3] in that order are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

Rearrange nums in place into the arrangement that comes right after the current one. If the current arrangement is already the last (largest) one, rearrange it into the first (smallest) one, i.e. sorted ascending.

Your function should modify nums directly and return nothing; the judge checks the contents of nums afterwards. Use only O(1) extra memory. Values may repeat.

Example 1

Example 2

Example 3

Constraints

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

Pattern Path · Two Pointers · problem 22 of 169

Start simple

Generate every permutation, sort them and pick the one after the current arrangement: O(n! · n) time.

The key idea

To get the very next arrangement you want to change as little as possible at the left, so look for the rightmost position that can still increase.

Scan from the right while the values are non-increasing. That suffix is already in its largest order, so no rearrangement of it alone makes a bigger array. Let i be the index just left of it, so nums[i] < nums[i + 1]. If no such index exists, the whole array is the largest arrangement and reversing it gives the smallest.

Position i must now grow, but by as little as possible: swap nums[i] with the smallest suffix value that is larger than it. Because the suffix is non-increasing, that is the rightmost value greater than nums[i], found by scanning from the end.

After the swap, the suffix is still non-increasing (the swapped-in value fits in the same place). The prefix up to i is now the smallest possible bigger prefix, so the suffix should be as small as possible, which means ascending. Reversing a non-increasing run sorts it in O(n), with no extra memory.

Using strict comparisons in both scans handles repeated values correctly.

Complexity

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

Python

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        # 1. Find the pivot: the rightmost i with nums[i] < nums[i + 1].
        i = len(nums) - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            # 2. Swap it with the rightmost (= smallest) larger value in the suffix.
            j = len(nums) - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        # 3. The suffix is non-increasing; reverse it to make it as small as possible.
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

JavaScript

var nextPermutation = function(nums) {
  const swap = (a, b) => { [nums[a], nums[b]] = [nums[b], nums[a]]; };

  // 1. Find the pivot: the rightmost i with nums[i] < nums[i + 1].
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;

  if (i >= 0) {
    // 2. Swap it with the rightmost (= smallest) larger value in the suffix.
    let j = nums.length - 1;
    while (nums[j] <= nums[i]) j--;
    swap(i, j);
  }

  // 3. The suffix is non-increasing; reverse it to make it as small as possible.
  for (let left = i + 1, right = nums.length - 1; left < right; left++, right--) {
    swap(left, right);
  }
};

What the interviewer is checking

The interviewer is testing whether you can reason about lexicographic order from first principles and turn that reasoning into careful index manipulation in place.

Mistakes to avoid

• Using <= or >= in the wrong scan, which breaks on duplicates such as [1, 5, 1].
• Swapping with the first larger value in the suffix instead of the smallest larger one.
• Sorting the suffix (O(n log n)) when a reverse is enough, or forgetting the full wrap-around case.

Follow-ups to expect

• How would you find the previous permutation? (Mirror every comparison.)
• How would you generate all permutations in order? (Start sorted; repeat until wrap.)
• What is the k-th permutation of 1..n? (Factorial number system.)

In real software

C++'s std::next_permutation uses exactly this algorithm, and it is how test generators and brute-force solvers enumerate orderings without storing them.

Practice next