31. Next Permutation
Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 33.9%
Problem Breakdown
We are given an integer list nums and need to rearrange its elements into the lexicographically next greater permutation in-place. If no such arrangement exists (meaning we have reached the highest possible order, e.g., [3, 2, 1]), we must reset it to the lowest possible order (ascending sort).
Key Constraints:
- In-Place Modification: We cannot return a new list;
numsitself must be mutated. - Constant Extra Space: auxiliary memory is required, ruling out sorting or generating all permutations.
- Edge Cases to Consider: Single element arrays (no change), strictly decreasing sequences (reset to ascending), and duplicate values within the array.
Intuition
A brute-force approach would be to generate every possible permutation ( complexity) until we find one greater than the current input, or sort all permutations lexicographically. This is computationally infeasible for . Even generating adjacent swaps and checking if they are larger leads to redundant checks.
The key insight lies in understanding how lexicographical order works: it compares elements from left to right. To find the next permutation, we want to keep the longest possible prefix unchanged because changing an earlier digit increases the value more significantly than a later one. We only need to change the suffix as little as necessary.
Looking at the array from right to left, permutations are ordered based on how “ascending” they end. If a sequence is strictly decreasing (e.g., 5, 4, 3), we cannot make it larger without changing an earlier number. We need to find the first position where this descending trend breaks—specifically, the rightmost index such that nums[i] < nums[i+1].
Once found:
- The suffix starting at is in non-increasing order (descending). To get a larger permutation with minimal change, we swap
nums[i]with the smallest number in this descending suffix that is strictly greater than it. This ensures the increase is minimized. - After swapping, the suffix remains in descending order but now starts higher. We must reverse the suffix to make it ascending (the lowest possible state for that prefix), ensuring we get the immediate next permutation rather than skipping ahead by a larger jump.
Approach
- Find Pivot: Iterate backwards from
len(nums) - 2down to0. Identify indexiwherenums[i] < nums[i+1]. If no such element exists (loop finishes without finding), the array is in descending order; reverse the entire list and return. - Find Swap Target: Iterate backwards from
len(nums) - 1down to0starting after indexi. Find the first elementnums[j]strictly greater thannums[i]. This ensures we pick the smallest valid increase for that position. - Swap and Reverse: Swap elements at indices
iandj. Finally, reverse the suffix fromi+1to the end of the list (since it is currently descending).
Complexity Analysis
- Time Complexity: . We traverse the array a constant number of times: once to find pivot , once to find swap index , and once to reverse the suffix. All operations are linear scans.
- Space Complexity: auxiliary space (excluding input storage). The reversal is done via pointer manipulation, not creating new lists.
Solution
def nextPermutation(nums):
n = len(nums)
# Helper function to reverse a subarray in-place
def reverse(start, end):
left = start
right = end - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# Step 1: Find the first pivot from right where nums[i] < nums[i+1]
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i == -1:
# Entire array is non-increasing (descending), reset to ascending order
reverse(0, n)
return
# Step 2: Find the smallest element in suffix greater than pivot nums[i]
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# Swap elements at i and j
nums[i], nums[j] = nums[j], nums[i]
# Step 3: Reverse the suffix to make it ascending (smallest possible order)
reverse(i + 1, n)
Edge Cases Handled
- Single Element (
[1]): Thewhile i >= 0loop condition fails immediately ( starts at -1). Code enters the reset block if needed or simply returns since reversing a single element does nothing, maintaining correctness. - Strictly Decreasing Sequence (
[3,2,1]): Pivot search finds no index where left < right ( becomes-1). The code reverses the entire array to[1, 2, 3], which is correct (lowest order). - Duplicates (
[1, 1, 5]): Logic uses strict inequalitynums[i] >= nums[i+1]. If duplicates exist in suffix like[5, 4, 4, 3], the search for swap target finds strictly greater values. The pivot logic correctly identifies where order breaks regardless of duplicate values adjacent to each other. - Already Ascending (
[1,2,3]): Pivot found at index0. Swap with largest valid element in suffix (index2). Reverse remaining[3]. Result[1, 3, 2], which is correct next permutation.