Next Permutation — Intuition, Explanation, and Clean Implementation

Hey fellow developers 👋

Welcome back to our DSA learning series!

This series is all about picking problems that every beginner finds confusing at first — and breaking them down slowly, logically, and humanly. We are students ourselves, and we know how overwhelming DSA can feel if you jump straight into the code without understanding why something works.

Today, we are exploring a classic problem that helps build strong intuition around arrays and ordering — Next Permutation.

At first glance, it feels abstract and mathematical.

But once you understand the pattern behind permutations, the entire logic becomes surprisingly simple and elegant.

---

Problem Statement

We are given an array of integers representing a permutation.

Our goal is to rearrange the numbers to form the next lexicographically greater permutation.

If such an arrangement does not exist (meaning the array is already the highest possible permutation), we return the lowest possible arrangement — which is just the array sorted in ascending order.

Example:

• [1,2,3] → [1,3,2]
• [2,3,1] → [3,1,2]
• [3,2,1] → [1,2,3]

The rearrangement must be in-place and use constant extra memory.

---

Understanding the Core Idea

Before we try to code anything, let us think about what it means for one permutation to come after another in lexicographical order.

Take this example:

1 2 5 4 3

We want to find the "next" arrangement.

What does "next" mean?

It means:

Make the smallest possible change that results in a bigger permutation.

So we ask ourselves:

---

Step 1: Finding the Pivot (the dip point)

We scan from right to left and find the first place where the order breaks the descending pattern.

Why descending?

Because if the entire array is in descending order (like [5,4,3,2,1]), it is already the largest permutation.

Example:

1 *2* 5 4 3
   ↑
  2 > 4 fails

So the pivot is 2’s index.

This pivot is the point where we can make a “small increase”.

---

Step 2: Find the next greater element on the right

To make the permutation just slightly larger, we swap the pivot with the next greater element from its right side.

For our example, our next element greater than 2 from the right is 3, so we swap it with 2

1 3 5 4 2

---

Step 3: Reverse the remaining right portion

Once we swap, the right portion is still in descending order.

Reversing it gives the smallest lexicographical tail i.e. our result will be

1 3 2 4 5

This step finalizes the next permutation.

---

Why This Algorithm Works

Because lexicographical ordering is all about:

• Making the smallest possible increase at the earliest position
• Keeping the rest of the sequence as small as possible

This ensures we get the next permutation — not just any greater permutation.

---

Code Implementation (Java)

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

        // Step 1: Find pivot index
        for (int i = n - 1; i > 0; --i) {
            if (nums[i] > nums[i - 1]) {
                pivot = i - 1;
                break;
            }
        }

        // If no pivot found, array is in descending order
        if (pivot == -1) {
            Arrays.sort(nums); 
            return;
        }

        // Step 2: Find next greater element on the right of pivot
        for (int i = n - 1; i > pivot; --i) {
            if (nums[i] > nums[pivot]) {
                int temp = nums[i];
                nums[i] = nums[pivot];
                nums[pivot] = temp;
                break;
            }
        }

        // Step 3: Reverse the descending suffix
        reverse(nums, pivot + 1, n - 1);
    }

    private void reverse(int[] nums, int left, int right) {
        while (left < right) {
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;

            left++;
            right--;
        }
    }
}

---

Conclusion

In conclusion, the problem looks intimidating at first because it deals with lexicographical order — something we usually do not think about explicitly.

But once you understand the three simple steps:

1. Find the pivot
2. Swap with the next greater element
3. Reverse the tail

…the problem becomes extremely intuitive.

This problem tests:

• Pattern recognition
• Understanding of permutations
• Logical reasoning
• Ability to write clean in-place algorithms

Master this once and it will stick with you forever.

Happy coding, friends!