ASSIGNMENT 12

Next Permutation (In-Place & Optimal Solution)

Understanding permutations is key in many algorithmic problems.
Let’s solve a classic one: finding the next lexicographically greater permutation

Given an array of integers nums, rearrange it into the next lexicographically greater permutation.

Constraints:
-Must be done in-place
-Use only constant extra memory
-If no greater permutation exists → return the lowest possible order (sorted ascending)

Example 1
Input: [1, 2, 3]
Output: [1, 3, 2]
Example 2
Input: [3, 2, 1]
Output: [1, 2, 3]
Example 3
Input: [1, 1, 5]
Output: [1, 5, 1]

We want the next bigger arrangement, but just slightly bigger — not the maximum.

Find a place where the order breaks
Swap intelligently
Rearrange the remaining part

Step-by-Step Algorithm

• Step 1: Find the Breakpoint

Traverse from right and find the first index i such that:

nums[i] < nums[i + 1]

If No Breakpoint Found

The array is in descending order (largest permutation)

Simply reverse it:

[3,2,1] → [1,2,3]
Step 2: Find Next Greater Element

From the right side, find an element nums[j] such that:

nums[j] > nums[i]
Step 3: Swap

Swap:

nums[i] ↔ nums[j]
Step 4: Reverse the Right Half

Reverse elements from:

i + 1 → end

This ensures the smallest possible order after the swap

Python Implementation
def next_permutation(nums):
n = len(nums)

# Step 1: Find breakpoint

i = n - 2

while i >= 0 and nums[i] >= nums[i + 1]:

    i -= 1

  
  
  Step 2: If breakpoint exists


if i >= 0:

    j = n - 1

    while nums[j] <= nums[i]:

        j -= 1

    nums[i], nums[j] = nums[j], nums[i]

  
  
  Step 3: Reverse the suffix


left, right = i + 1, n - 1

while left < right:

    nums[left], nums[right] = nums[right], nums[left]

    left += 1

    right -= 1

Example usage

nums = [1, 2, 3]
next_permutation(nums)
print(nums)