Problem Description

This problem asks you to find the next permutation of an array in lexicographical order.

A permutation is a rearrangement of all elements in an array. For example, [1,2,3] has 6 permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

The next permutation means finding the permutation that would come immediately after the current one if all permutations were sorted in lexicographical (dictionary) order. Think of it like finding the next word in a dictionary.

For example:

• The next permutation of [1,2,3] is [1,3,2]
• The next permutation of [2,3,1] is [3,1,2]
• The next permutation of [3,2,1] (the largest possible) wraps around to [1,2,3] (the smallest possible)

The key insight is to identify where to make the smallest possible change that results in a larger permutation:

1. Find the pivot: Scan from right to left to find the first pair where nums[i] < nums[i+1]. This i is where we need to make a change.

2. Find the swap element: From the right side, find the smallest element that is still larger than nums[i]. This will be nums[j].

3. Swap and reverse: After swapping nums[i] and nums[j], reverse all elements after position i to get the smallest permutation that is still larger than the original.

If no such i exists (the array is in descending order), the array is already the largest permutation, so we reverse the entire array to get the smallest permutation.

The solution must modify the array in-place using only constant extra memory.

Intuition

To understand how to find the next permutation, let's think about how numbers work. When counting (123, 124, 125...), we increment from the rightmost position. When we can't increment anymore (like 129), we move to the next position left and reset everything to the right (130).

The same principle applies here. We want to find the rightmost position where we can make the array "larger" while keeping the change as small as possible.

Consider the array [1, 3, 5, 4, 2]. Reading from right to left: 2 < 4 < 5, but then 5 > 3. This tells us that the suffix [5, 4, 2] is already in descending order - it's the largest possible arrangement of these three numbers. We can't make the permutation larger by just rearranging this suffix.

The position where the descending pattern breaks (at index i where nums[i] = 3) is our pivot point. This is where we need to put a larger number to create the next permutation.

But which number should replace nums[i]? We need the smallest number from the right side that's still larger than nums[i]. Why? Because we want the very next permutation, not just any larger one. In our example, from [5, 4, 2], the smallest number greater than 3 is 4.

After swapping to get [1, 4, 5, 3, 2], notice that the suffix [5, 3, 2] is still in descending order. Since we want the smallest permutation that starts with [1, 4, ...], we should arrange the remaining numbers in ascending order. The quickest way to convert a descending sequence to ascending is to simply reverse it.

This gives us [1, 4, 2, 3, 5] - the next permutation!

The special case is when the entire array is in descending order (like [5, 4, 3, 2, 1]). This means we're already at the largest possible permutation, so we "wrap around" to the smallest by reversing the entire array to get [1, 2, 3, 4, 5].

Learn more about Two Pointers patterns.

Solution Approach

The implementation follows a two-traversal approach to find and create the next permutation:

Step 1: Find the pivot point (first traversal)

We traverse the array from right to left, looking for the first position i where nums[i] < nums[i + 1]. This identifies where the descending suffix ends.

i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)

This uses Python's next() function with a generator expression to find the first i that satisfies our condition. If no such position exists, it returns -1, meaning the entire array is in descending order.

Step 2: Find the swap element (second traversal)

If we found a valid pivot (i != -1), we traverse from right to left again to find the first position j where nums[j] > nums[i]. This gives us the smallest element in the suffix that's larger than our pivot.

if ~i:  # This checks if i != -1 using bitwise NOT
    j = next((j for j in range(n - 1, i, -1) if nums[j] > nums[i]))
    nums[i], nums[j] = nums[j], nums[i]

The condition ~i is a clever way to check if i != -1. The bitwise NOT of -1 is 0 (False), while the bitwise NOT of any other negative or non-negative number is non-zero (True).

Step 3: Reverse the suffix

After the swap (or if no pivot was found), we reverse all elements from position i + 1 to the end:

nums[i + 1 :] = nums[i + 1 :][::-1]

This works for both cases:

• If we found a pivot and swapped, this reverses the descending suffix to make it ascending, giving us the smallest arrangement
• If no pivot was found (i = -1), then i + 1 = 0, so this reverses the entire array, wrapping around from the largest to the smallest permutation

The beauty of this solution is that it modifies the array in-place and uses only O(1) extra space (just the variables i and j), while achieving O(n) time complexity with at most two passes through the array.

Example Walkthrough

Let's walk through finding the next permutation of [1, 5, 8, 4, 7, 6, 5, 3, 1].

Step 1: Find the pivot point

We scan from right to left looking for the first pair where nums[i] < nums[i+1]:

• Position 8: 1 < 3? No (1 < 3 is true, but we need nums[8] < nums[7])
• Position 7: 3 < 5? No
• Position 6: 5 < 6? No
• Position 5: 6 < 7? No
• Position 4: 7 < 4? No
• Position 3: 4 < 8? No
• Position 2: 8 < 5? No
• Position 1: 5 < 1? No
• Wait, let me recalculate...
• Position 7: nums[7]=3, nums[8]=1, so 3 < 1? No
• Position 6: nums[6]=5, nums[7]=3, so 5 < 3? No
• Position 5: nums[5]=6, nums[6]=5, so 6 < 5? No
• Position 4: nums[4]=7, nums[5]=6, so 7 < 6? No
• Position 3: nums[3]=4, nums[4]=7, so 4 < 7? Yes!

