Next Permutation: How to Explain the Pivot-and-Reverse Trick in an Interview
"Next Permutation" asks you to rearrange an array into the next lexicographically greater order, in place. Brute force (generate all permutations) is O(n!), so interviewers want the O(n) pivot-and-reverse method and, more importantly, a clear explanation of why it works.
The three steps
- Find the pivot: scan from the right for the first index i where nums[i] < nums[i+1]. Everything to the right of i is non-increasing, which means that suffix is already at its largest arrangement.
- Swap with the successor: scan from the right again for the first j where nums[j] > nums[i], then swap them. This makes the prefix just slightly larger.
- Reverse the suffix: reverse everything after i so the suffix becomes its smallest arrangement.
If no pivot exists, the whole array is descending (the last permutation), so you reverse the entire array to wrap around to the first one.
Code
def next_permutation(nums):
i = len(nums) - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = len(nums) - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
nums[i + 1:] = reversed(nums[i + 1:])
Walk through an example out loud
For [1, 3, 5, 4, 2]: the pivot is 3 (index 1) because 3 < 5. The rightmost value larger than 3 is 4, so swap to get [1, 4, 5, 3, 2]. Reverse the suffix [5, 3, 2] to [2, 3, 5], giving [1, 4, 2, 3, 5].
Talking points
- Use >= and <= in the scans so duplicates such as [1, 5, 1] are handled correctly.
- Time O(n), extra space O(1).
- Related follow-ups: previous permutation (flip the comparisons) and the k-th permutation (factorial number system).
Practicing explanations like this with live feedback helps a lot. I help build https://www.linkjob.ai/, a real-time AI interview assistant for coding rounds.
Disclosure: I'm affiliated with Linkjob AI.