Algorithm

Next Permutation

Arrays & Strings Pattern

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographical next greater permutation. If such arrangement is not possible, it must be rearranged as the lowest possible order (i.e., sorted in ascending order). The replacement must be in-place and use constant extra memory.

CONSTRAINTS
  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100
EXAMPLE 1
Input: nums = [1,2,3]
Output: [1,3,2]
Pivot is 2 (since 2 < 3). Swap with 3, reverse the (single-element) tail. [1,3,2] is the very next arrangement after [1,2,3].
EXAMPLE 2
Input: nums = [3,2,1]
Output: [1,2,3]
Fully descending — already the largest arrangement. No pivot exists, so we wrap around by reversing everything to the smallest.
EXAMPLE 3
Input: nums = [1,1,5]
Output: [1,5,1]
Duplicates are fine: pivot is the second 1 (1 < 5), swap with 5, reverse the tail.
What does 'lexicographically next' mean exactly?
Line up all rearrangements in dictionary order (compare element by element from the left). Return the one immediately after the current arrangement — the smallest rearrangement strictly greater than it.
What if the array is entirely decreasing?
Then it is already the largest possible arrangement. The problem defines the answer as wrapping to the smallest — i.e. reverse the array into ascending order.
How do duplicates affect the algorithm?
They are handled by two strictness choices: the pivot scan skips equal neighbors (nums[i] >= nums[i+1] keeps moving), and the successor must be strictly greater than the pivot. Both are needed to avoid swapping equal values and producing the same permutation.
Do I return a new array?
No — modify nums in place with O(1) extra memory. There is no return value.

Finding the next permutation is like finding the "next largest" number you can build using a specific set of digits. To keep the increase as small as possible, we want to modify the number as far to the right as possible, shifting the smallest "weight" digits first.

Sort All Permutations (O(N!))

The most naive approach is to generate every single permutation of the numbers, sort them lexicographically, find the current arrangement, and return the one immediately after it. Since there are N! permutations, this becomes impossible for even small arrays (e.g., 10! is over 3 million).

python
# Theoretical approach:
all_perms = sorted(generate_all_permutations(nums))
current_idx = all_perms.find(nums)
return all_perms[current_idx + 1]
2. The Insight: Seek the "Least Increase" from the Right

To make the change as small as possible, we look for the first opportunity (starting from the right) where a smaller digit can be swapped with a larger one.
- If a sequence is decreasing (e.g., [7, 5, 4, 1]), it is already at its maximum possible value. No swap within this group can make it larger.
- We must find the first "dip" from the right — the point where nums[i] < nums[i+1]. This digit is our Pivot.

Pivot, Swap, and Reverse (O(N))

We can find the next permutation in three precise steps:
1. Find Pivot (i): Scan from right to left. Stop at the first index where nums[i] < nums[i+1].
2. Find Successor (j): If a pivot exists, scan from right to left again to find the smallest number that is still strictly larger than nums[i]. Swap them.
3. Reverse Tail: The numbers to the right of the pivot are currently in decreasing order. Reverse them to make them as small as possible (increasing order).

python
# 1. Find the first dip from the right
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i+1]:
    i -= 1

if i >= 0:
    # 2. Swap pivot with the smallest larger number to its right
    j = len(nums) - 1
    while nums[j] <= nums[i]:
        j -= 1
    nums[i], nums[j] = nums[j], nums[i]

# 3. Reverse the descending tail to make it as small as possible
nums[i+1:] = nums[i+1:][::-1]
Worked Example:[1, 2, 7, 4, 3, 1]
0
1
1
2
pivot (i)
2
7
3
4
4
3
5
1
We scan the array from right to left to find the first decrease in value. We locate this pivot point at index 1, where the number 2 is smaller than the adjacent 7.
0
1
1
3
i
2
7
3
4
4
2
j
5
1
We scan the elements to the right of our pivot to find the smallest number that is still larger than 2. We find 3 at index 4 and swap it with our pivot 2.
0
1
1
3
i
2
1
3
2
4
4
5
7
To get the next smallest lexicographical permutation, we reverse the sequence to the right of our pivot, turning the descending list into an ascending one. This completes the transformation.
Interactive Strategy Visualization

Next Permutation Logic

Lexicographical Shift Strategy
1
2
7
4
3
1
Starting: Find the next bigger sequence version of [1, 2, 7, 4, 3, 1].
LEXICOGRAPHICAL RULE

We find the rightmost pivot point that can be increased, swap it with its smallest larger successor, and set the rest to the smallest order (reverse).

THE MAX CASE

If no pivot is found (descending order), we are at the absolute last permutation. We reverse the entire array to wrap back to the first.

O(N!) Generate All
→
O(N) Pivot-Swap-Reverse