Next Permutation — Brute Force to Optimal Intuition

The Next Permutation problem requires rearranging a given sequence of numbers into its lexicographically next greater permutation. If no such greater permutation exists (i.e., the array is sorted in descending order), the sequence must be rearranged into its lowest possible order (sorted in ascending order). The algorithm must perform this transformation in-place using $O(1)$ auxiliary space.

1. Problem Definition and Lexicographical Order

A permutation is an arrangement of a collection of numbers into a specific linear order. For an array of length $N$ containing distinct elements, there are $N!$ possible permutations.

When all permutations are listed in lexicographical order (dictionary order), they are sorted numerically from smallest to largest value.

Problem Rules

1. Given an array arr, return the permutation that immediately follows it in lexicographical order.
2. Edge Case: If the input is the last permutation (e.g., [3, 2, 1]), fallback to the first permutation (e.g., [1, 2, 3]).
3. Modifications must be done in-place without allocating additional array structures.

2. Real-World Analogy: Dictionary Order & Prefix Matching

Real-Life Analogy

Consider how words are sorted in an English dictionary:

• Prefix Match: Notice that "RAJ" and "RAX" share a long common prefix ("RA"). Because "RA" is preserved, "RAX" comes immediately after "RAJ".
• Prefix Break: "RBX" comes much later because it breaks the prefix at the second letter ('B' instead of 'A').

Core Principle: To find the immediate next value, keep the longest possible matching prefix, and change the character right after the prefix to the smallest possible larger character.

3. Naive Brute-Force Approach (Recursive Generation)

The naive mental model directly follows the problem definition.

Algorithm Steps

1. Generate All: Recursively generate all $N!$ permutations of the array.
2. Sort: Sort all generated permutations in ascending lexicographical order.
3. Linear Search: Iterate through the sorted list to find the location of the input array.
4. Select Next: Return the permutation at index + 1. If the array is at index = N! - 1, return the permutation at index = 0.

Why Brute Force Fails in Production

• Time Complexity: $O(N! \times N)$ — Generating $N!$ permutations where each has length $N$. For $N = 15$, $15! \approx 1.3 \times 10^{12}$ operations, leading to Time Limit Exceeded (TLE).
• Space Complexity: $O(N! \times N)$ auxiliary space to store all permutations.

Interview Tip: In an interview, describe this brute-force approach abstractly at a high level. Do not write recursive code for generating all permutations unless explicitly requested, as it wastes critical coding time. Transition quickly by stating the time complexity is $O(N! \times N)$ and proposing an optimization.

4. Built-in STL Approach (C++ Specific)

In C++, the Standard Template Library (STL) provides a built-in method:

#include <algorithm>
#include <vector>

std::vector<int> arr = {1, 2, 3};
std::next_permutation(arr.begin(), arr.end());

Note: While mentioning std::next_permutation in C++ demonstrates language awareness, interviewers will invariably ask you to implement the underlying logic manually without relying on built-in utilities.

5. Optimal Approach: Key Observations & Mathematical Intuition

To derive the optimal $O(N)$ solution, examine the numerical properties of sequences during lexicographical incrementing using a large example:

Observation 1: The Breakpoint (Finding the Dip)

Traverse the array from right to left (end to start). As long as numbers are increasing (arr[i] >= arr[i+1]), no larger permutation can be formed using just that right suffix—it is already at its maximum possible value.

The first index where arr[i] < arr[i + 1] is the breakpoint (the "dip").

• Looking at [2, 1, 5, 4, 3, 0, 0] from right to left:
  • 0 <= 0 (Increasing/Flat)
  • 0 <= 3 (Increasing)
  • 3 <= 4 (Increasing)
  • 4 <= 5 (Increasing)
  • 1 < 5 $\longrightarrow$ Breakpoint found at Index i = 1 (arr[1] = 1).

Prefix to preserve: [2] (Index 0).

Observation 2: Finding the Next Greater Element

We must replace arr[breakpoint] (which is 1) with an element from its right suffix [5, 4, 3, 0, 0] that is strictly greater than 1, but as small as possible (to get the immediate next permutation).

Since the suffix to the right of breakpoint is guaranteed to be in non-increasing order:

• Scan from right to left.
• The first element strictly greater than arr[breakpoint] is our target.

Scanning [5, 4, 3, 0, 0] from right to left:

• 0 > 1 (False)
• 0 > 1 (False)
• 3 > 1 (True) $\longrightarrow$ Select 3 at Index j = 4.

Swap arr[1] (1) and arr[4] (3):

Observation 3: Minimizing the Suffix (Reversing)

The prefix is now [2, 3]. Because 23... is strictly greater than 21..., any arrangement of the remaining suffix [5, 4, 1, 0, 0] will yield a value larger than the original array.

To make it the immediate next permutation, the suffix must be as small as possible (sorted in ascending order).

Since the suffix was already sorted in descending order, swapping the breakpoint element preserved this property. To convert a descending sequence into an ascending sequence, simply reverse the suffix in $O(N)$ time.

Suffix before reverse: [5, 4, 1, 0, 0]
Suffix after reverse:  [0, 0, 1, 4, 5]

Final Result: [2, 3, 0, 0, 1, 4, 5]

6. Complete Vertical Workflow

[2, 1, 5, 4, 3, 0, 0]
       |
       | Step 1: Scan right-to-left to find dip (arr[i] < arr[i+1])
       v
