How to Solve Next Permutation on LeetCode
The Next Permutation problem is a popular LeetCode question that demonstrates your ability to manipulate arrays in-place and reason about permutations.
Problem Statement
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, rearrange it as the lowest possible order (i.e., sorted in ascending order).
Example:
Input: nums = [1,2,3]
Output: [1,3,2]
Why This Problem Matters for Interviews
This problem:
- Tests in-place array manipulation
- Builds understanding of permutation theory
- Requires identifying and reversing subarrays
Steps for Next Permutation
In-Place Modification (Optimal)
- Find first decreasing element from right.
- Swap it with just larger element on the right.
- Reverse the subarray after original index.
Time Complexity: O(n)
Space Complexity: O(1)
def nextPermutation(nums: list[int]) -> None:
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]
left, right = i+1, len(nums)-1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
Key Interview Talking Points
- Why reverse is required after swap
- Handling already highest permutation (descending)
- Lexicographical ordering definition
- Edge cases: single-element array
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| In-place Swap | O(n) | O(1) |
Pro Interview Tips
- Walk through the algorithm step-by-step on example input.
- Use pointers and drawing for explanation.
- Practice with test cases