Next Permutation
Medium · Backtracking · Array · Two Pointers
Problem
Imagine listing every ordering of an integer array in lexicographic (dictionary) order. The next permutation of nums is the ordering that comes immediately after it in that list. If nums is already the last (largest) ordering, the next one wraps around to the first: the values in ascending order.
Rearrange nums in place into its next permutation, using only constant extra memory. Your function returns nothing; the tests check nums after the call.
Examples
Input: nums = [1,3,2] Output: [2,1,3]
Among the orderings of 1, 2 and 3, the one after 1,3,2 is 2,1,3.
Input: nums = [4,3,2,1] Output: [1,2,3,4]
4,3,2,1 is the largest ordering, so it wraps to ascending order.
Input: nums = [2,4,4] Output: [4,2,4]
With duplicates, each distinct ordering counts once: after 2,4,4 comes 4,2,4.
Constraints
- 1 <= len(nums) <= 100
- 0 <= nums[i] <= 100
Approaches
- Baseline: try each position from the right, sort what follows — time O(n²), space O(1)
Follow-up
How would you step backwards instead? Flip every comparison: find the first drop from the right, swap with the rightmost smaller value, and reverse. See the use case “The ordering just before”. The same scan also finds the next larger number with the same digits.
Related problems
Start free on Cariara · Coding problems · System design studio
