LeetCode #31 Medium

Next Permutation

Rearrange nums into the next lexicographically greater permutation in place. If none exists, wrap to the smallest (ascending) arrangement.

arraytwo-pointers

Open on LeetCode ↗

02

Intuition

💡

Scanning from the right, find the first place where order dips — that pivot is the digit we can grow. Swap it with the smallest value to its right that still beats it, then reverse the tail so it becomes the smallest possible suffix.

03

Approach

1

Enumerating permutations is hopeless

Listing all n! permutations to find the one after the current arrangement is astronomically slow. Instead we reason directly about what 'the next larger arrangement' means lexicographically, like finding the next number with the same digits — and that turns out to need just three local operations.

2

Find the pivot: the first dip from the right

Scan from the right for the first index i where nums[i] < nums[i+1]. Everything to the right of i is in descending order, which means that suffix is already the largest it can be — you can't make the number bigger by rearranging only the suffix. So the digit that must increase is nums[i], the pivot. (If no such i exists, the whole array is descending — it's the largest permutation, and the answer wraps to the smallest.)

3

Swap minimally, then reset the tail

To grow the number by the smallest possible amount, swap the pivot with the smallest value to its right that still exceeds it — found by scanning from the far right for the first nums[j] > nums[i]. After the swap, the suffix is still descending; since we want the smallest tail following the increased pivot, reverse that suffix into ascending order. Pivot-find, swap, reverse — all O(n), O(1) space, in place.

04

Solution & live demo

python

▶1class Solution:
▶2    def nextPermutation(self, nums):
▶3        n = len(nums)
▶4        i = n - 2
▶5        while i >= 0 and nums[i] >= nums[i + 1]:
▶6            i -= 1
▶7        if i >= 0:
▶8            j = n - 1
▶9            while nums[j] <= nums[i]:
▶10                j -= 1
▶11            nums[i], nums[j] = nums[j], nums[i]
▶12        nums[i + 1:] = reversed(nums[i + 1:])

05

Edge cases

Already the largest, e.g. [3,2,1]

No pivot is found (i falls below 0); the suffix reverse then turns the whole array ascending — the smallest permutation.

Single element

No pivot, no swap; reversing a length-1 suffix leaves it unchanged.

Duplicates, e.g. [1,5,1]

The >=/<= comparisons pick the correct pivot and swap target even with repeats.

06

Complexity

Time

O(n)

Space

O(1)

A scan, a swap, and a reverse — all linear.