Next Permutation

Description

Next Permutation
A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

• For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1].

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

• For example, the next permutation of arr = [1,2,3] is [1,3,2].
• Similarly, the next permutation of arr = [2,3,1] is [3,1,2].
• While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.

Given an array of integers nums, find the next permutation of nums.

The replacement must be in place and use only constant extra memory.

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

Approach

• So basically we find a pivot which is basically the first element from right so that the next element is increasing so the element next to pivot the elements next to it would be decreasing because if not then that would be pivot
• once we find the pivot then we just swap these two basically that is what is lexicographically we pick the next element
• then we reverse that decreasing order because if we have a new element then next elements should be increasing and not decreasing
• Time: O(n) (at most 2 passes)
• Space: O(1) (in-place swap and reverse)

class Solution {
    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 (j > i && nums[i] >= nums[j])
                j--;
            
            swap(nums, i , j);
        }    
 
        reverse(nums, i + 1, nums.length - 1);
 
    }
 
    void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
 
    void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

---

1. Brute Force Approach (Conceptual)

Intuition

To find the next lexicographically larger permutation, you can explicitly generate all possibilities in sorted order.

Steps:

1. Generate all $N!$ permutations of the array.
2. Sort them in ascending lexicographical order.
3. Search for the input array in the sorted list.
4. Return the permutation that appears right after it (if it’s the last one, return the first permutation).

Complexity:

• Time Complexity: $O(N!\cdot N)$ — Generating all $N!$ permutations takes factorial time.
• Space Complexity: $O(N!\cdot N)$ — Storing all generated permutations in memory.

Why it won’t work: LeetCode requires an in-place solution with $O(1)$ extra memory. For $N=100$, $100!$ is larger than the number of atoms in the universe!

---

2. Optimal Approach: The 3-Step “Breakpoint” Algorithm

The Mental Trick (How to Remember It Easily)

Think of the array as a sequence of digits (e.g., [2, 1, 5, 4, 3]). To get the next smallest increase:

1. Find where the digits start decreasing from right to left (The Breakpoint).
2. Swap that digit with the next smallest digit that is larger than it to its right.
3. Reverse everything after the breakpoint to make the suffix as small as possible.

---

Step-by-Step Example: [2, 1, 5, 4, 3]

Step 1: Find the Breakpoint (i)

Scan from right to left to find the first element that is smaller than its right neighbor (nums[i] < nums[i + 1]).

• 3 < 4 (No, moving left…)
• 4 < 5 (No, moving left…)
• 1 < 5 (Yes! Breakpoint found at i = 1, value 1)

(If no such breakpoint exists—e.g., [5, 4, 3, 2, 1]—it means the array is in reverse order. Simply reverse the whole array to get [1, 2, 3, 4, 5] and you’re done!)

Step 2: Swap with the Next Just-Bigger Number (j)

Scan from the right end again to find the first number greater than nums[i].

• Compare with 3: $3>1$ (Found at j = 4, value 3)
• Swap nums[i] and nums[j]:
  [2, 1, 5, 4, 3] $\to$ [2, 3, 5, 4, 1]

Step 3: Reverse the Suffix

Everything to the right of index i (index 2 to 4, which is [5, 4, 1]) is currently in descending order. Reverse it to make it ascending (smallest possible suffix):

• Reverse [5, 4, 1] $\to$ [1, 4, 5]
• Final Result: [2, 3, 1, 4, 5]

Key points

• Decreasing Suffix: Everything to the right of breakpoint i is guaranteed to be in decreasing order (left-to-right), meaning those digits currently form the largest possible number they can.
• Finding Next Larger Element: Scanning backwards with while (nums[j] <= nums[i]) j--; starts from the smallest digit in the suffix and moves up. The first element strictly greater than nums[i] is mathematically guaranteed to be the next larger element (the smallest valid jump forward).
• Preserved Decreasing Order & Reversal: Swapping nums[i] and nums[j] keeps the suffix strictly decreasing. Because it remains descending, reversing it into ascending order is both correct and necessary to reset it to its absolute smallest arrangement.
• >= being used everywhere

---

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
 
        // Step 1: Find the first decreasing element from the right
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
 
        // Step 2: If breakpoint exists, find the next larger element and swap
        if (i >= 0) {
            int j = n - 1;
            while (nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
 
        // Step 3: Reverse the suffix starting from i + 1
        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);
            start++;
            end--;
        }
    }
}
 

---

Complexity Analysis

• Time Complexity: $O(N)$ — At most two linear scans of the array and one reverse operation.
• Space Complexity: $O(1)$ — Done entirely in-place with standard pointers.