← DSA Atlas
Dedicated problem page · #31

Next Permutation

MediumTwo PointersFind pivot, swap successor, reverse suffixTwo pointers (in-place array manipulation)
Solve on LeetCode ↗
31
MediumTwo PointersTwo pointers (in-place array manipulation)Find pivot, swap successor, reverse suffix

Next Permutation

Rearrange nums into the lexicographically next greater permutation of its numbers, in place. If no greater permutation exists (the array is in descending order), rearrange it to the lowest possible order (ascending). Use only constant extra memory.

Open official problem prompt ↗
In plain English

Transform the array in place into the very next arrangement in dictionary order, wrapping to the smallest arrangement when it is already the largest.

Picture it like this

Like counting up on an odometer of digits: you find the rightmost digit you can bump up minimally, replace it with the next-larger available digit, and reset everything to its right to the smallest possible tail.

Example
Input
nums = [1, 2, 3]
Output
[1, 3, 2]
Why
Among all permutations of {1,2,3}, [1,3,2] is the smallest one strictly greater than [1,2,3].
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 100
Pattern lesson

See the pattern, then code

Find pivot, swap successor, reverse suffix
Recognition clue

The phrase 'next permutation in place with O(1) memory' points to the classic pivot-swap-reverse pointer procedure, not to generating permutations.

↗
Two Pointers

Sorted input, opposite-end scanning, pair search, or in-place compaction.. Scanning from the right, the longest descending suffix is already maximal; to grow the number minimally, swap the pivot just left of it with the smallest suffix value that still exceeds it, then reverse the suffix to its smallest arrangement.

New words, made simpleKnow these before the algorithm
Pivot
The rightmost index i with nums[i] < nums[i+1]; the spot that can be increased.
Descending suffix
The trailing run that is already the maximum permutation of those elements.
Successor
The smallest suffix value still larger than the pivot, chosen for the swap.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Generate and sort all permutations

Astronomically slow and memory-heavy; ignores the required O(1) space.

List every permutation, sort them, and pick the one after the current.

Time O(n! * n)Space O(n!)
Best choicePivot-swap-reverse

Linear, in place, and directly constructs the next permutation.

Locate the pivot, swap with its smallest larger successor, reverse the suffix.

Time O(n)Space O(1)
The rule we keep true

Invariant

Everything to the right of the pivot is in non-increasing order, so it is the maximal arrangement of those elements and reversing it produces their minimal arrangement.

Why this is correct

Reasoning

Increasing the pivot to the smallest value that still beats it is the least possible increase at that position; making the suffix ascending afterward gives the smallest tail, so the result is the immediate next permutation. When no pivot exists the array is fully descending (the largest permutation), and reversing gives the smallest.

The algorithm in three movesSay these aloud before coding
1From the right, find the first index i where nums[i] < nums[i+1] (the pivot)

pivot i=1 (nums[1]=2 < nums[2]=3)

2If no pivot exists, reverse the whole array and stop

j=2 (nums[2]=3 > 2) -> swap -> [1,3,2]

3From the right, find the first j with nums[j] > nums[i] and swap i and j

reverse suffix [2:] (single element) -> [1,3,2]

4Reverse the suffix after index i to make it ascending

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
21
32
1 · Read[1,2,3]
2 · AskRightmost i with nums[i]<nums[i+1]?
3 · Update statei=2: 3? none; i=1: 2<3 yes
4 · Resultpivot i=1.
Key takeaway

Pivot at index 1 swaps with its successor 3, then the one-element suffix stays put, yielding [1,3,2].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-6Locate pivot

    Walk left while the suffix stays non-increasing to find the first ascent from the right.

  2. 2
    Lines 7-11Swap successor

    If a pivot exists, find the smallest suffix value greater than it and swap.

  3. 3
    Lines 12-17Reverse the suffix

    Turn the (still descending) tail into ascending order, which is its minimum; this also handles the all-descending case by reversing the whole array.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single element stays unchanged
  • Strictly descending input like [3,2,1] wraps to ascending [1,2,3]
  • Duplicates like [1,1,5] are handled because comparisons use >= and > appropriately
  • Already-minimal arrays advance by one step
!

Common beginner mistakes

  • Using strict > in the pivot search (should be >=) causes wrong behavior with equal neighbors
  • Using >= instead of > when finding the successor j picks an equal value and fails to increase the permutation
  • Forgetting to reverse the suffix, leaving a non-minimal tail
Check your understanding

Why reverse the suffix instead of sorting it ascending?

More in Two Pointers

#153SumSorted two-pointer scan around a fixed anchor#11Container With Most WaterConverging pointers on a width-vs-height tradeoff#184SumTwo fixed anchors plus a sorted two-pointer inner scan#26Remove Duplicates from Sorted ArraySlow/fast in-place overwrite#42Trapping Rain WaterConverging pointers tracking left/right maxima#75Sort ColorsDutch National Flag partition