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]))