Next Permutation
Problem Description
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.
For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].
The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2].
Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory.
Examples
Input: nums = [1,2,3]
Output: [1,3,2]
Input: nums = [3,2,1]
Output: [1,2,3]
Input: nums = [1,1,5]
Output: [1,5,1]
Constraints
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
Okay ! After going through the problem statement, What could we think about the logic?After reading the problem, the first thing that comes to mind is: How can we use the current permutation to find the next permutation?
Brute Force Approach
Intuition
Okay, as per the problem description, we know that, "The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such an arrangement is not possible, i.e if the current permutation is the last one in the permutations list then we need to return the first one in the sorted permutation list."
For example, the current permutation is [1,3,2] then the next permutation will be [2,1,3] this can be easily understandable as taking the current permutation as 132 then the next permutation digit is 213, which is the next greater element of 132. So, simply we need to find the next greater element of the given number’s permutation.
One way to achieve this is by generating all possible permutations of the given list. Once we have all the permutations, we can simply:
- Sort the permutations
- Identify the smallest permutation that is greater than the original permutation.
- If no such permutation exists, return the smallest permutation of the sorted permutation list i.e the first one in the permutation list.
What is Permutation?
So, what exactly are permutations?Well, think of it like arranging your favorite books on a shelf. How many different ways can you place them? That’s what permutations are—different orders of elements! For example, with three books labeled 1, 2, and 3, you can arrange them in 6 ways:123, 132, 213, 231, 312, and 321. Pretty cool, right?
Now, you might ask, “How do I generate all these different orders?” We can do it recursively by picking one book (or element), fixing it, and then permuting the rest. Keep swapping and repeating until you've covered every possible order!
Approach
Step 1: Initializing the empty list for permutations.
Step 2: Generate all possible permutations of the current permutation and store it in a list.
Step 3: Sort the list of the generated permutations in ascending order.
Step 4: Find the smallest permutation that is greater than the current permutation.
Step 5: If there is no greater permutation, return the first one in the sorted permutation list.Else return the resultant greater number.
Dry Run
Input: nums = [1,3,4,2]
Output: [1,4,2,3]
Explanation : This is the next permutation for the given permutation.
Initialization: n = [1,3,4,2] permutations = []
Generate Permutations: Generate all possible permutations of the digits: permutations = [[1, 3, 4, 2], [1, 3, 2, 4], [1, 4, 3, 2], [1, 4, 2, 3], ..., [2, 4, 1, 3], [2, 4, 3, 1]]
Sort Permutations: Sort the permutations lexicographically: sorted_permutations = [[1, 2, 3, 4], [1, 2, 4, 3], [1, 3, 2, 4], ..., [4, 3, 2, 1]]
Find the Smallest Greater Number permutation: Locate [1,3,4,2] in the sorted list:
- The number just after [1,3,4,2] in the sorted list is [1,4,2,3].
Updated list is: Output: [1,4,2,3]
Brute Force Code in all Languages
1. C++ Try on Compiler
class Solution {
private:
void generatePermutations(std::vector<int>& nums, int start, int end, std::vector<std::vector<int>>& permutations) {
if (start == end) {
permutations.push_back(nums);
return;
}
for (int i = start; i <= end; i++) {
std::swap(nums[start], nums[i]);
generatePermutations(nums, start + 1, end, permutations);
std::swap(nums[start], nums[i]);
}
}
public:
void nextPermutation(std::vector<int>& nums) {
std::vector<std::vector<int>> permutations;
generatePermutations(nums, 0, nums.size() - 1, permutations);
// Sort the permutations in lexicographical order
std::sort(permutations.begin(), permutations.end());
for (int i = 0; i < permutations.size(); i++) {
if (permutations[i] == nums) {
int x = i;
while (x + 1 < permutations.size() && permutations[x] == permutations[x + 1]) {
x++;
}
std::vector<int> nextPerm = (x + 1 < permutations.size()) ? permutations[x + 1] : permutations[0];
nums = nextPerm;
return;
}
}
}
};2. Java Try on Compiler
class Solution {
private void generatePermutations(int[] nums, int start, int end, List<int[]> permutations) {
if (start == end) {
permutations.add(Arrays.copyOf(nums, nums.length));
return;
}
for (int i = start; i <= end; i++) {
int temp = nums[start];
nums[start] = nums[i];
nums[i] = temp;
generatePermutations(nums, start + 1, end, permutations);
temp = nums[start];
nums[start] = nums[i];
nums[i] = temp;
}
}
public void nextPermutation(int[] nums) {
List<int[]> permutations = new ArrayList<>();
generatePermutations(nums, 0, nums.length - 1, permutations);
permutations.sort((a, b) -> {
for (int i = 0; i < a.length; i++) {
if (a[i] != b[i]) {
return a[i] - b[i];
}
}
return 0;
});
for (int i = 0; i < permutations.size(); i++) {
if (Arrays.equals(permutations.get(i), nums)) {
int x = i;
while (x + 1 < permutations.size() && Arrays.equals(permutations.get(x), permutations.get(x + 1))) {
x++;
}
int[] nextPerm = (x + 1 < permutations.size()) ? permutations.get(x + 1) : permutations.get(0);
System.arraycopy(nextPerm, 0, nums, 0, nums.length);
return;
}
}
}
}3. Python Try on Compiler
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Modify nums in-place to produce the next permutation using brute force.
"""
def generate_permutations(nums, start, end, permutations):
# Base case: if start equals end, add a copy of the current permutation to the list
if start == end:
permutations.append(nums[:])
return
# Iterate over all possible swaps for generating permutations
for i in range(start, end + 1):
# Swap the current element with the element at position 'start'
nums[start], nums[i] = nums[i], nums[start]
# Recur to generate permutations for the remaining elements
generate_permutations(nums, start + 1, end, permutations)
# Backtrack by swapping the elements back to their original positions
nums[start], nums[i] = nums[i], nums[start]
# Initialize a list to store all permutations of the input list
permutations = []
# Call the function to generate permutations starting from index 0
generate_permutations(nums, 0, len(nums) - 1, permutations)
# Sort all generated permutations in lexicographical order
permutations.sort()
# Iterate over the sorted permutations to find the next permutation
for i in range(len(permutations)):
# Check if the current permutation matches the input list
if permutations[i] == nums:
# If the current permutation matches, check for duplicates
x = i
while x + 1 < len(permutations) and permutations[x] == permutations[x + 1]:
x += 1
# Select the next permutation, or wrap around to the first if at the end
next_perm = permutations[x + 1] if x + 1 < len(permutations) else permutations[0]
# Update the input list in-place with the next permutation
nums[:] = next_perm
break4. JavaScript Try on Compiler
var nextPermutation = function(nums) {
// Helper function to generate permutations
function generatePermutations(nums, start, end, permutations) {
// Base case: if start equals end, add a copy of the current permutation to the list
if (start === end) {
permutations.push([...nums]); // Using spread to copy the array
return;
}
// Iterate over all possible swaps for generating permutations
for (let i = start; i <= end; i++) {
// Swap the current element with the element at position 'start'
[nums[start], nums[i]] = [nums[i], nums[start]]; // Swap using destructuring
// Recur to generate permutations for the remaining elements
generatePermutations(nums, start + 1, end, permutations);
// Backtrack by swapping the elements back to their original positions
[nums[start], nums[i]] = [nums[i], nums[start]];
}
}
// Initialize a list to store all permutations of the input list
let permutations = [];
// Call the function to generate permutations starting from index 0
generatePermutations(nums, 0, nums.length - 1, permutations);
// Sort all generated permutations in lexicographical order
permutations.sort((a, b) => {
for (let i = 0; i < a.length; i++) {
if (a[i] !== b[i]) {
return a[i] - b[i];
}
}
return 0;
});
// Iterate over the sorted permutations to find the next permutation
for (let i = 0; i < permutations.length; i++) {
// Check if the current permutation matches the input list
if (JSON.stringify(permutations[i]) === JSON.stringify(nums)) {
// If the current permutation matches, check for duplicates
let x = i;
while (
x + 1 < permutations.length &&
JSON.stringify(permutations[x]) === JSON.stringify(permutations[x + 1])
) {
x++;
}
// Select the next permutation, or wrap around to the first if at the end
let nextPerm = x + 1 < permutations.length ? permutations[x + 1] : permutations[0];
// Update the input list in-place with the next permutation
nums.length = 0; // Clear the original array
nums.push(...nextPerm); // Spread the next permutation into the original array
return;
}
}
};
Time Complexity: O(d!log(d!))
Generating Permutations: The code generates all d! permutations of the digits, where d is the number of digits in the list.
Sorting Permutations: Sorting d! permutations requires O(d!⋅log(d!)).
Finding the Next Greater Number: Iterating through the sorted list adds O(d!).
Total Time Complexity: O(d!) + O(d!⋅log(d!)) ≈ O(d!log(d!))
Space Complexity: O(d!)
Auxiliary Space Complexity:Auxiliary space is the extra space or temporary space used by an algorithm apart from the input.
- Generating Permutations : The algorithm generates and stores all d! permutations of the digits, using O(d!) space, where d is the number of digits in the list.
Total space complexity
The space complexity for input array - O(d)
Auxiliary space is - O(d!)
Total space complexity - O(d) + O(d!) ≈ O(d!)
The code we see works fine for small numbers, but for larger inputs, it struggles due to generating all possible permutations, which grows as d!. Imagine millions of permutations for just 10 digits—this makes the code both slow and memory-heavy. In order to move further in the interview we have to figure out an optimal way, let’s figure it out together !!
Optimal Approach
Intuition
Alright, let’s cut down on the time and space wasted by brute-forcing through permutations. We’ve got a smarter way to find the next permutation number!
Okay, let’s take the list [5,6,3,5,4].
What will be the next permutation number for it? [5,6,4,3,5], right!!!
Okay then, take [1,2,3,4,5]. What would be the next permutation number for it? [1,2,3,5,4], right!!!
What is the next permutation number for [5,6,7,3,4,3,2,1]? [5,6,7,4,1,2,3,3], isn’t it? Check out once carefully…
Have you got any pattern or any observation from the given examples? Yeah!!
Let’s have all the examples together!!!
Number Next Permutation Number Difference
[5,6,3,5,4] [5,6,4,3,5] 354 —--> 435 [last 3 digits changed their order]
[1,2,3,4,5] [1,2,3,5,4] 45 —--->54 [Last 2 digits changed their order]
[5,6,7,3,4,3,2,1] [5,6,7,4,1,2,3,3] 34321—>41233 [similarly Last 5 digits]
If you observe the above examples carefully, the digits from the right to left, covering a certain distance, are only rearranging themselves to become the next permutation, for the given number. Hope we are on the track, buddies!!!! Big yes for this!
Okay then, let’s closely observe them. When the digits are rearranging, how are they?Let’s take the number 56354 again and make the analysis. As per the above observation, the change occurred in 354 !
If you observe carefully, rearranging 4 alone in the same place cannot make the number bigger !! Okay then, consider 54.
Rearranging 54 front and forth… Can these digits (5, 4) make the number bigger? Noooo, because 54 is already greater than 45, right? So there is no use of rearranging, right! Move forward, consider the last three digits now — 354. Be attentive, my dear! Can rearranging these digits make the number the next permutation of the original one? Yessssss… Lots of chances to make our number bigger by arranging the digits as follows — 453, 435, 534, 543.
But why not 345 or 354? Keeping 354 again as it is doesn’t make any sense, as it is already present there, right? We need the greater one than the present right, so we won’t consider the same arrangement again! Ok fine then, keeping 345 will give the previous permutation for the original value, so we don’t need it !!
At last, we have 4 arrangements which can be our next permutation for the original one. But we want the next permutation element of our original, which is slightly near to it, so what arrangement will make the number slightly near in these 4? (453, 435, 534, 543) Absolutely 435 among those 4, right!!!
Finally, we add this arrangement to the remaining list back to get the next permutation for our original permutation number, which is [5,6,4,3,5].
So from the above things, coming from right to left, if the sequence has been increasing in order, there is no use rearranging them because they are already maximized. Then, whenever the increasing order breaks — so called as a breakpoint — we have the chance to get the next permutation by rearranging the digits from right to left up to that breakpoint.
The intuition goes like this - First, we find where the digits break their increasing order from right to left. Once we spot that, we swap the identified smaller digit with the smallest larger digit from the right side.
Observe this,
[5,6,3,5,4]
3—--—> is the break point , then we swap with the smallest larger number n its right side, then the number becomes [5,6,4,5,3]
[5,6,4,5,3]
Next, we reverse the digits after the swapped position to get the smallest possible number from the remaining digits. See, why do we need to reverse the remaining elements? If you observe that after reversing we will get the smallest next greater element instead of leaving it as it is which is not the next permutation as we discussed earlier. Then the numbers after reversing the remaining elements list becomes [5,6,4,3,5].
But here’s the twist — if the digits are already in descending order (meaning no "break" is found), there’s no way to get the next permutation , it means we are at the last permutation so return the reversed list number which is only our next permutation and the first element in the sorted permutation list. So, what might be the best part? We use a two-pointer technique to find the breakpoint and reverse the digits efficiently, saving both time and space. It’s like taking a shortcut through the maze instead of wandering around aimlessly. Cool, right?
“Why not change earlier digits?” Good question! Changing earlier digits creates a much bigger jump, which we don’t want. Adjusting the breakpoint keeps the change minimal, making it the perfect starting point for our next permutation list!
Approach
Step 1: Initialize a pointer with a value of length of the list - 1
Step 2: Traverse the list from right to left to find the first index where a digit is smaller than the digit immediately to its right. This is the "breakpoint”.
Step 3: Starting from the rightmost digit, locate the smallest digit that is larger than the digit at the breakpoint.
Step 4: Swap the digit at the breakpoint with the smallest larger digit found in the previous step.
Step 5: Reverse the digits to the right of the breakpoint to form the smallest possible number greater than the original.
Dry Run
Input: [1,3,4,2]
Output : [1,4,2,3]|
Explanation : This is the next permutation for the given permutation.
Find the Breakpoint:
Start from the right:
- Compare 4 > 2 (no break).
- Compare 3 < 4 (break found at index 1).
Find the Smallest Larger Digit:
Check digits to the right of index 3 (['4', '2']).
- The smallest digit larger than 3 is 4 (at index 2).
Swap the Digits:
Swap digits[1] and digits[2]: Result: ['1', '4', '3', '2']
Reverse the Digits After the Breakpoint:
Reverse the sublist after index 1 (['3', '2']):
- Reversed sublist: [‘2’, '3']
- Updated list: ['1', '4', '2', '3']
Updated list is: Output: [1,4,2,3]
Optimal Code in all Languages
1. C++ Try on Compiler
class Solution {
public:
vector<int> nextPermutation(vector<int>& nums) {
int n = nums.size();
// Step 1: Find the first decreasing element from the right
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If no such element is found, reverse the entire array to get the smallest permutation
if (i < 0) {
reverse(nums.begin(), nums.end());
return nums;
}
// Step 2: Find the smallest element to the right of nums[i] that is larger than nums[i]
int j = n - 1;
while (j > i && nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap nums[i] and nums[j]
swap(nums[i], nums[j]);
// Step 4: Reverse the elements to the right of i to get the smallest lexicographical order
reverse(nums.begin() + i + 1, nums.end());
return nums;
}
};2. Java Try on Compiler
class Solution {
public int[] nextPermutation(int[] nums) {
int n = nums.length;
// Step 1: Find the first decreasing element from the right
int i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If no such element is found, reverse the array to get the smallest permutation
if (i < 0) {
reverse(nums, 0, n - 1);
return nums;
}
// Step 2: Find the smallest element to the right of nums[i] that is larger than nums[i]
int j = n - 1;
while (j > i && nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap nums[i] and nums[j]
swap(nums, i, j);
// Step 4: Reverse the elements to the right of i to get the smallest lexicographical order
reverse(nums, i + 1, n - 1);
return nums;
}
// Helper function to swap elements
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
// Helper function to reverse the subarray
private void reverse(int[] nums, int start, int end) {
while (start < end) {
swap(nums, start, end);
start++;
end--;
}
}
}
3. Python Try on Compiler
class Solution:
def nextPermutation(self, nums):
# Step 1: Find the first digit that is smaller than the digit next to it, from right to left
i = len(nums) - 1
while i > 0 and nums[i - 1] >= nums[i]:
i -= 1
# If no such digit is found, the number is the largest possible permutation
if i == 0:
nums.reverse() # Reverse to get the smallest permutation
return nums
# Step 2: Find the smallest digit to the right of nums[i-1] that is larger than nums[i-1]
j = len(nums) - 1
while nums[j] <= nums[i - 1]:
j -= 1
# Step 3: Swap the two digits identified in steps 1 and 2
nums[i - 1], nums[j] = nums[j], nums[i - 1]
# Step 4: Reverse the digits after the position i-1 to get the smallest number
nums[i:] = nums[i:][::-1]
return nums
4. JavaScript Try on Compiler
var nextPermutation = function (nums) {
let n = nums.length;
// Step 1: Find the first decreasing element from the right
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) {
i--;
}
// If no such element is found, return the sorted array (smallest permutation)
if (i < 0) {
nums.sort((a, b) => a - b);
return nums;
}
// Step 2: Find the smallest element to the right of nums[i] that is larger than nums[i]
let j = n - 1;
while (j > i && nums[j] <= nums[i]) {
j--;
}
// Step 3: Swap nums[i] and nums[j]
[nums[i], nums[j]] = [nums[j], nums[i]];
// Step 4: Reverse the elements to the right of i to get the smallest lexicographical order
let left = i + 1,
right = n - 1;
while (left < right) {
[nums[left], nums[right]] = [nums[right], nums[left]];
left++;
right--;
}
return nums;
};
Time Complexity: O(d)
Traversing: We traverse the list to find the break point and the smallest larger digit.So at most we travel the whole array - O(d).
Reversing : We reverse the sublist after the swap, at most we reverse the whole array using pointers is - O(d/2).Here, d is the length of the given permutation(nums)
Thus, the overall time complexity is O(d) + O(d/2) ≈ O(d).
Space Complexity: O(1)
Auxiliary Space Complexity: - Auxiliary space is the extra space or temporary space used by an algorithm apart from the input.
- Traversing: We use a pointer for traversing - O(1)
Total space complexity
Space for input array of current permutation- O(d)
Auxiliary space for pointer - O(1)
Total space complexity - O(d) + O(1) ≈ O(d)
Here, d is the length of the given permutation(nums)
Learning Tip
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.