Next Permutation - CA12

My Thinking and Approach

---

Introduction

In this problem, I was given an array of integers and asked to rearrange it into the next lexicographically greater permutation.

If such arrangement is not possible, I need to rearrange it into the smallest possible order.

---

Problem Statement

• Given an array of integers nums

• Modify the array to its next permutation

• Conditions:

  • Modify in-place
  • Use constant extra space
  • If no next permutation exists → rearrange to ascending order

---

My Initial Thought

At first, I considered:

• Generating all permutations
• Sorting them
• Picking the next one

But this approach is not efficient.

---

Key Observation

While analyzing the problem:

• The change happens from the right side
• We need to find a position where increasing order breaks

---

Optimized Approach

I decided to follow three steps.

Logic:

• Find the break point
• Swap with next greater element
• Reverse the right part

---

My Approach (Step-by-Step)

1. Traverse from right and find index i such that:

• nums[i] < nums[i + 1]

1. If index exists:

• Find element just greater than nums[i] from right
• Swap them

1. Reverse elements from i + 1 to end

---

Code (Python)

Below is the implementation clearly separated inside a code block:

class Solution:
    def nextPermutation(self, nums):
        n = len(nums)
        i = n - 2

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

        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left = i + 1
        right = n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

---

Example Walkthrough

Input:

nums = [1, 2, 3]

Steps:

• Break point → index 1
• Swap → [1, 3, 2]
• Reverse right part

Output:

[1, 3, 2]

---

Complexity Analysis

Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

---

Key Takeaways

• Right to left traversal is important
• In-place modification is required
• Efficient approach avoids generating permutations

---

Conclusion

This problem helped me understand how to efficiently compute the next permutation using a step-by-step approach.

---