Next Permutation: How to Think, Explain & Avoid Common Mistakes

Next Permutation: How to Think, Explain & Avoid Common Mistakes | DevMentor

What the Interviewer Is Really Testing#

When an interviewer asks you to solve Next Permutation, they're not just checking if you've memorized the algorithm. They're watching how you think. Can you observe a pattern? Can you translate that observation into clean, efficient code? Can you explain your reasoning out loud without freezing up?

Here's the thing most people miss — this problem has a beautiful, intuitive logic behind it. Candidates who spot that logic and articulate it clearly stand out immediately. Candidates who jump straight to "let me generate all permutations" send a red flag before they've written a single line of code.

Let's make sure you're in the first group.

The Problem, Plainly Stated#

Given an integer array nums, rearrange it into the next lexicographically greater permutation. If no such permutation exists (the array is already the largest), rearrange it to the smallest possible order — which is just the array sorted ascending.

text

Input:  [1, 2, 3]  →  Output: [1, 3, 2]
Input:  [3, 2, 1]  →  Output: [1, 2, 3]
Input:  [1, 1, 5]  →  Output: [1, 5, 1]

Simple to state. Surprisingly easy to get wrong under interview pressure.

Building the Right Intuition First#

Before writing any code, here's the framing you should say out loud in your interview:

"Instead of generating all permutations and finding the next one — which would be O(n!) — I want to make the smallest possible increase to this number."

That single sentence tells the interviewer you're thinking efficiently. Now let's build on it.

Imagine the array [1, 3, 5, 4, 2]. Read it like a number: 13542. What's the next number up from 13542 using the same digits? It's 13524... wait, no. Think smaller steps. It's 14235? No. Let's think carefully.

Here's the key observation: the right portion of the array is often already in descending order. In our example, [5, 4, 2] is descending. That means that suffix is already the largest arrangement of those digits. You can't squeeze any more value out of it.

So what do you do? You touch the element just before that descending suffix — the 3 at index 1 — and increase it slightly. Then you make everything after it as small as possible.

That's the entire algorithm. Let's formalize it.

The Four-Step Approach#

Step 1: Find the Pivot#

Scan from right to left and find the first index i where nums[i] < nums[i+1]. This is your pivot — the leftmost place where you can make an increase.

In [1, 3, 5, 4, 2], scanning right to left: is 4 < 2? No. Is 5 < 4? No. Is 3 < 5? Yes! So i = 1, pivot is 3.

If no such i exists, the array is fully descending (like [3, 2, 1]). That means it's already the largest permutation — just reverse the whole thing.

Step 2: Find the Next Greater Element#

From the right side of the array, find the first element that is strictly greater than nums[i]. Because the suffix is descending, the first element greater than the pivot from the right is the smallest element greater than the pivot. That's exactly what you want.

In our example, scanning right to left from the end: is 2 > 3? No. Is 4 > 3? Yes! So j = 3, element is 4.

Step 3: Swap#

Swap nums[i] and nums[j]. Now the pivot position holds a slightly larger value.

After swap: [1, 4, 5, 3, 2]

Step 4: Reverse the Suffix#

Reverse everything after index i. The suffix is still in descending order after the swap (think about why — you swapped the pivot with the smallest element greater than it, so the relative order of the rest is preserved as descending). Reversing a descending sequence gives you the smallest possible arrangement.

After reverse: [1, 4, 2, 3, 5] ✅

That's the next permutation of [1, 3, 5, 4, 2].

The Clean, Interview-Ready Code#

Here's the Java solution you should be able to write from memory:

java

class Solution {
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
 
        // Step 1: Find the pivot — first index where nums[i] < nums[i+1]
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
 