Found pivot at i = 3 where nums[3] = 4.

Step 2: Find the swap element

Now we scan from the right to find the smallest element larger than 4:

• Position 8: nums[8]=1, is 1 > 4? No
• Position 7: nums[7]=3, is 3 > 4? No
• Position 6: nums[6]=5, is 5 > 4? Yes!

Found swap position at j = 6 where nums[6] = 5.

Step 3: Swap pivot and swap element

Swap nums[3] and nums[6]:

• Before: [1, 5, 8, 4, 7, 6, 5, 3, 1]
• After: [1, 5, 8, 5, 7, 6, 4, 3, 1]

Step 4: Reverse the suffix

Reverse everything after position 3 (from index 4 to end):

• Before reversal: suffix is [7, 6, 4, 3, 1]
• After reversal: suffix becomes [1, 3, 4, 6, 7]

Final Result: [1, 5, 8, 5, 1, 3, 4, 6, 7]

This is the next permutation because:

• We made the smallest possible increase at position 3 (changed 4 to 5)
• We arranged all elements after position 3 in ascending order to get the smallest permutation that starts with [1, 5, 8, 5, ...]

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm consists of three main operations:

1. Finding the rightmost ascending pair: The first next() function iterates from right to left through the array once in the worst case, taking O(n) time.
2. Finding the smallest element greater than nums[i]: The second next() function iterates from right to left starting from the end of the array, taking at most O(n) time.
3. Reversing the suffix: The slice reversal nums[i + 1:][::-1] creates a reversed copy and assigns it back, which takes O(n) time in the worst case.

Since these operations are performed sequentially, the overall time complexity is O(n) + O(n) + O(n) = O(n).

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space:

• Variables i, j, and n each use O(1) space
• The swap operation nums[i], nums[j] = nums[j], nums[i] uses O(1) temporary space
• The slice reversal nums[i + 1:][::-1] appears to create a temporary reversed copy, but since it's immediately assigned back to the same slice, Python optimizes this to use O(1) extra space for in-place modification

Therefore, the overall space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Finding the Swap Element

A common mistake is to swap the pivot with the first element from the right that is greater than it, without considering that we need the rightmost such element. Since the suffix after the pivot is in descending order, the rightmost element greater than the pivot is actually the smallest element that's still larger than the pivot.

Incorrect approach:

# Wrong: Breaking too early or searching from the wrong direction
for j in range(pivot_index + 1, n):  # Searching from left to right
    if nums[j] > nums[pivot_index]:
        swap_index = j
        break  # This might not give us the smallest valid element

Correct approach:

# Right: Search from right to left to find the first (rightmost) element > pivot
for j in range(n - 1, pivot_index, -1):
    if nums[j] > nums[pivot_index]:
        swap_index = j
        break  # This guarantees the smallest element greater than pivot

2. Off-by-One Errors in Index Boundaries

When searching for the pivot or performing the reversal, it's easy to make index boundary mistakes.

Common mistakes:

• Starting the pivot search from n - 1 instead of n - 2 (you need to compare pairs)
• Using wrong boundaries when reversing: forgetting that pivot_index + 1 could be 0 when pivot_index = -1
• Incorrectly handling the case when the entire array needs to be reversed

Solution: Always verify your loop boundaries with small test cases like [1], [1,2], and [3,2,1].

3. Not Handling Edge Cases Properly

Edge cases that are often missed:

• Single element array: [1] should remain [1]
• Already largest permutation: [3,2,1] should become [1,2,3]
• Duplicate elements: [1,1,5] should become [1,5,1]

Solution: Ensure your algorithm handles:

if n <= 1:  # Arrays with 0 or 1 element don't need processing
    return

4. Using Complex One-Liners That Obscure Logic

While the original solution's use of next() with generator expressions and bitwise NOT (~i) is clever, it can lead to bugs and maintenance issues:

# Hard to debug and understand:
i = next((i for i in range(n - 2, -1, -1) if nums[i] < nums[i + 1]), -1)
if ~i:  # What does ~i mean? It's checking if i != -1

Better approach for clarity:

# Clear and maintainable:
pivot_index = -1
for i in range(n - 2, -1, -1):
    if nums[i] < nums[i + 1]:
        pivot_index = i
        break

if pivot_index != -1:  # Explicit and clear

5. Inefficient Reversal Implementation

Using slicing for reversal like nums[i + 1:] = nums[i + 1:][::-1] creates a temporary copy, which technically violates the O(1) space requirement in strict terms.

Better approach using two pointers:

# True O(1) space reversal
left = pivot_index + 1
right = n - 1
while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

This ensures true in-place modification without any temporary arrays.