Leetcode 31. Next Permutation
Rearrange the array in-place to produce the lexicographically next greater permutation (using only O(1) extra space); if no larger permutation exists, reorder it to the lowest (ascending) permutation.
Asked at:
Meta
Amazon
DESCRIPTION
Rearrange the array in-place to produce the lexicographically next greater permutation (using only O(1) extra space); if no larger permutation exists, reorder it to the lowest (ascending) permutation.
Input:
nums = [1, 2, 3]
Output:
[1, 3, 2]
Explanation: The next lexicographically greater permutation of [1,2,3] is [1,3,2]
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
- Must modify the array in-place with O(1) extra space
Understanding the Problem
Let's understand what we're being asked to do. We have an array like [1, 2, 3] and need to rearrange it to the next lexicographically greater permutation.
Tracing through: [1, 2, 3] becomes [1, 3, 2] (next greater). Then [1, 3, 2] becomes [2, 1, 3] (next greater). Eventually [3, 2, 1] is the largest permutation, so it wraps around to [1, 2, 3] (smallest).
Important constraint: We must rearrange in-place using only O(1) extra space. We can't create a new array!
Edge cases to consider: What if the array is already the largest permutation like [3, 2, 1]? (wrap to smallest: [1, 2, 3]). What if all elements are the same like [1, 1, 1]? (no change). What if the array has only one element?
Building Intuition
To find the next permutation, we need to find the rightmost position where we can make a swap that increases the value.
Look from right to left: find the first element that is smaller than its right neighbor. This is the 'pivot' - the position where we can increase the value. Everything to the right of this pivot is in descending order (that's why we couldn't find a swap earlier).
Once we find the pivot, we need to swap it with the smallest element to its right that is larger than it. This gives us the minimal increase.
But we're not done! After the swap, the elements to the right of the pivot are still in descending order. To get the next permutation (not just any larger one), we must reverse this suffix to make it ascending (the smallest arrangement).
Think about counting: to go from 1234 to the next number, you increment the rightmost digit: 1235. But what about 1239? You can't just increment the 9.
Instead, you find the rightmost digit you can increment (the 3), increment it to 4, and reset everything to its right to the smallest values: 1240. The same logic applies to permutations - find where you can 'increment', do the minimal increment, then reset the suffix to its smallest arrangement.
Common Mistakes
Optimal Solution
The optimal approach works in three steps: (1) Find the rightmost 'pivot' - the first element from the right that is smaller than its right neighbor. If no such element exists, the array is the largest permutation. (2) Find the smallest element to the right of the pivot that is larger than the pivot, and swap them. (3) Reverse the suffix after the pivot position to get the smallest arrangement. This gives us the next lexicographically greater permutation in-place with O(1) space.
def next_permutation(nums):"""Rearrange array to next lexicographically greater permutation in-place.If no larger permutation exists, rearrange to smallest (ascending) order."""n = len(nums)# Step 1: Find the rightmost pivot (first element from right smaller than its right neighbor)pivot = -1for i in range(n - 2, -1, -1):if nums[i] < nums[i + 1]:pivot = ibreak# If no pivot found, array is largest permutation - reverse entire arrayif pivot == -1:nums.reverse()return nums# Step 2: Find smallest element to right of pivot that is larger than pivotsuccessor = -1for i in range(n - 1, pivot, -1):if nums[i] > nums[pivot]:successor = ibreak# Swap pivot with successornums[pivot], nums[successor] = nums[successor], nums[pivot]# Step 3: Reverse the suffix after pivot to get smallest arrangementleft = pivot + 1right = n - 1while left < right:nums[left], nums[right] = nums[right], nums[left]left += 1right -= 1return nums
Start: Find next lexicographically greater permutation
0 / 12
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n) We scan the array from right to left once to find the pivot (O(n)), then scan again to find the swap candidate (O(n)), then reverse the suffix (O(n)). All steps are linear, giving O(n) total time.
Space Complexity: O(1) We only use a constant number of variables (pivot index, swap index, pointers for reversal) regardless of array size. The rearrangement is done in-place with no additional data structures.
What We've Learned
- Two-pointer pivot identification: The next permutation algorithm starts by scanning from right-to-left to find the first pivot element (arr[i] < arr[i+1]) - this rightmost ascending pair marks where the permutation can be increased, since everything to its right is already in descending order (the largest possible arrangement).
- Reverse for minimal increment: After swapping the pivot with its successor, reverse the suffix (everything after the pivot position) rather than sorting it - this works because the suffix is already in descending order, and reversing transforms it to ascending order (the smallest arrangement), ensuring the next permutation is the immediate successor.
- In-place array manipulation mastery: Achieve O(1) space by using three distinct operations on the same array: (1) right-to-left scan to find pivot, (2) right-to-left scan to find swap candidate, (3) two-pointer reversal of suffix - no auxiliary data structures needed.
- Edge case: descending array handling: When no pivot exists (array is completely descending like [3,2,1]), the entire array IS the suffix to reverse - this naturally wraps around to the smallest permutation [1,2,3], elegantly handling the circular boundary condition without special logic.
- Greedy successor selection: When finding the element to swap with the pivot, scan from the right to find the smallest element that's still larger than the pivot - this greedy choice ensures we increment the permutation by the minimum amount necessary for the next lexicographic order.
- Permutation generation pattern: This algorithm is the foundation for iterative permutation enumeration - repeatedly applying next permutation generates all n! permutations in sorted order, useful for combinatorial problems, testing frameworks, and scenarios where recursive backtracking is too memory-intensive.
Related Concepts and Problems to Practice
medium
Sort Colors requires in-place array manipulation with O(1) space using two pointers to partition elements, similar to how Next Permutation requires in-place rearrangement. Both problems involve scanning and swapping elements to achieve a specific ordering without extra space.
easy
Move Zeroes practices in-place array rearrangement with O(1) space constraint using two pointers. This builds foundational skills for understanding how to manipulate array elements in-place, which is essential for solving Next Permutation's rearrangement challenge.
medium
Rotate Image requires in-place matrix transformation with O(1) extra space, involving careful element swapping and positioning logic. This shares the same space constraint and manipulation pattern as Next Permutation, helping develop skills in complex in-place array transformations.
Test Your Understanding
Why is array the right data structure for this problem?
array provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Mid December, 2025
Meta
Senior
Early November, 2025
Meta
Manager
https://leetcode.com/problems/next-permutation
Early October, 2025
Meta
Mid-level
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.