Next Permutation

Problem Link

Problem: Next Permutation

Problem Statement

You are given an array of integers nums. A permutation of nums is a rearrangement of its elements. The next permutation is the one that is lexicographically greater than the current one.

If such an arrangement is not possible (i.e., the array is in descending order), 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.

Examples

Example 1
Input: nums = [1,2,3]
Output: [1,3,2]

Example 2
Input: nums = [3,2,1]
Output: [1,2,3]

Example 3
Input: nums = [1,1,5]
Output: [1,5,1]

Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 100

Intuition

We want to generate the next permutation that is just greater than the current one.
To do that, we must:

Find the first pair from the end where the left is smaller than the right → this is the point where the order dips.
Then find the smallest number greater than that dip element to the right of it and swap them.
Finally, reverse the subarray to the right of the dip to get the smallest lexicographic order.

Approach

Traverse the array from the end to find the first decreasing element at index i such that nums[i] < nums[i + 1].
If no such index is found (i.e., array is in descending order), reverse the entire array.
If i is found, again traverse from the end to find the smallest element greater than nums[i] and swap them.
Reverse the portion of the array after index i to get the next lexicographical permutation.

Code (Java)

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

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

        // Step 2: If dip is found, find the next larger element to the right and swap
        if (i >= 0) {
            int j = nums.length - 1;
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }

        // Step 3: Reverse the part after the dip
        reverse(nums, i + 1, nums.length - 1);
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    private void reverse(int[] arr, int s, int e) {
        while (s < e) {
            swap(arr, s, e);
            s++;
            e--;
        }
    }
}

Time and Space Complexity

Time Complexity: O(n)
Each step (finding the dip, swap, reverse) takes at most linear time.
Space Complexity: O(1)
All operations are in-place.

Dry Run

Input: `nums = [1, 3, 2]`

Find the dip:
- Start from the end → nums[1] = 3 > nums[2] = 2 → move to i = 0
- nums[0] = 1 < nums[1] = 3 → dip found at i = 0
Find next larger element on the right of index 0:
- Start from the end → nums[2] = 2 > nums[0] = 1 → j = 2
- Swap nums[0] and nums[2] → nums = [2, 3, 1]
Reverse subarray from i+1 = 1 to end:
- Reverse [3, 1] → [1, 3]

Final array: [2, 1, 3]

Conclusion

This problem is a classic implementation of next lexicographical permutation using a greedy and in-place approach. It avoids generating all permutations and directly jumps to the next valid one using well-defined steps: dip → swap → reverse.