Next Permutation LeetCode 31 Guide

LeetCode 31 — Next Permutation — gives you an array of integers and asks you to rearrange it into the lexicographically next greater permutation of its digits. Lexicographic order means the same ordering used for words in a dictionary: you compare element by element from left to right, and the first position where the sequences differ determines which is larger. For example, [1,3,2] comes after [1,2,3] because they agree on the first element but 3 > 2 at the second.

If the input is already the largest possible permutation — meaning the array is in descending order like [3,2,1] — the next permutation wraps around to the smallest, which is the ascending-sorted arrangement [1,2,3]. This wrap-around behavior is explicitly required by the problem. The algorithm must handle this edge case without a special branch: the same three steps naturally produce the correct result.

The modification must be done in place, meaning you cannot create a new array and return it. The problem allows only O(1) extra memory, so sorting or building a new list is off-limits. The entire logic must work by swapping elements within the original array. The expected time complexity is O(n) — a single linear scan followed by a constant number of linear passes.

The three-step algorithm is the standard O(n) solution to Next Permutation. Step 1: scan the array from right to left to find the rightmost index i where nums[i] < nums[i+1]. This index is called the ascent point — it is the rightmost position where the sequence is still increasing from left to right. Everything to the right of i (the suffix nums[i+1:]) is in descending order.

Step 2: once the ascent index i is found, scan the suffix from right to left again to find the rightmost index j where nums[j] > nums[i]. Swap nums[i] and nums[j]. This makes the value at position i slightly larger than before — the smallest possible increase. After the swap, the suffix nums[i+1:] remains in descending order because we picked the rightmost element greater than nums[i], preserving the relative ordering of all other suffix elements.

Step 3: reverse the suffix nums[i+1:] in place. Reversing a descending sequence turns it into ascending order, which is the lexicographically smallest possible arrangement of those elements. The result is the next permutation. If no ascent exists (the entire array is descending), skip steps 2 and 3 and just reverse the entire array to get the first permutation.

To find the ascent point, start from the second-to-last index and scan leftward: set i = len(nums) - 2, then while i >= 0 and nums[i] >= nums[i+1]: i -= 1. The loop stops at the first index where nums[i] < nums[i+1], which is the rightmost ascent. The loop condition uses >= (not >) to handle duplicate values — if nums[i] == nums[i+1], we keep scanning left because that position does not qualify as an ascent.

If the loop exits with i < 0, no ascent was found. This means the entire array is in non-increasing order — it is the last permutation. The correct next permutation is the first permutation: the ascending sorted order. Rather than sorting, simply reverse the entire array in O(n). This is correct because the array is already in the worst (largest) order, and reversing it gives the best (smallest) order.

After finding a valid i, the algorithm guarantees that nums[i+1:] is sorted in descending order. This is a direct consequence of how the scan works: we stopped at i because nums[i] < nums[i+1], and we know for every position k > i that nums[k] >= nums[k+1] (otherwise we would have stopped at k, not i). This descending suffix property is exploited in both step 2 and step 3.

With the ascent index i identified, the next task is to find the best element in the suffix to swap with nums[i]. "Best" means the smallest value in the suffix that is still strictly greater than nums[i]. Swapping with this element makes the value at position i just barely larger than before, ensuring the result is the very next permutation rather than skipping ahead.

To find the swap partner, scan right to left from the end of the array: set j = len(nums) - 1, then while nums[j] <= nums[i]: j -= 1. The loop stops at the rightmost j where nums[j] > nums[i]. Because the suffix is descending, the rightmost such j gives the smallest qualifying value — if there are duplicates larger than nums[i], this finds the rightmost (and thus smallest among equals) one. Swap nums[i] and nums[j].

After the swap, the value at position i is now nums[j] (slightly larger than the original nums[i]). The suffix nums[i+1:] contains the original nums[i] in place of nums[j], but is still in descending order. Why? Because we swapped with the rightmost element greater than nums[i]. All elements to the right of j that are larger than the original nums[i] were already larger than nums[j] too, so the descending property holds throughout the suffix.

After the swap, the suffix nums[i+1:] is in descending order. To complete the next permutation, reverse this suffix in place. Reversing a descending sequence produces an ascending sequence, which is the lexicographically smallest possible arrangement of those elements. Since we already made position i slightly larger in step 2, we want everything after it to be as small as possible — and ascending order achieves that.

The reversal uses two pointers: left = i+1 and right = len(nums)-1. While left < right: swap nums[left] and nums[right], then left += 1, right -= 1. This runs in O(n/2) = O(n) time with O(1) space. No sorting is needed — the descending-to-ascending conversion via reversal is always valid after step 2, because the suffix is guaranteed to be in descending order at that point.

The complete three-step process — find ascent, swap with rightmost larger, reverse suffix — produces exactly the next permutation in lexicographic order. The total time complexity is O(n): one scan for the ascent (O(n)), one scan for the swap partner (O(n)), and one reversal (O(n)). Space complexity is O(1) because all operations are in-place swaps with no auxiliary data structures.

Python solution: def nextPermutation(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]; left,right=i+1,len(nums)-1; while left<right: nums[left],nums[right]=nums[right],nums[left]; left+=1; right-=1. Three while loops, O(n) time, O(1) space. Each loop traverses at most n elements. The i<0 guard handles the edge case where no ascent exists.

Trace through [1,2,3]: ascent found at i=1 (nums[1]=2 < nums[2]=3). Scan right for j: nums[2]=3 > nums[1]=2, so j=2. Swap: [1,3,2]. Reverse suffix after i=1: suffix is [2], single element, unchanged. Result: [1,3,2]. Trace through [3,2,1]: no ascent found (3>=2>=1), so i=-1. Skip swap. Reverse entire array: [1,2,3]. Result: [1,2,3].

Java solution: public void nextPermutation(int[] nums) { int i=nums.length-2; while(i>=0 && nums[i]>=nums[i+1]) i--; if(i>=0){ int j=nums.length-1; while(nums[j]<=nums[i]) j--; int tmp=nums[i]; nums[i]=nums[j]; nums[j]=tmp; } int l=i+1,r=nums.length-1; while(l<r){ int tmp=nums[l]; nums[l]=nums[r]; nums[r]=tmp; l++; r--; } }. The reversal runs unconditionally after the swap block — when i=-1, reversing from index 0 correctly handles the wrap-around.

Permutations (LeetCode 46) asks you to return all permutations of a list of distinct integers. While Next Permutation finds the single next permutation in O(n), LeetCode 46 generates all n! permutations using backtracking. Understanding how lexicographic order works — as taught by Next Permutation — helps you reason about the ordering of permutations returned by LeetCode 46 and about deduplication strategies in LeetCode 47 (Permutations II).

Subsets II (LeetCode 90) involves generating all subsets of an array that may contain duplicates, and uses sorting to skip duplicate elements during backtracking. The same sorted-array intuition from Next Permutation — where the suffix being sorted is key to the algorithm — reappears in Subsets II when you sort the input to group duplicates together and decide when to skip a candidate.

Combination Sum (LeetCode 39) and array manipulation problems like Rotate Array (LeetCode 189) round out this family. Rotate Array uses a three-reversal technique that is structurally similar to the suffix reversal in Next Permutation: both problems exploit the reversal-of-a-reversal identity to rearrange array segments in O(n) time with O(1) space. Studying these problems together deepens understanding of in-place array manipulation as a general technique.