Next Permutation

Q: What is the time complexity of Next Permutation?

O(n) . One scan from the right finds the pivot, a second finds the value to swap with, and one reversal fixes the suffix. The extra memory is O(1) , since everything happens inside the array.

MediumArrays and strings Two pointers

+10

You get an array of integers nums, and values may repeat. Picture every distinct arrangement of these values, sorted in dictionary order: compare two arrangements at the first index where they differ, and the one with the smaller value there comes first. Return the arrangement that comes right after nums in that order.

If nums is already the largest arrangement, there is none after it: return the smallest one, which is the values sorted in increasing order. Aim for O(n) time and O(1) extra memory.

Function

nextPermutation(nums: integer-array) → integer-array

numsinteger-array: the current arrangement of values
Returnsinteger-array: the next arrangement in dictionary order, or the values sorted in increasing order if nums is the largest

Constraints

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Examples

Input: nums = [2, 5, 4, 1]
Output: [4, 1, 2, 5]
Explanation: The tail 5, 4, 1 is falling, so the 2 in front of it must grow. The smallest tail value above 2 is 4; put it there and the rest in increasing order: [4, 1, 2, 5].

Input: nums = [3, 2, 2, 1]
Output: [1, 2, 2, 3]
Explanation: The whole array is falling, so it is the largest arrangement of 3, 2, 2 and 1. The answer wraps around to the smallest one, [1, 2, 2, 3].

Input: nums = [1, 5, 1]
Output: [5, 1, 1]
Explanation: The first 1 must grow. The last 1 is equal to it, not larger, so the only value that can take its place is 5, which gives [5, 1, 1].

Follow-up

How would you find the previous arrangement instead, the one that comes right before nums in dictionary order?

Solution

A falling suffix is already as large as its values allow, so the next arrangement changes the value right before it, the pivot. Raise the pivot by the smallest possible amount, then make the suffix as small as possible. That takes two scans from the right and one reversal, inside the array.

List arrangements in order

Correct, but does not finish on the largest tests

Intuition

Build arrangements depth first from the sorted values, always trying the smallest unused value first. That produces them in dictionary order, so the first one strictly greater than nums is the answer; if none is, return the sorted values. Repeated values build some arrangements twice, as in 115, 151, 115, 151, 511, 511 for [1, 1, 5], but a copy only repeats one built earlier, so the first greater one is still the next.

The count grows as n!: 12 distinct values have 479,001,600 arrangements.

Algorithm

Sort a copy of nums into pool.
Build arrangements depth first, choosing unused entries of pool from left to right.
When an arrangement is complete, compare it with nums position by position.
Return the first arrangement that is greater than nums.
If none is greater, return pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Find the pivot, swap, reverse the suffix

Intuition

The pivot is the first value from the right that is smaller than its right neighbour: the 2 in [2, 5, 4, 1]. It is the rightmost position that can grow, and growing the rightmost position possible keeps the increase smallest.

Swap the pivot with the smallest suffix value that is strictly larger. The suffix is falling, so that is the rightmost value larger than the pivot: 4, giving [4, 5, 2, 1]. The suffix still falls, because the old pivot fits where 4 was. With the front now larger, the suffix should be as small as possible, in increasing order, and reversing a falling run does that: [4, 1, 2, 5].

With no pivot the array is the largest arrangement, and reversing all of it gives the smallest. Each step is one scan or one reversal: O(n) time and O(1) memory, though the R version returns an O(n) copy.

Algorithm

Set i to n-2 and move it left while nums[i] ≥ nums[i + 1].
If i ≥ 0, set j to n-1 and move it left while nums[j] ≤ nums[i], then swap nums[i] and nums[j].
Reverse the part from i + 1 to the end with two indices walking toward each other.
Return nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Pitfalls and edge cases

Using > instead of ≥ in the pivot search. In [3, 2, 2, 1] the pair 2, 2 is not a rise, and stopping there picks a pivot that cannot grow.
Swapping with a value equal to the pivot. In [1, 5, 1] swapping the two 1s changes nothing; search for a value strictly larger.
Swapping with the largest suffix value. In [2, 5, 4, 1] that puts 5 in front and skips every arrangement starting with 4.
Skipping the no-pivot case. The largest arrangement must come back sorted, by reversing the whole array.
In Rust, a usize index starting at n-2 panics when n = 1, and stepping left past 0 panics when there is no pivot. Use a signed index or count from 1.

Frequently asked questions3

What is the time complexity of Next Permutation?

O(n). One scan from the right finds the pivot, a second finds the value to swap with, and one reversal fixes the suffix. The extra memory is O(1), since everything happens inside the array.

Why do you reverse the suffix instead of sorting it?

After the swap the suffix is still falling, so reversing it already sorts it in increasing order. A reversal takes O(n); a sort gives the same result in O(n log n).

Does Next Permutation work with duplicate values?

Yes, as long as both comparisons treat equal values as not larger. The pivot search skips equal neighbours with ≥, and the swap search skips values equal to the pivot with ≤. Then [1, 5, 1] becomes [5, 1, 1], the next distinct arrangement.

def nextPermutation(nums):
    # Write code here

Test #1

Test #2

Test #3

Argument

nums = [2, 5, 4, 1]

Expected Output

[4, 1, 2, 5]