Next Permutation-CA12

My Thinking and Approach

In this problem, I was given an array of integers and asked to find the next permutation of that array.

At first, the problem felt confusing because it was not a direct sorting or simple loop problem. I had to clearly understand what “next permutation” actually means before solving it.

---

Problem Understanding

• A permutation means rearranging elements into a sequence
• The next permutation means the next greater arrangement in lexicographical (dictionary) order
• If no greater arrangement exists, we must return the smallest possible arrangement (sorted in ascending order)

---

My Initial Thought

Initially, I thought of a brute force approach:

• Generate all permutations
• Sort them
• Find the next permutation

But I quickly realized:

• Generating permutations takes O(n!) time
• This is not feasible for larger inputs

So I needed a smarter approach.

---

Key Observation

While thinking more, I noticed:

• Changes in permutations mostly happen from the right side
• The rightmost elements change faster compared to the left

This observation helped me move towards the optimal solution.

---

My Step-by-Step Approach

Step 1: Find the Break Point

I start from the right and look for the first position where the order breaks.

• Find index i such that:

nums[i] < nums[i + 1]

This tells me that I can still form a bigger permutation from this position.

Example

[1, 2, 3]

• Start from right:

  • 2 < 3 → break point at index 1

---

Step 2: Find the Next Greater Element

Now I need to make the number just slightly bigger.

• Again start from the right
• Find the element just greater than nums[i]
• Swap both

Example

[1, 2, 3]

• Break point = 2
• Next greater element = 3
• Swap → [1, 3, 2]

---

Step 3: Reverse the Right Part

After swapping, the right part is not in smallest order.

• Reverse elements from i + 1 to end
• This gives the next smallest permutation

Example

[1, 3, 2]

• Right part is already minimal → no major change

---

Code (Java)

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;

        // Step 1: Find breakpoint
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // Step 2: Swap with next greater element
        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        // Step 3: Reverse right part
        reverse(nums, i + 1, n - 1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

---

Full Example Walkthrough

Example 1

Input:
[1, 2, 3]

• Break point → index 1 (2 < 3)
• Swap 2 and 3 → [1, 3, 2]
• Reverse right → [1, 3, 2]

Output:
[1, 3, 2]

---

Example 2

Input:
[2, 3, 1]

• Break point → index 0 (2 < 3)
• Find next greater than 2 → 3
• Swap → [3, 2, 1]
• Reverse right → [3, 1, 2]

Output:
[3, 1, 2]

---

Edge Case

Input:
[3, 2, 1]

• No break point found
• Entire array is decreasing
• Reverse whole array

Output:
[1, 2, 3]

---

Time and Space Complexity

• Time: O(n)
• Space: O(1)

---

Final Understanding

From this problem, I learned:

• Brute force is not always the right approach
• Observing patterns (especially from right to left) is very important
• Small logical steps can lead to an optimal solution

This problem helped me improve my thinking in permutations, array manipulation, and optimization techniques.