Find Next Permutation

Problem

Given an array. Find the next permutation that rearranges the array into the next lexicographical order. If there is no next permutation, rearrange the array into the lowest possible order.

Examples

  • [2, 4, 1, 7, 5, 0] ➜ [2, 4, 5, 0, 1, 7]

  • [3, 4, 2, 5, 1] ➜ [3, 4, 5, 1, 2]

  • [3, 2, 1] ➜ [1, 2, 3]

    • As [3, 2, 1] is the last permutation, the next permutation is the lowest one.

Constraints

  • 1 ≤ arr.size() ≤ 10⁵

  • 0 ≤ arr[i] ≤ 10⁵

Expected Complexities

  • Time Complexity: O(n)O(n)

  • Auxiliary Space: O(1)O(1)

Solution

Python
Numeric = int | float


def find_next_permutation(arr: list[Numeric]) -> list[Numeric]:
    n: int = len(arr)

    def reverse(left_index: int, right_index: int) -> None:
        while left_index < right_index:
            arr[left_index], arr[right_index] = arr[right_index], arr[left_index]
            left_index += 1
            right_index -= 1

    pivot_index: int = -1
    for i in range(n - 2, -1, -1):
        if arr[i] < arr[i + 1]:
            pivot_index = i
            break

    if pivot_index == -1:
        reverse(0, n - 1)
        return arr

    for i in range(n - 1, pivot_index, -1):
        if arr[i] > arr[pivot_index]:
            arr[i], arr[pivot_index] = arr[pivot_index], arr[i]
            break

    reverse(pivot_index + 1, n - 1)
    return arr


print(find_next_permutation([2, 4, 1, 7, 5, 0]))
print(find_next_permutation([3, 4, 2, 5, 1]))
print(find_next_permutation([3, 2, 1]))