Problem Statement

Next Permutation

A permutation is just one specific ordering of the numbers in a list. If you write out all the orderings and sort them like words in a dictionary (this is called lexicographic order, meaning smallest first when you compare position by position), each ordering has a "next" one right after it. Your job: take the current ordering and turn it into the very next one in that dictionary list. If you are already at the last one (the numbers are in fully descending order, biggest to smallest), wrap back around to the first one (ascending order, smallest to biggest). The trick has three steps: (1) find the rightmost spot where a number is smaller than the one just after it (we call this the "pivot"), (2) find the rightmost number bigger than the pivot and swap them, (3) flip the tail of the list that comes after the pivot. This gives the smallest ordering that is still bigger than what you started with.

mediumArrayArrays & HashingTime: O(n) · Space: O(1)

Signals to notice

rearrange to next lexicographic permutationin-placefind the pivot point

Brute force first

Generate all permutations in order, find the current one, return the next. Catastrophically slow. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.

The key insight

Three steps: (1) Find the rightmost pair where nums[i] < nums[i+1] — that's the pivot. (2) Find the smallest element to the right of i that's larger than nums[i], swap them. (3) Reverse everything after position i. Instead of recomputing the world every time, you preserve just enough context to let the next decision become obvious.

Trace it on `nums=[1,3,5,4,2]`

Find pivot from right: i=3 (4>=2)→ i=2 (5>=4)→ i=1 (3<5) STOP. pivot i=1, nums[i]=3
Suffix [5,4,2] is descending; pivot is the last ascending step
Find swap target j from right: j=4 (2<=3)→ j=3 (4>3) STOP. j=3, nums[j]=4
Swap nums[1] and nums[3] → nums=[1,4,5,3,2]
Reverse suffix after i (indices 2..4): left=2,right=4 swap → [1,4,2,3,5]; left=3,right=3 STOP
Return [1,4,2,3,5]

What must stay true

The rightmost ascending pair marks where the permutation can be incremented. Swapping with the next larger element advances the digit, and reversing the suffix resets it to the smallest arrangement. As long as that statement keeps holding, you can trust the steps built on top of it.

Shape of the loop

i = n - 2
while i >= 0 and nums[i] >= nums[i+1]: i -= 1   # find pivot
if i >= 0:
    j = n - 1
    while nums[j] <= nums[i]: j -= 1            # next larger to the right
    swap(nums[i], nums[j])
reverse(nums, i+1, n-1)                          # reset suffix to ascending

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

If no ascending pair exists (array is fully descending), the answer is the first permutation — reverse the entire array. When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.

Arrays & Hashing Pattern