LeetCode 31: Next Permutation

Problem Restatement

We are given an integer array nums.

We need to rearrange it into the next lexicographically greater permutation.

If no greater permutation exists, we rearrange it into the smallest possible permutation, which is ascending order.

The replacement must be done in place and must use only constant extra memory. The constraints are 1 <= nums.length <= 100 and 0 <= nums[i] <= 100.

Input and Output

Function shape:

def nextPermutation(nums: list[int]) -> None:
    ...

Examples

Example 1:

nums = [1, 2, 3]

All permutations in sorted order are:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

The next permutation after [1, 2, 3] is:

[1, 3, 2]

Example 2:

nums = [3, 2, 1]

This is already the largest permutation.

So we wrap around to the smallest permutation:

[1, 2, 3]

Example 3:

nums = [1, 1, 5]

The next permutation is:

[1, 5, 1]

First Thought: Generate All Permutations

A direct approach is:

1. Generate every permutation of nums.
2. Sort all permutations lexicographically.
3. Find the current permutation.
4. Return the next one.

This works conceptually, but it is far too expensive.

For an array of length n, there can be n! permutations.

Even for n = 10, this is already millions of permutations.

We need to compute the next permutation directly.

Key Insight

To get the next permutation, we want the smallest possible increase.

That means we should change the array as far to the right as possible.

Consider:

nums = [1, 3, 5, 4, 2]

Look at the suffix:

[5, 4, 2]

This suffix is descending.

A descending suffix is already the largest possible arrangement of those elements.

So we cannot make the array larger by only rearranging [5, 4, 2].

We need to change the element just before that suffix:

[1, 3, 5, 4, 2]
    ^

The pivot is 3.

To make the next permutation, we replace 3 with the smallest number in the suffix that is larger than 3.

The suffix has:

[5, 4, 2]

The numbers larger than 3 are 5 and 4.

The smallest larger value is 4.

Swap 3 and 4:

[1, 4, 5, 3, 2]

Now the prefix [1, 4] is fixed. To make the whole array as small as possible after this increase, sort the suffix ascending:

[1, 4, 2, 3, 5]

Because the suffix was descending before the swap, we can reverse it instead of sorting it.

Algorithm

Scan from right to left and find the first index i such that:

nums[i] < nums[i + 1]

This index is the pivot.

If no such index exists, the whole array is descending. That means it is already the largest permutation. Reverse the whole array and stop.

Otherwise, scan from right to left again and find the first index j such that:

nums[j] > nums[i]

Swap nums[i] and nums[j].

Then reverse the suffix starting at i + 1.

Correctness

The scan from right to left finds the first place where the descending suffix begins. Everything after index i is in non-increasing order, so that suffix is the largest possible arrangement of those suffix elements.

To get a greater permutation, we must increase some position. Choosing the rightmost possible pivot i gives the smallest change to the prefix.

After choosing i, we need to replace nums[i] with the smallest value in the suffix that is larger than it. Since the suffix is non-increasing, scanning from the right finds exactly that value.

After the swap, the prefix becomes slightly larger than before. To make the full permutation as small as possible with that new prefix, the suffix must be arranged in ascending order.

The suffix after the swap is still in non-increasing order, so reversing it gives ascending order.

Therefore, the algorithm produces the smallest permutation that is greater than the original. If no pivot exists, the original array is the largest permutation, so reversing it gives the smallest permutation.

Complexity

Implementation

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        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 = i + 1
        right = n - 1

        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Code Explanation

Start from the second-to-last index:

i = n - 2

We move left while the array is descending from that point:

while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1

When the loop stops, either i == -1, or nums[i] < nums[i + 1].

If i >= 0, we found a pivot.

if i >= 0:

Then we find the rightmost element larger than the pivot:

j = n - 1
while nums[j] <= nums[i]:
    j -= 1

Swap the pivot with that element:

nums[i], nums[j] = nums[j], nums[i]

Finally, reverse the suffix after the pivot:

left = i + 1
right = n - 1

while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

If i == -1, this reverses the whole array, which handles the descending case.

Testing

def check(nums: list[int], expected: list[int]) -> None:
    original = nums[:]
    Solution().nextPermutation(nums)
    assert nums == expected, (original, nums, expected)

def run_tests():
    check([1, 2, 3], [1, 3, 2])
    check([3, 2, 1], [1, 2, 3])
    check([1, 1, 5], [1, 5, 1])
    check([1], [1])
    check([1, 3, 5, 4, 2], [1, 4, 2, 3, 5])
    check([2, 3, 1], [3, 1, 2])
    check([1, 5, 1], [5, 1, 1])
    check([2, 2, 7, 5, 4, 3, 2, 2, 1], [2, 3, 1, 2, 2, 2, 4, 5, 7])

    print("all tests passed")

run_tests()

Test meaning: