Next Permutation of Array - Optimal Approach

Next Permutation of Array - Optimal Approach

Visualization

Algorithm Steps

Given an array arr of integers.
Start from the end and find the first index i where arr[i] < arr[i+1]. This identifies the pivot.
If no such index exists, reverse the entire array to get the lowest permutation.
Otherwise, find the next larger element than arr[i] from the end of the array, say index j, and swap arr[i] and arr[j].
Finally, reverse the subarray from i+1 to the end to get the next permutation.

Find Next Lexicographical Permutation of an Array Code

Python

JavaScript

Java

C++

C

def next_permutation(arr):
    n = len(arr)
    i = n - 2
    while i >= 0 and arr[i] >= arr[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while arr[j] <= arr[i]:
            j -= 1
        arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1:] = reversed(arr[i + 1:])
    return arr

# Sample Input
arr = [1, 2, 3]
print("Next Permutation:", next_permutation(arr))