Day 8 of #100DaysOfDSA

Photo by Jesús Vidal on Unsplash

Next Permutation

One of the things I enjoy most about Data Structures and Algorithms is how some problems seem complicated until you discover the simple idea hiding behind them.

Next Permutation is one of those problems.

At first, it feels like we might need to generate every permutation, sort them, and then pick the next one. But there’s a much smarter approach that works in O(n) time and O(1) extra space.

Let’s understand the intuition behind it.

Problem Statement

Given an array representing a permutation of numbers, rearrange it into the next lexicographically greater permutation.

If no such permutation exists (the array is already the largest possible arrangement), rearrange it into the smallest possible permutation.

Example 1

Input:
1 2 3

Output:
1 3 2

Example 2

Input:
3 2 1

Output:
1 2 3

Example 3

Input:
1 3 2

Output:
2 1 3

Brute Force Approach

One obvious solution is:

• Generate all permutations.
• Sort them lexicographically.
• Find the current permutation.
• Return the next one.

Complexity

• Time: O(n × n!)
• Space: O(n × n!)

Clearly not practical.

So let’s think differently.

The Key Question

We are not looking for just any larger permutation.

We are looking for the smallest permutation that is larger than the current one.

That one sentence completely determines the algorithm.

To make the smallest increase, we should:

• Keep the beginning of the array unchanged.
• Change a number as far to the right as possible.
• Increase it by the smallest possible amount.

Everything in the algorithm follows from this idea.

Step 1: Find the Rightmost Position That Can Be Increased

Consider the permutation:

1 2 3 4

The next permutation is:

1 2 4 3

Notice something?

We didn’t change the 1.

We didn’t change the 2.

We changed the rightmost position where a larger arrangement was still possible.

This tells us to search from the right.

We’re looking for the first position where:

arr[i] < arr[i + 1]

This position is called the pivot (or breakpoint).

Example

1 2 7 6 5 4
  ^

Here,

2 < 7

So the pivot is 2.

Why Search From the Right?

Think about what we’re trying to achieve.

We want the next permutation, not one that’s much larger.

Changing a digit on the left creates a much bigger jump than changing one on the right.

For example:

1 2 3 4

Changing 2 gives something like:

1 3 ...

Changing 3 gives:

1 2 4 ...

The second change is much smaller.

So we always try to modify the permutation as late as possible, which is why we search from the right.

A Beautiful Observation

Once we find the pivot, everything after it is already in descending order.

For example,

1 2 7 6 5 4

The suffix is

7 6 5 4

Why?

Because if there had been an increasing pair further to the right, we would have found the pivot there instead.

This descending suffix is the key to the entire algorithm.

Step 2: Find the Smallest Larger Element

Now we need to increase the pivot.

But by how much?

As little as possible.

In the example:

1 2 7 6 5 4

The numbers larger than 2 are

4 5 6 7

The smallest one is 4.

So we swap 2 and 4.

Result:

1 4 7 6 5 2

Why Do We Search From the Right Again?

This is where many people get confused.

Remember, the suffix is already in descending order:

7 6 5 4

If we scan from the right, we’ll encounter:

4
5
6
7

The first element greater than the pivot is automatically the smallest one greater than it.

So the moment we find it, we can swap and immediately stop.

There is no need to continue searching.

Step 3: Reverse the Suffix

After swapping, we have:

1 4 7 6 5 2

The suffix is still in descending order.

To obtain the smallest possible permutation after the new pivot, we simply reverse it.

1 4 2 5 6 7

And that’s the answer.

Complete Walkthrough

Start with

1 2 7 6 5 4

Find the pivot

1 2 7 6 5 4
  ^

Swap with the smallest larger element

1 4 7 6 5 2

Reverse the suffix

1 4 2 5 6 7

Final answer:

1 4 2 5 6 7

Edge Case

Suppose the array is

5 4 3 2 1

There is no position where

arr[i] < arr[i+1]

This means the array is already the largest possible permutation.

The next permutation is simply

1 2 3 4 5

which can be obtained by reversing the entire array.

C++ Solution

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
      int n = nums.size();
        int pivot = -1;
        // Step 1: Find the pivot
        for(int i = n - 2; i >= 0; i--) {
            if(nums[i] < nums[i + 1]) {
                pivot = i;
                break;
            }
        }
        // Already the largest permutation
        if(pivot == -1) {
            reverse(nums.begin(), nums.end());
            return;
        }
        // Step 2: Find the smallest larger element
        for(int i = n - 1; i > pivot; i--) {
            if(nums[i] > nums[pivot]) {
                swap(nums[i], nums[pivot]);
                break;
            }
        }
        // Step 3: Reverse the suffix
        reverse(nums.begin() + pivot + 1, nums.end());
    }
};

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(1)

Key Takeaways

• We want the smallest permutation larger than the current one.
• To achieve that, we modify the rightmost position where an increase is possible.
• After the pivot, the array is always in descending order.
• Searching from the right immediately gives us the smallest element greater than the pivot.
• Finally, reversing the suffix makes it the smallest possible arrangement.

Day 8 of #100DaysOfDSA complete! 🚀