Next Permutation — Finding the Next Smallest Bigger Number

Let’s assume an array:

[3, 1, 2]

We need to find the next permutation of the given array.

What is a Permutation?

A permutation is simply a rearrangement of the elements of an array.

For example, the permutations of:

[1, 2, 3]

are:

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

These permutations are arranged in lexicographical order, which is similar to the order of words in a dictionary.

What is Next Permutation?

Given a permutation, we need to find the arrangement that comes immediately after it in lexicographical order.

For example:

Current permutation:

[2, 1, 3]

Next permutation:

[2, 3, 1]

Another example:

Current permutation:

[3, 2, 1]

Next permutation:

[1, 2, 3]

Since [3, 2, 1] is already the largest possible arrangement, we wrap around to the smallest arrangement.

A simple way to think about this problem is:

Find the smallest possible number that is still greater than the current arrangement.

How Do We Find It?

Consider the array:

[8, 4, 2, 7, 5, 3, 1]

Treat it as a number:

8427531

We want the next bigger number, but we want the increase to be as small as possible.

Step 1: Traverse from the Right

We start from the right because changing digits near the end produces the smallest possible increase.

Step 2: Find the Pivot

Moving from right to left:

1 < 3 < 5 < 7

This suffix is already in decreasing order:

7 > 5 > 3 > 1

Since this part is already the largest arrangement possible, we continue moving left.

We stop at:

2 < 7

The digit 2 is called the pivot.

Step 3: Find the Smallest Element Greater Than the Pivot

To the right of the pivot, we have:

[7, 5, 3, 1]

Among these elements, the smallest value greater than 2 is:

3

So we swap 2 and 3.

The array becomes:

[8, 4, 3, 7, 5, 2, 1]

Step 4: Make the Remaining Part as Small as Possible

The suffix:

[7, 5, 2, 1]

is still in decreasing order.

To get the immediate next permutation, we must make this suffix as small as possible.

So we reverse it:

[1, 2, 5, 7]

Final result:

[8, 4, 3, 1, 2, 5, 7]

Key Thoughts

The goal is not to find any larger permutation.

The goal is to:

1. Increase the number at the rightmost possible position.
2. Increase it by the smallest possible amount.
3. Make the remaining digits as small as possible.

That’s exactly why the Next Permutation algorithm works.

Complexity Analysis

The algorithm scans the array from right to left to find the pivot, then scans again to find the element to swap, and finally reverses the suffix.

Time Complexity: O(n)

Space Complexity: O(1)

The solution is performed in-place and does not require any extra array.

How Do We Recognize a Next Permutation Problem?

The phrase “Next Permutation” may not always appear directly in the question. Instead, look for clues such as:

• Next lexicographically greater arrangement
• Next larger arrangement using the same digits/elements
• Immediate successor in dictionary order
• Smallest number greater than the current arrangement
• Rearrange the elements to obtain the next greater sequence

Final Takeaway

Next Permutation = Find the next smallest bigger number using the same elements.

Next Permutation Summarized