Algorithm Day100 - Next Permutation

🧩 Problem

LeetCode 31 - Next Permutation
Implement the next lexicographical permutation of the given integer array nums.
If such arrangement is not possible, rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in-place and use only constant extra memory.

Example:

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]

---

💡 Idea

To get the next lexicographically larger permutation, we follow three steps:

1. Find the first decreasing element (pivot) from the right side where nums[i] < nums[i+1].
   If no such index exists, it means the array is in descending order → reverse it directly.

2. Find the smallest element greater than nums[i] to the right of it, say nums[j].

3. Swap nums[i] and nums[j], then reverse the subarray from i+1 to the end.
   This ensures the next immediate permutation is achieved.

---

💻 Java Code

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = n - 1;
            while (nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }

        reverse(nums, i + 1, n - 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

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

---

🧠 Complexity

• Time: O(n) — One pass to find pivot, one to reverse.
• Space: O(1) — In-place manipulation.

---

🏁 Summary

The key insight is recognizing the first decreasing pair from the right and making the minimal change to reach the next permutation.
This elegant algorithm is widely used in combinatorial generation and backtracking problems.