        // Step 2 & 3: If pivot exists, find next greater and swap
        if (i >= 0) {
            int j = nums.length - 1;
            while (j > i && nums[j] <= nums[i]) {
                j--;

And here's the equivalent in Python if that's your language:

python

class Solution:
    def nextPermutation(self, nums: list[int]) -> None:
        n = len(nums)
        i = n - 2
 
        # Step 1: Find pivot
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
 
        # Step 2 & 3: Find next greater element and swap
        if i >= 0:
            j = n - 1
            while j > i and nums[j] <= nums[i]:
                j -= 1

Notice — both solutions modify the array in-place. Time complexity is O(n), space complexity is O(1). Be ready to state that confidently.

Where Candidates Get Stuck#

I've watched hundreds of candidates attempt this problem. Here are the exact pitfalls that derail otherwise strong engineers:

Mistake 1: Wrong Comparison Direction When Finding Next Greater Element#

This is the most common bug. Candidates write:

java

// WRONG — this skips elements in the wrong direction
while (nums[r] <= nums[i]) {
    j--;
}

The fix is to check nums[j] <= nums[i] — you want to skip elements that are not greater than the pivot, stopping at the first one that is.

java

// CORRECT
while (j > i && nums[j] <= nums[i]) {
    j--;
}

Get the comparison backwards and you'll either swap the wrong element or loop infinitely. Either way, the interviewer notices.

Mistake 2: Wrong Loop Boundary — Including the Pivot Itself#

Some candidates write while (i >= j) or use a boundary that includes index i in the suffix scan. This causes you to compare the pivot with itself and can produce wrong swaps. Always keep j > i as your boundary guard.

Mistake 3: Not Handling the "No Pivot" Case#

For an input like [3, 2, 1], i will end up as -1 after the first loop. If you then blindly try to access nums[i], you'll get an index out of bounds error. The if (i >= 0) check before the swap logic is non-negotiable. Missing this in an interview is a red flag — it signals you didn't think through edge cases.

Mistake 4: Sorting Instead of Reversing the Suffix#

A lot of candidates, when they realize the suffix needs to be in ascending order, reach for a sort. That works but it's O(n log n) — unnecessary overhead. The suffix is already in descending order when you reach Step 4. Reversing it is O(n) and the correct insight. If you sort, the interviewer will almost certainly ask: "Can you do better?" Know why reversing works.

Mistake 5: Trying to Brute-Force With All Permutations#

Please don't start here. Saying "I'll generate all permutations and find the next one" is an O(n!) approach and signals you haven't thought about the problem structure. Even if you correct yourself, you've already spent interview capital. Start with the observation, not the brute force.

How to Talk Through This in an Interview#

Here's example dialogue you can adapt. This is the kind of verbal walkthrough that makes interviewers write "strong communicator" in their notes.

Opening (after reading the problem):

"Before jumping into code, let me think about the intuition here. The brute force would be to generate all permutations — but that's O(n!) which is way too slow. Instead, I want to find the minimal increase. I notice that the rightmost portion of the array tends to already be in descending order, meaning it's already the largest arrangement of those elements. So I need to find the boundary of that descending suffix and modify the element just before it."

Walking through the steps:

"My plan is: first, scan from the right to find the pivot — the first index where nums[i] is less than nums[i+1]. Then, find the smallest element greater than the pivot from the right side of the array, swap them, and finally reverse the suffix to make it the smallest possible arrangement."

Before coding:

"Let me verify with the example [1, 3, 5, 4, 2]. Scanning right to left, the pivot is at index 1 — that's the 3. The smallest element greater than 3 from the right is 4 at index 3. After swapping, I get [1, 4, 5, 3, 2]. Then reversing the suffix from index 2 onward gives [1, 4, 2, 3, 5]. That looks right. Let me also check the edge case [3, 2, 1] — no pivot found, so we just reverse the whole array to get [1, 2, 3]. Good. Let me code this up."

That kind of structured, out-loud reasoning is exactly what FAANG interviewers are looking for.

Follow-Up Questions to Expect#

A good interviewer won't just accept your solution — they'll probe deeper. Here's what they're likely to ask and how to handle it:

Follow-Up Question	Strong Answer
"Why do you reverse instead of sort?"	"The suffix is already descending after the swap, so reversing is O(n) — no need for O(n log n) sort."
"What if there are duplicate elements?"	"The algorithm handles it — the `>=` comparison in Step 1 and `<=` in Step 2 correctly skip duplicates."
"Can you do this without modifying the array?"	"If we need to return a new array, we'd copy first — but the in-place approach is standard and expected here."
"What's the time and space complexity?"	"O(n) time for the three linear passes, O(1) space since we modify in-place."
"How would you find the previous permutation?"	"Reverse the logic — find the first index where nums[i] > nums[i+1], find the largest element smaller than it from the right, swap and reverse the suffix."

Being ready for that last one — the "previous permutation" variant — is a genuine interview differentiator.

Red Flags to Avoid#

Silence for more than 60 seconds without saying anything. Think out loud even when you're unsure. Say "I'm thinking about the edge case where the array is fully descending..."
Writing code before explaining your approach. Always walk through your logic first. Interviewers want to see your thinking, not just your typing speed.
Not testing with examples. After writing the code, trace through at least two examples — the normal case and the edge case (fully descending array). Do it on the whiteboard or in your head, but do it visibly.
Using ambiguous variable names. Call your pivot i or pivotIdx, call the swap partner j. Don't use a, b, x, y — it makes it hard to follow your reasoning.
Forgetting the in-place constraint. This problem specifically expects an in-place modification. Don't create a new array unless you've explicitly discussed it with the interviewer.

The One-Line Intuition (Worth Memorizing)#

*"Find where you can increase, increase it as little as possible, then minimize everything after it."

If you can say that clearly and then back it up with working code, you've nailed this problem.

Key Takeaways#

Lead with intuition, not brute force. Saying "make the smallest possible increase" immediately signals algorithmic maturity.
Four clean steps: find pivot → find next greater → swap → reverse suffix. Memorize these in order.
The suffix is always descending at the time of reversal. That's why reverse works instead of sort — and that's what the interviewer will ask.
Guard against the no-pivot case. Always check if (i >= 0) before attempting the swap.
Comparison direction matters. In Step 2, you're skipping elements that are <= nums[i], stopping at the first one that's strictly greater.
O(n) time, O(1) space — know this and state it confidently.
Prepare for follow-ups: previous permutation, duplicates handling, and why reverse beats sort are the three most common probes.

This problem comes up more than you'd think — not just as a standalone question but as a building block in problems involving permutations and combinatorics. Nail the intuition, practice the four steps until they're automatic, and you'll handle any variant they throw at you.