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:

1. 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.

2. 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).

3. 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.

4. 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:

1. Traverse to Find the Pivot: We start by traversing the array from the end to the beginning. We look for the first index i where nums[i] < nums[i + 1]. This step locates the longest non-increasing suffix, and i is identified as the pivot. This is completed in O(n) time complexity, where n is the length of the array.

2. 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 where nums[j] > nums[i]. The element at j is the smallest element greater than the pivot within the suffix. This step ensures we get the next permutation.

3. Swap the Pivot and its Successor: We swap the elements at i and j. Now, the pivot is at the place of its immediate successor which is the minimum necessary increment to the current permutation.

4. 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.

5. 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:

1def nextPermutation(self, nums: List[int]) -> None:
2    n = len(nums)
3    # Finding the pivot using a generator expression.
4    # The default value -1 is used if no pivot is found.
5    i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
6  
7    # If a pivot is found (i is not -1 after applying ~ operator)
8    if ~i:
9        # Finding the successor to pivot (nums[j] > nums[i]).
10        j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
11        # Swap pivot with its successor.
12        nums[i], nums[j] = nums[j], nums[i]
13      
14    # Reverse the suffix. This is done in place, and Python's slicing is used.
15    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.

Example 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:

1. 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 index 1.

2. 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 is 4 at index 3.

3. Swap the Pivot and its Successor: We swap 3 and 4. The array is now: [1, 4, 5, 3, 2].

4. 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

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:

1. 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 takes O(n) time, where n is the size of the nums list.

2. If such an i is found (i.e., the permutation is not the last one), the code looks for the smallest number greater than nums[i] after the index i, and swaps nums[i] with nums[j]. This operation is also O(n) since in the worst case it might scan all elements to the left of j.

3. The last line reverses the segment of the list after the ith index. This operation has a complexity of O(n), since reversing a list is linear in the length of the segment being reversed.

4. 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.