{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Next Permutation – Solution & Complexity

Interview solutions
/
Next Permutation

Solution Walkthrough

  1. Step 1: Understand the lexicographic rule

    • A permutation is "next" only if it is larger than the current one but as small as possible among all larger permutations.
    • That means we must change the array as far to the right as possible, then keep the suffix minimal.

  2. Step 2: Brute-force by rebuilding the suffix

    • Scan pivot positions from right to left.
    • For the first pivot that has a larger value somewhere to its right, swap in the smallest larger value and then sort the suffix.
    • This is correct, but the explicit suffix sort costs extra work.
    def next_permutation(nums: list[int]) -> list[int]:
    arr = nums[:]
    for pivot in range(len(arr) - 2, -1, -1):
        larger = [value for value in arr[pivot + 1:] if value > arr[pivot]]
        if not larger:
            continue
        swap_value = min(larger)
        swap_index = len(arr) - 1
        while arr[swap_index] != swap_value:
            swap_index -= 1
        arr[pivot], arr[swap_index] = arr[swap_index], arr[pivot]
        arr[pivot + 1:] = sorted(arr[pivot + 1:])
        return arr
    return sorted(arr)

  3. Step 3: Exploit the descending suffix

    • The first index from the right where nums[i] < nums[i + 1] is the pivot.
    • Everything to its right is already in descending order, so once we swap in the next-larger value, reversing that suffix makes it as small as possible.

  4. Step 4: Build the optimal O(n) transformation

    • Find the pivot from the right.
    • Find the first value from the right that is larger than the pivot and swap them.
    • Reverse the suffix in place instead of sorting it.
    def next_permutation(nums: list[int]) -> list[int]:
    arr = nums[:]
    pivot = len(arr) - 2
    while pivot >= 0 and arr[pivot] >= arr[pivot + 1]:
        pivot -= 1
    if pivot >= 0:
        swap_index = len(arr) - 1
        while arr[swap_index] <= arr[pivot]:
            swap_index -= 1
        arr[pivot], arr[swap_index] = arr[swap_index], arr[pivot]
    arr[pivot + 1:] = reversed(arr[pivot + 1:])
    return arr

  5. Step 5: Dry run / state trace

    Trace nums = [1,2,3,6,5,4].

    stepstateexplanation
    find pivot[1,2,3,6,5,4]scan from the right; 3 < 6, so pivot index is 2
    find swap[1,2,3,6,5,4]the first value from the right larger than 3 is 4
    swap[1,2,4,6,5,3]now the prefix is the next-larger prefix
    reverse suffix[1,2,4,3,5,6]the suffix was descending, so reversing it makes it minimal

  6. Step 6: Common mistakes and follow-ups

    • Sorting the whole array after the swap, which is correct but slower than necessary.
    • Picking a larger suffix value that is not the smallest possible larger value.
    • Forgetting the "already highest permutation" case, which should wrap to ascending order.
    • Follow-up: how would you do the in-place mutation-only LeetCode version if the function returned void?

  7. Step 7: Edge cases to test mentally

    • Single-element arrays stay unchanged.
    • Arrays with all equal values also stay unchanged.
    • A fully descending array should wrap to ascending order.
    • Duplicates in the suffix still work because we swap with the rightmost value that is just large enough.

  8. Step 8: Final full solution and complexity

    Find the pivot, swap with the next-larger value from the right, then reverse the descending suffix. This runs in O(n) time and uses O(n) output space here only because we return a new array rather than mutating the caller-owned one.

    def next_permutation(nums: list[int]) -> list[int]:
    arr = nums[:]
    pivot = len(arr) - 2
    while pivot >= 0 and arr[pivot] >= arr[pivot + 1]:
        pivot -= 1

    if pivot >= 0:
        swap_index = len(arr) - 1
        while arr[swap_index] <= arr[pivot]:
            swap_index -= 1
        arr[pivot], arr[swap_index] = arr[swap_index], arr[pivot]

    arr[pivot + 1:] = reversed(arr[pivot + 1:])
    return arr

FAQ

See also

Practice Next Permutation online (run code in the browser)Container With Most Water solution (medium)3Sum solution (medium)3Sum Closest solution (medium)Find the Duplicate Number solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?