Next Permutation — Solution in Python, Java & C++
Next Permutation solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Next Permutation is a medium coding problem on arrays and two pointers, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Arrays, Two Pointers
- Asked at: Amazon, Google, Microsoft, Meta, Flipkart, Rubrik
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A permutation of an array is one of its possible orderings. Listing all permutations of an array in increasing lexicographic order gives a sequence; the next permutation of an arrangement is the one that follows it in that sequence.
If no greater arrangement exists, the next permutation is the smallest one — the array sorted in ascending order.
Given nums, return its next permutation.
Example 1
Input: nums = [1,2,3]
Output: [1,3,2]
Example 2
Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: This is the largest arrangement, so it wraps to the smallest.
Example 3
Input: nums = [1,1,5]
Output: [1,5,1]
Constraints
1 <= nums.length <= 200 <= nums[i] <= 30
Hints for Next Permutation
Hint 1
Scan from the right for the first index
iwithnums[i] < nums[i + 1]— the suffix after it is non-increasing and already maximal.Hint 2
Swap
nums[i]with the rightmost element greater than it; that is the smallest possible increase at positioni.Hint 3
Then reverse the suffix, turning the largest arrangement of those values into the smallest.
How to solve Next Permutation
Find the rightmost position that can still be increased, raise it by the smallest possible amount, then make the suffix after it as small as possible.
Approach
- Scan from the right for the first
iwithnums[i] < nums[i + 1]; the suffix afteriis non-increasing. - If such
iexists, find the rightmostj > iwithnums[j] > nums[i]and swap them. - Reverse the suffix starting at
i + 1.
Why it works
The suffix after i is the largest arrangement of its elements, so no larger permutation shares the prefix through i. Swapping in the smallest larger value at i gives the least possible increase there, and the suffix stays non-increasing, so reversing it yields the smallest completion. When no i exists the array is the last permutation and reversing everything wraps to the first.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- The comparisons must be
>=/<=when scanning so equal elements are skipped correctly. - Forgetting the reverse produces a larger permutation, not the next one.
Reference solution
Python
def nextPermutation(nums):
nums = list(nums)
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
return numsJava
public static int[] nextPermutation(int[] nums) {
int[] a = Arrays.copyOf(nums, nums.length);
int n = a.length;
int i = n - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i >= 0) {
int j = n - 1;
while (a[j] <= a[i]) j--;
int t = a[i]; a[i] = a[j]; a[j] = t;
}
for (int l = i + 1, r = n - 1; l < r; l++, r--) {
int t = a[l]; a[l] = a[r]; a[r] = t;
}
return a;
}C++
vector<int> nextPermutation(vector<int>& nums) {
vector<int> a = nums;
int n = (int) a.size();
int i = n - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i >= 0) {
int j = n - 1;
while (a[j] <= a[i]) j--;
swap(a[i], a[j]);
}
reverse(a.begin() + i + 1, a.end());
return a;
}JavaScript
var nextPermutation = function(nums) {
const a = nums.slice();
const n = a.length;
let i = n - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i >= 0) {
let j = n - 1;
while (a[j] <= a[i]) j--;
const t = a[i]; a[i] = a[j]; a[j] = t;
}
for (let l = i + 1, r = n - 1; l < r; l++, r--) {
const t = a[l]; a[l] = a[r]; a[r] = t;
}
return a;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique