Next Permutation

📌 Problem Statement

A permutation of an array of integers is a reordering of its elements into a sequence.

 For example, 
 for arr = [1, 2, 3], all permutations are:
 [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]

The next permutation of an array is the next lexicographically greater permutation.

If such a permutation is not possible (i.e., the array is sorted in descending order), then the result should be the lowest possible order (i.e., sorted in ascending order).

❗Requirements:

You must rearrange the numbers in-place.

You can only use constant extra memory.

🧠 Understanding with Examples

Example 1:

Input:  [1, 2, 3]
Output: [1, 3, 2]
Explanation: In lexicographical order, [1,3,2] comes right after [1,2,3].

Example 2:

Input:  [3, 2, 1]
Output: [1, 2, 3]
Explanation: No higher permutation possible → so return the lowest.

Example 3:

Input:  [1, 1, 5]
Output: [1, 5, 1]

🔍 Approach: Step-by-Step Explanation

Let’s find the next permutation in three key steps:

✅ Step 1: Find the Break Point

Traverse the array from right to left and find the first index i such that:

nums[i] < nums[i + 1]

This is where the array starts descending. Let’s call it the "break point".

If no such index exists, the array is sorted in descending order. Reverse the whole array to return the lowest permutation.

✅ Step 2: Find the Just Larger Element

If we found such an index i, again traverse from the end and find first index j such that:

nums[j] > nums[i]

This is the smallest number greater than nums[i] to the right. Swap nums[i] and nums[j].

✅ Step 3: Reverse the Subarray

Reverse the elements from index i+1 to the end to get the next smallest arrangement.

🔁 Dry Run on [1, 3, 5, 4, 2]

1. Break point: i = 1 (nums[1] = 3, because 3 < 5)
2. Just larger: j = 3 (nums[3] = 4, because 4 > 3)
3. Swap: [1, 4, 5, 3, 2]
4. Reverse from index 2: [1, 4, 2, 3, 5]
✅ Final Output: [1, 4, 2, 3, 5]

🧑‍💻 Code Implementations

✅ C++ Code

#include <vector>
#include <algorithm>
using namespace std;

void nextPermutation(vector<int>& nums) {
    int i = nums.size() - 2;

    while (i >= 0 && nums[i] >= nums[i + 1]) i--;

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

    reverse(nums.begin() + i + 1, nums.end());
}

✅ Java Code

import java.util.*;

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

        while (i >= 0 && nums[i] >= nums[i + 1]) i--;

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

        reverse(nums, i + 1, nums.length - 1);
    }

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

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

✅ Python Code

def nextPermutation(nums):
    i = len(nums) - 2

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

    if i >= 0:
        j = len(nums) - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]

    # Reverse from i+1 to end
    nums[i+1:] = reversed(nums[i+1:])

📊 Time & Space Complexity

All operations are done in-place with constant extra memory.

🎯 Conclusion

The Next Permutation algorithm is a powerful yet elegant tool to generate the next

lexicographical arrangement. It’s widely asked in interviews and teaches you:

Greedy thinking

In-place swapping

Array traversal and manipulation