Break Index = 1 (Value = 1)
       |
       | Step 2: Scan right-to-left to find first value > arr[1]
       v
Swap Index = 4 (Value = 3)
       |
       | Step 3: Swap arr[1] and arr[4]
       v
[2, 3, 5, 4, 1, 0, 0]
       |
       | Step 4: Reverse suffix from break_index + 1 to end
       v
[2, 3, 0, 0, 1, 4, 5] (Final Result)

7. Step-by-Step Flow Walkthrough

Example Array: [2, 1, 5, 4, 3, 0, 0]

1. Find Breakpoint:

   • i = 5: arr[5] (0) >= arr[6] (0)
   • i = 4: arr[4] (3) >= arr[5] (0)
   • i = 3: arr[3] (4) >= arr[4] (3)
   • i = 2: arr[2] (5) >= arr[3] (4)
   • i = 1: arr[1] (1) < arr[2] (5) $\longrightarrow$ Break Point ind = 1

2. Handle Edge Case (No Breakpoint):

   • If ind == -1 (e.g., array is [5, 4, 3, 2, 1]), reverse the entire array to return [1, 2, 3, 4, 5] and finish.

3. Find Swap Target:

   • i = 6: arr[6] (0) <= arr[1] (1)
   • i = 5: arr[5] (0) <= arr[1] (1)
   • i = 4: arr[4] (3) > arr[1] (1) $\longrightarrow$ Swap Target j = 4

4. Swap Elements:

   • Swap arr[1] and arr[4].
   • Array becomes [2, 3, 5, 4, 1, 0, 0].

5. Reverse Suffix:

   • Reverse range [ind + 1, N - 1] $\longrightarrow$ Range [2, 6].
   • Segment [5, 4, 1, 0, 0] becomes [0, 0, 1, 4, 5].
   • Final Array: [2, 3, 0, 0, 1, 4, 5].

8. Implementation Code

C++ Implementation

#include <vector>
#include <algorithm>
#include <iostream>

class Solution {
public:
    void nextPermutation(std::vector<int>& nums) {
        int n = nums.size();
        int breakIndex = -1;

        // Step 1: Find the break point (first dip from the right)
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                breakIndex = i;
                break;
            }
        }

        // Edge Case: If no break point exists, array is in descending order
        if (breakIndex == -1) {
            std::reverse(nums.begin(), nums.end());
            return;
        }

        // Step 2: Find element strictly greater than nums[breakIndex] from right
        for (int i = n - 1; i > breakIndex; i--) {
            if (nums[i] > nums[breakIndex]) {
                std::swap(nums[i], nums[breakIndex]);
                break;
            }
        }

        // Step 3: Reverse the right suffix to make it smallest possible
        std::reverse(nums.begin() + breakIndex + 1, nums.end());
    }
};

Java Implementation

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

        // Step 1: Find the break point
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                breakIndex = i;
                break;
            }
        }

        // Edge Case: If array is sorted descending, reverse all
        if (breakIndex == -1) {
            reverse(nums, 0, n - 1);
            return;
        }

        // Step 2: Find element greater than nums[breakIndex] from right
        for (int i = n - 1; i > breakIndex; i--) {
            if (nums[i] > nums[breakIndex]) {
                swap(nums, i, breakIndex);
                break;
            }
        }

        // Step 3: Reverse the suffix starting at breakIndex + 1
        reverse(nums, breakIndex + 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--;
        }
    }
}

Python Implementation

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        break_index = -1

        # Step 1: Find the break point
        for i in range(n - 2, -1, -1):
            if nums[i] < nums[i + 1]:
                break_index = i
                break

        # Edge Case: If no break point, reverse entire array
        if break_index == -1:
            nums.reverse()
            return

        # Step 2: Find smallest element strictly greater than nums[break_index] from right
        for i in range(n - 1, break_index, -1):
            if nums[i] > nums[break_index]:
                nums[i], nums[break_index] = nums[break_index], nums[i]
                break

        # Step 3: Reverse suffix in-place
        left = break_index + 1
        right = n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

9. Complexity Analysis & Strategy Summary

Algorithmic Comparison

Detailed Analysis of Optimal Solution

• Time Complexity: $O(3N) \approx O(N)$
  • Step 1 (Find Dip): At most $N$ iterations.
  • Step 2 (Find Next Greater): At most $N$ iterations.
  • Step 3 (Reverse Suffix): At most $N/2$ swaps.
  • Total time is strictly linear, $O(N)$.
• Space Complexity: $O(1)$ auxiliary space since all operations (finding indices, swapping, and reversing) are performed directly in-place on the input array.

10. Summary and Key Takeaways

• Lexicographical Ordering: Permutations follow dictionary order. Finding the next permutation requires keeping the prefix match as long as possible.
• The Dip Property: Traverse from right to left to find the first element where arr[i] < arr[i + 1]. This marks the breakIndex.
• Descending Suffix Guarantee: Everything to the right of breakIndex is guaranteed to be sorted in descending order (arr[i + 1] >= arr[i + 2] >= ...).
• Target Selection: Swap arr[breakIndex] with the first element strictly greater than it when traversing from the right edge.
• Suffix Reversal: Because the suffix remains in descending order after swapping, reversing it converts it to ascending order in $O(N)$ time, achieving the smallest possible suffix continuation.
• Edge Case Loop-Back: If no dip is found (breakIndex == -1), the array represents the absolute maximum permutation. Reversing the entire array loops back to the absolute minimum permutation (sorted ascending).