31. Next Permutation
Problem Description
The problem asks us to find the next permutation of an array of integers in lexicographical order. A permutation refers to arranging the integers in a different sequence. If we consider all possible permutations of an array sorted in lexicographical order (dictionary order), the 'next permutation' is the permutation that comes directly after the current one in this sorted list. The challenge here is to generate this next permutation efficiently, using constant extra space (in-place).
If the array is sorted in descending order, there is no next permutation, and the array should be rearranged to its lowest possible order (ascending order). We need to identify a method for transforming the arrangement of the array to the next permutation without generating all permutations.
For example, given nums = [1,2,3]
, the next permutation is [1,3,2]
. Given nums = [3,2,1]
, as it's the last permutation in lexicographical order, the next permutation would reset to [1,2,3]
.
Intuition
To find the next permutation, we need to understand how permutations can be ordered lexicographically. We must identify the smallest change in the sequence that leads to a larger permutation. The process of finding the next permutation can typically be broken down into the following steps:
-
Find the Longest Decreasing Suffix: We traverse from the end of the array moving backward, looking for the first pair of elements where the previous element is smaller than the next one (nums[i] < nums[i+1]). This identifies the boundary of the longest decreasing (non-increasing) suffix of the array.
-
Identify the Pivot: The element just before the non-increasing suffix is called the pivot. If no pivot is found, it implies the entire array is non-increasing, which means we are at the last permutation and the next one is the first permutation (sorted in ascending order).
-
Find a Successor to the Pivot: We again traverse from the end of the array moving backward, looking for the first element larger than the pivot. This successor will be the one we swap with the pivot to ensure we get the next larger permutation.
-
Perform the Swap and Reverse the Suffix: As the suffix is in decreasing order, to get the next permutation, we swap the pivot with its successor and then reverse the suffix, turning it from decreasing to increasing, which gives us the least increase necessary to form the next permutation.
The intuition behind this approach is that we want to increase the sequence as little as possible - only enough to make it the ānextā permutation lexicographically. Swapping the pivot with the smallest element larger than it in the decreasing suffix ensures this minimal increase. Reversing the decreasing suffix guarantees that the sequence remains as small as possible after the pivot.
Learn more about Two Pointers patterns.
Solution Approach
The solution involves a carefully crafted algorithm, which includes identifying key positions in the array and manipulating it using basic operations like swapping elements and reversing a sub-array. Here's a step-by-step walk-through:
-
Traverse to Find the Pivot: We start by traversing the array from the end to the beginning. We look for the first index
i
wherenums[i] < nums[i + 1]
. This step locates the longest non-increasing suffix, andi
is identified as the pivot. This is completed inO(n)
time complexity, wheren
is the length of the array. -
Find the Successor to the Pivot: If a pivot is found (the array is not entirely non-increasing), we again traverse the array from the end to find the first index
j
wherenums[j] > nums[i]
. The element atj
is the smallest element greater than the pivot within the suffix. This step ensures we get the next permutation. -
Swap the Pivot and its Successor: We swap the elements at
i
andj
. Now, the pivot is at the place of its immediate successor which is the minimum necessary increment to the current permutation. -
Reverse the Suffix: Finally, the suffix starting from
i+1
till the end of the array is reversed. Since the suffix was in a non-increasing order, reversing it will change it to non-decreasing order. This ensures the remainder of the array is as low as possible to be the next permutation after the incremented pivot. -
In-Place and Constant Space: The entire operation does not need any additional storage as all operations are performed on the input array itself. The space complexity is
O(1)
since no additional space is required regardless of the input size.
The provided solution uses Python's generator expressions and the tilde operator (~
) for a concise implementation. Here is the detailed approach referring to the provided code:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
# Finding the pivot using a generator expression.
# The default value -1 is used if no pivot is found.
i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
# If a pivot is found (i is not -1 after applying ~ operator)
if ~i:
# Finding the successor to pivot (nums[j] > nums[i]).
j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
# Swap pivot with its successor.
nums[i], nums[j] = nums[j], nums[i]
# Reverse the suffix. This is done in place, and Python's slicing is used.
nums[i + 1 :] = nums[i + 1 :][::-1]
Here the next
method is used from Python's built-in functionality, which returns the next item from the iterator. If the iterator is exhausted, a default value is returned (in this case, -1
). By using a generator expression within the next
method, we effectively condense the loop to find the pivot and successor in a single line each. The ~
operator is a bitwise complement operator, which, when applied to -1
, results in 0
, thereby allowing us to check if i
is not -1
in a concise manner.
Understanding this algorithm's steps and carefully executing them in the correct order are crucial to finding the next permutation effectively.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Consider the following array of integers:
nums = [1, 3, 5, 4, 2]
We want to find the next permutation for this array in lexicographical order. Following the steps mentioned in the solution approach:
-
Traverse to Find the Pivot: We start from the end of the array and look for the first pair where the number is less than its successor. Traverse: 2 < 4 (stop here). So, the pivot is
3
at index1
. -
Find the Successor to the Pivot: We need to find the smallest number greater than the pivot
3
, starting from the end of the array. Traverse: 2 (not greater), 4 (greater, stop here). The successor is4
at index3
. -
Swap the Pivot and its Successor: We swap
3
and4
. The array is now:[1, 4, 5, 3, 2]
. -
Reverse the Suffix: We reverse the suffix starting right after the pivot's new position (index
1
) till the end. The suffix is[5, 3, 2]
and its reverse is[2, 3, 5]
. The array after reversing the suffix is:[1, 4, 2, 3, 5]
.
The resulting array [1, 4, 2, 3, 5]
is the next permutation of the input array [1, 3, 5, 4, 2]
.
By performing these steps, we successfully found the next permutation in lexicographical order using constant space and without the need to generate all permutations.
Solution Implementation
1class Solution:
2 def nextPermutation(self, nums: List[int]) -> None:
3 # The length of the 'nums' list
4 length = len(nums)
5
6 # First, find the first element from the right that is smaller than the element next to it.
7 pivot = -1
8 for i in range(length - 2, -1, -1):
9 if nums[i] < nums[i + 1]:
10 pivot = i
11 break
12
13 # If such an element was found, then we can form the next permutation
14 if pivot != -1:
15 # Now, we find the smallest element greater than the 'pivot', starting from the end
16 for j in range(length - 1, pivot, -1):
17 if nums[j] > nums[pivot]:
18 # Swap the 'pivot' with this element
19 nums[pivot], nums[j] = nums[j], nums[pivot]
20 break
21
22 # Finally, reverse the elements following the 'pivot' (inclusive if pivot is -1)
23 # to get the lowest possible sequence with the 'pivot' being the prefix
24 nums[pivot + 1:] = reversed(nums[pivot + 1:])
25
26 # This mutates 'nums' in-place to the next permutation
27
1class Solution {
2 public void nextPermutation(int[] nums) {
3 // Length of the array
4 int length = nums.length;
5 // Initialize the index i to start from the second last element
6 int i = length - 2;
7
8 // Find the first pair of two successive numbers a[i] and a[i+1], from right to left, which satisfy a[i] < a[i+1]
9 while (i >= 0 && nums[i] >= nums[i + 1]) {
10 i--;
11 }
12
13 // If such pair was found, i denotes the pivot
14 if (i >= 0) {
15 // Find the rightmost successor to the pivot
16 for (int j = length - 1; j > i; j--) {
17 if (nums[j] > nums[i]) {
18 // Swap the successor and the pivot
19 swap(nums, i, j);
20 break;
21 }
22 }
23 }
24
25 // Reverse the suffix starting right after the pivot point
26 int start = i + 1, end = length - 1;
27 while (start < end) {
28 // Swap the start and end elements of the suffix
29 swap(nums, start, end);
30 start++;
31 end--;
32 }
33 }
34
35 // Helper function to swap elements in the array
36 private void swap(int[] nums, int i, int j) {
37 int temp = nums[i];
38 nums[i] = nums[j];
39 nums[j] = temp;
40 }
41}
42
1#include <vector>
2#include <algorithm> // For std::reverse
3
4class Solution {
5public:
6 // Rearranges numbers into the lexicographically next greater permutation
7 void nextPermutation(std::vector<int>& nums) {
8 int n = nums.size(); // Size of the given array
9 int i = n - 2; // Start from the second last element
10
11 // Find the first element that is not in a non-increasing sequence from the end
12 while (i >= 0 && nums[i] >= nums[i + 1]) {
13 --i;
14 }
15
16 if (i >= 0) { // If such an element is found
17 // Find the smallest element greater than nums[i] to the right of it
18 for (int j = n - 1; j > i; --j) {
19 if (nums[j] > nums[i]) {
20 std::swap(nums[i], nums[j]); // Swap them
21 break;
22 }
23 }
24 }
25
26 // Reverse the sequence from nums[i + 1] to the end of the array
27 // This is to get the smallest possible permutation after i
28 std::reverse(nums.begin() + i + 1, nums.end());
29 }
30};
31
1/**
2 * Rearranges numbers into the lexicographically next greater permutation of numbers.
3 * If such arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
4 * Modifies the array in place.
5 * @param {number[]} nums - An array of integers to find the next permutation for.
6 */
7function nextPermutation(nums: number[]): void {
8 // Get the length of the numbers array.
9 const length = nums.length;
10 // Start from the second last element and move backwards to find the first pair where the left index is less than the right index.
11 let pivotIndex = length - 2;
12 while (pivotIndex >= 0 && nums[pivotIndex] >= nums[pivotIndex + 1]) {
13 pivotIndex--;
14 }
15 // If such pair is found, find the number just larger than the pivot to swap with.
16 if (pivotIndex >= 0) {
17 for (let swapIndex = length - 1; swapIndex > pivotIndex; swapIndex--) {
18 if (nums[swapIndex] > nums[pivotIndex]) {
19 // Swap the pivot with the number just larger than it.
20 [nums[pivotIndex], nums[swapIndex]] = [nums[swapIndex], nums[pivotIndex]];
21 break;
22 }
23 }
24 }
25 // Reverse the numbers to the right of pivotIndex to get the next smallest lexicographic permutation.
26 let start = pivotIndex + 1;
27 let end = length - 1;
28 while (start < end) {
29 [nums[start], nums[end]] = [nums[end], nums[start]];
30 start++;
31 end--;
32 }
33}
34
Time and Space Complexity
The function nextPermutation
manipulates an array nums
to transform it into the next permutation in lexicographically increasing order. Analyzing the code block by block:
-
i
is found by iterating backwards, starting from the second to last element, to find the first number that is smaller than the one directly after it. In the worst case, this takesO(n)
time, wheren
is the size of thenums
list. -
If such an
i
is found (i.e., the permutation is not the last one), the code looks for the smallest number greater thannums[i]
after the indexi
, and swapsnums[i]
withnums[j]
. This operation is alsoO(n)
since in the worst case it might scan all elements to the left ofj
. -
The last line reverses the segment of the list after the
i
th index. This operation has a complexity ofO(n)
, since reversing a list is linear in the length of the segment being reversed. -
There are no additional data structures that depend on the size of the input, so the space complexity remains constant, i.e.,
O(1)
.
In summary, even though there are multiple sequential O(n)
operations, the overall time complexity is still O(n)
because we do not perform these operations more than once for the entire input. Therefore, the reference answer's claim of O(n)
time complexity and O(1)
space complexity is correct.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!