CA 12 - Next Permutation

Problem Statement

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

For example, for arr = [1,2,3], the following are all the permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

Given an array of integers nums, find the next permutation of nums.

The replacement must be in-place and use only constant extra memory.

Examples:

Input: nums = [1,2,3]
Output: [1,3,2]

Input: nums = [3,2,1]
Output: [1,2,3]

Input: nums = [1,1,5]
Output: [1,5,1]

My Goal

For this problem, my goal was to understand how permutations are ordered lexicographically. Learn how to generate the next permutation efficiently avoiding brute-force generation of all permutations. Solve the problem in-place with constant space

Solution

I followed the standard next permutation approach but kept the logic simple step by step. First, I traverse the array from the right and find the first index where the current element is smaller than the next one. This tells me where the change needs to happen.

If I find such an index, I again traverse from the right to find an element that is just greater than it, then swap both of them. After that, I reverse the part of the array that comes after that index to get the next smallest permutation. If no such index is found, it means the array is already in the highest permutation, so I just reverse the whole array to get the lowest one.

Solution Code (Python)

a = [1, 2, 3]

i = len(a) - 2

while i >= 0 and a[i] >= a[i + 1]:
    i -= 1

if i >= 0:
    j = len(a) - 1
    while a[j] <= a[i]:
        j -= 1
    a[i], a[j] = a[j], a[i]

l = i + 1
r = len(a) - 1

while l < r:
    a[l], a[r] = a[r], a[l]
    l += 1
    r -= 1

print(a)