Next Permutation
Medium Pivot + reverse
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Rearrange the array into the next larger ordering of its numbers in dictionary order. If it's already the largest, wrap around to the smallest. Do it in place.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the next bigger arrangement of the same digits.
Why this works: from the right, find the first digit that can be increased (smaller than its right neighbour). Swap it with the smallest bigger digit on its right, then make the tail as small as possible.
Example: [1, 3, 5, 4, 2]
pivot: 3 (since 3 < 5)smallest bigger on right: 4 → swap → [1, 4, 5, 3, 2]reverse tail [5,3,2] → [1, 4, 2, 3, 5]
✦Hints open one at a time
↗Approach
Find the pivot i scanning from the right. If none exists, reverse everything. Otherwise find j from the right with nums[j] > nums[i], swap, and reverse i+1..end (it's still decreasing, so reversing sorts it).
</>Solution (Java)
class Solution {
public void nextPermutation(int[] nums) {
int i = nums.length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // find the pivot
if (i >= 0) {
int j = nums.length - 1;
while (nums[j] <= nums[i]) j--; // just-larger element on the right
swap(nums, i, j);
}
reverse(nums, i + 1, nums.length - 1); // smallest possible suffix
}
private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
private void reverse(int[] a, int l, int r) { while (l < r) swap(a, l++, r--); }
}!Common mistake
Sorting the suffix instead of reversing — correct but O(n log n), and it misses the key observation.
- Time: O(n).
- Space: O(1).
