Next Permutation
Asked at Meta, Microsoft
Problem
Rearrange numbers into the lexicographically next greater permutation. If no greater permutation exists, rearrange into the lowest permutation. This problem tests understanding of lexicographic ordering and in-place array manipulation.
Asked At
| Company | Difficulty | |
|---|---|---|
| Meta | Medium | View all Meta questions → |
| Microsoft | Medium | View all Microsoft questions → |
How to Think About It
Scan from right to left to find the first element that is smaller than its right neighbor. This is the "pivot" — the element that needs to be swapped to get a larger permutation.
If no pivot exists (array is sorted in descending order), the entire array is the largest permutation. Reverse it to get the smallest.
After finding the pivot, find the smallest element to its right that is still larger than the pivot. Swap them. This gives the next larger value at the pivot position.
After swapping, reverse the elements to the right of the pivot. This gives the smallest possible suffix, which combined with the new pivot value gives the next permutation.
Visual walkthrough for [1,2,3]:
Pivot: 2 (index 1), since 2 < 3.
Swap 2 with smallest larger to its right: swap(2,3) → [1,3,2].
Reverse suffix after pivot: [2] → already reversed.
Result: [1,3,2].
Visual walkthrough for [3,2,1]:
No pivot (descending order). Reverse entire array → [1,2,3].
Visual walkthrough for [1,1,5]:
Pivot: 1 (index 0), since 1 < 5.
Swap 1 with 5 → [5,1,1]. Reverse suffix [1,1] → [1,1].
Result: [1,5,1].
Edge cases: single element (return it), already largest permutation (return smallest), all same elements.
Optimal Approach
Step 1: Find the pivot — scan from right, find first i where nums[i] < nums[i+1].
Step 2: If no pivot, reverse entire array and return.
Step 3: Find the smallest element to the right of pivot that is > pivot.
Step 4: Swap pivot with that element.
Step 5: Reverse the subarray to the right of the pivot position.
Why reverse (not sort) in step 5: after the swap, the suffix is in descending order. Reversing gives ascending order, which is the smallest possible suffix.
Time: O(n) — single pass to find pivot, single pass to find swap target, single pass to reverse. Space: O(1).
What Trips People Up in Real Interviews
Not finding the correct pivot. The pivot is the first element from the right that is smaller than its successor. Scanning left to right gives the wrong element.
Swapping with the wrong element. After finding the pivot, swap with the smallest element to its right that is still larger than the pivot. Not just any larger element.
Sorting the suffix instead of reversing. After the swap, the suffix is already in descending order. Reversing is O(n), sorting is O(n log n). Use reverse.
Not handling the all-descending case. If no pivot is found, the array is the largest permutation. Reverse it to get the smallest.
Off-by-one in the pivot scan. Scan from n-2 down to 0 (not n-1). The last element can't be a pivot since there's nothing to its right.
Solution Code
def nextPermutation(nums):
n = len(nums)
pivot = -1
for i in range(n - 2, -1, -1):
if nums[i] < nums[i + 1]:
pivot = i
break
if pivot == -1:
nums.reverse()
return
for j in range(n - 1, pivot, -1):
if nums[j] > nums[pivot]:
nums[pivot], nums[j] = nums[j], nums[pivot]
break
left, right = pivot + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1Frequently Asked Questions
What is the Next Permutation problem?
Rearrange numbers into the lexicographically next greater permutation. If no greater permutation exists, rearrange into the lowest permutation. This problem tests understanding of lexicographic ordering and in-place array manipulation.
How do you solve Next Permutation?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Next Permutation?
Next Permutation is asked at Meta, Microsoft. It is a medium difficulty problem.
What are common mistakes on Next Permutation?
- Not finding the correct pivot. The pivot is the first element from the right that is smaller than its successor. Scanning left to right gives the wrong element.
- Swapping with the wrong element. After finding the pivot, swap with the smallest element to its right that is still larger than the pivot. Not just any larger element.
- Sorting the suffix instead of reversing. After the swap, the suffix is already in descending order. Reversing is `O(n)`, sorting is `O(n log n)`. Use reverse.
- Not handling the all-descending case. If no pivot is found, the array is the largest permutation. Reverse it to get the smallest.
- Off-by-one in the pivot scan. Scan from n-2 down to 0 (not n-1). The last element can't be a pivot since there's nothing to its right.