CA 12 - Next Permuntation

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
Avoid brute-force generation of all permutations
Solve the problem in-place with constant space

Solution

I followed the standard next permutation algorithm, which works in a few key steps.

Idea:

Traverse from right and find the first index i such that
a[i] < a[i + 1]
If such an index exists:
Find index j such that a[j] > a[i] from the right
Swap a[i] and a[j]
Reverse the subarray from i + 1 to end
If no such index exists → reverse entire array

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)

Explanation

Find the "break point" where order stops increasing
Swap with the next greater element
Reverse the remaining part to get smallest order