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 👇

📌 Problem Statement

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)
🧪 Examples
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]
💡 Intuition

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)
🧾 Output
[1, 3, 2]
🔍 Dry Run (Quick Insight)

For:

[1, 2, 3]
Breakpoint → 2 < 3
Swap 2 and 3 → [1, 3, 2]
Reverse right → already minimal
⚡ Complexity Analysis
Metric Value
Time Complexity O(n)
Space Complexity O(1)