Next Permutation [Medium] — The In-Place Algorithm That Trips Up Senior Engineers [Google, Facebook, Amazon]

Problem Statement

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If no greater permutation exists (the array is the largest possible), rearrange it into the smallest possible order (i.e., sorted in ascending order). The replacement must be done in-place and use only O(1) extra memory.

Examples:

Input:  [1, 2, 3]   → Output: [1, 3, 2]
Reason: [1,2,3] → [1,3,2] is the next order in the sequence
        1,2,3 / 1,3,2 / 2,1,3 / 2,3,1 / 3,1,2 / 3,2,1

Input:  [3, 2, 1]   → Output: [1, 2, 3]
Reason: [3,2,1] is the last (largest) permutation — wrap to first (smallest)

Input:  [1, 1, 5]   → Output: [1, 5, 1]
Reason: Duplicates are allowed; [1,5,1] comes after [1,1,5]

Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 100

• Why This Problem Matters
• Building the Algorithm From Scratch
• The Core Question: Where Does the Next Permutation Differ?
• Step 1 — Why We Scan From the Right for the Pivot
• Step 2 — Why We Swap With the Smallest Element Larger Than the Pivot
• Step 3 — Why We Reverse Instead of Sort the Suffix
• The 3-Step Algorithm
• Edge Case: The Largest Permutation
• Visual Dry Run
• Trace 1: [1, 2, 3] → [1, 3, 2]
• Trace 2: [3, 2, 1] → [1, 2, 3] (wrap-around case)
• Trace 3: [1, 3, 2] → [2, 1, 3] (multi-element suffix swap)
• Common Mistakes
• Mistake 1: Scanning the Array From Left to Right in Step 1
• Mistake 2: Swapping the Pivot With the Wrong Element
• Mistake 3: Sorting the Suffix Instead of Reversing It
• Mistake 4: Not Handling the No-Pivot Case
• Solutions
• Python
• JavaScript
• Complexity Analysis
• Follow-up Questions
• 1. Previous Permutation (LeetCode 1053)
• 2. Permutation Sequence — k-th Permutation (LeetCode 60)
• 3. All Permutations (LeetCode 46)
• 4. Next Permutation With Duplicates (LeetCode 31 variant)
• This Pattern Solves
• Key Takeaway

Why This Problem Matters

LeetCode 31 is deceptively named — it sounds like a permutation-generation exercise. It is not. You do not enumerate all permutations and find the next one. You make a single, surgical rearrangement in O(n) time without any extra memory.

That distinction is exactly why Google, Facebook, and Amazon love this problem. It tests a specific cognitive skill: can you derive a non-obvious algorithm from first principles, under pressure, without knowing the answer?

The naive approach — generate all permutations in sorted order, find the current one, return the next — is O(n! · n) in time and O(n!) in space. It fails on any input larger than ~12 elements. The interviewee who jumps there first has revealed that they reach for brute force before thinking structurally.

The correct algorithm is three steps and runs in a single pass from the right. Every one of those three steps follows from asking a simple question. The goal of this post is to get you to the point where you could re-derive the algorithm on a whiteboard in five minutes, not just recite it.

Interview frequency: This exact problem or a close variant (previous permutation, k-th permutation) appears in roughly 1 in 8 FAANG array interviews according to Blind and LeetCode Discuss. Amazon and Google ask it most often, frequently as a medium-difficulty question where the in-place constraint is the real challenge.

Building the Algorithm From Scratch

Forget the three-step summary for a moment. Let us think from scratch.

The Core Question: Where Does the Next Permutation Differ?

Given [1, 2, 3], the next permutation is [1, 3, 2]. The first element (1) stays the same. Only the last two elements change. That is the key insight: to produce the next permutation, we want to change as few elements from the right as possible.

More precisely, we want to find the rightmost position where we can make an "upward" change — replace a digit with something larger — and then make everything to the right of that position as small as possible.

Step 1 — Why We Scan From the Right for the Pivot

Start from the right end of the array. Look for the first position i where nums[i] < nums[i + 1]. This is called the pivot.

Why from the right? Because the rightmost valid change causes the least disruption to the overall ordering. Changing the leftmost element would leapfrog billions of permutations in one step; changing a right-side element only advances by a handful.

More formally: everything to the right of any valid pivot is already in descending order (that is why the scan stopped there — we kept moving left past positions where nums[i] >= nums[i+1]). A fully descending suffix is the locally largest arrangement of those elements. There is nowhere to go from that suffix except to touch the element just to its left — the pivot.

If no such i exists (the entire array is descending), the array is already the largest permutation. The only move is to wrap to the smallest: reverse the whole array.

Step 2 — Why We Swap With the Smallest Element Larger Than the Pivot

Once we have the pivot at index i, we know we need to increase nums[i]. But by how much?

We want the smallest possible increase — that produces the permutation closest to the current one. Scan from the right to find the rightmost element in the suffix [i+1 ... n-1] that is strictly greater than nums[i]. Call its index j.

Why the rightmost such element? Because the suffix is in descending order, elements decrease as you go left. The rightmost element that beats nums[i] is the smallest one that does so. Swapping with any larger element would skip over permutations we have no right to skip.

Why strictly greater (not greater-or-equal)? Because swapping with an equal element produces an identical prefix, which gives a permutation that is not strictly greater than the current one.

After the swap, the prefix up to and including index i is now correctly advanced by the minimum amount.

Step 3 — Why We Reverse Instead of Sort the Suffix

After the swap, the suffix [i+1 ... n-1] still needs to be rearranged. We want it to be as small as possible — that is, in ascending order.

Here is the key observation that makes the O(n) solution possible: the suffix is still in descending order after the swap.

Why? Before the swap, the suffix was in descending order. The swap replaced nums[i] (the pivot) with nums[j] (the smallest element in the suffix larger than the pivot). This pushed nums[i] (which was smaller than everything in the suffix) into position j. Since nums[i] was smaller than everything in the suffix, inserting it at position j does not break the descending order of the suffix.

A descending sequence reversed becomes ascending. So instead of an O(n log n) sort, a single O(n) reverse pass is all we need.

The 3-Step Algorithm

After all that reasoning, the algorithm is a clean three-liner:

1. Find the pivot: Scan right-to-left; find the rightmost i where nums[i] < nums[i+1].
2. Find and swap the successor: Scan right-to-left from the end; find the rightmost j where nums[j] > nums[i]. Swap nums[i] and nums[j].
3. Reverse the suffix: Reverse the subarray from i+1 to the end.

If Step 1 finds no pivot (array is fully descending), skip Steps 2 and 3 and just reverse the entire array.

Edge Case: The Largest Permutation

When the array is in strictly descending order — e.g., [5, 4, 3, 2, 1] — every single position satisfies nums[i] >= nums[i+1]. The left-scan in Step 1 runs off the beginning of the array without finding a pivot.

This means the current arrangement is the last permutation. The problem specifies we must wrap around to the first permutation — the smallest, which is ascending order.

The correct handling: if no pivot is found (i.e., i < 0 after the scan), simply reverse the entire array. This converts descending to ascending in O(n) with no extra work.

Note: This is not a rare edge case. In an interview, explicitly stating it before coding signals strong problem-solving discipline.

Visual Dry Run

Trace 1: [1, 2, 3] → [1, 3, 2]

Array:  [1, 2, 3]
         0  1  2

Step 1 — Find pivot (scan right to left for nums[i] < nums[i+1]):
  i=1: nums[1]=2, nums[2]=3 → 2 < 3 ✓ → pivot = index 1

Step 2 — Find successor (rightmost element > nums[1]=2 in suffix [i+1..end]):
  Suffix is [3] (index 2 only)
  j=2: nums[2]=3 > 2 ✓ → j = 2
  Swap nums[1] and nums[2]: [1, 3, 2]

Step 3 — Reverse suffix from index i+1=2 to end:
  Suffix is [2] (single element) — reverse is a no-op
  
Result: [1, 3, 2] ✓

Trace 2: [3, 2, 1] → [1, 2, 3] (wrap-around case)

Array:  [3, 2, 1]
         0  1  2

Step 1 — Find pivot:
  i=1: nums[1]=2, nums[2]=1 → 2 >= 1, skip
  i=0: nums[0]=3, nums[1]=2 → 3 >= 2, skip
  i=-1: fell off the left edge — no pivot found

Step 2 — Skip (no pivot)

Step 3 — Reverse the ENTIRE array:
  [3, 2, 1] reversed → [1, 2, 3]

Result: [1, 2, 3] ✓

Trace 3: [1, 3, 2] → [2, 1, 3] (multi-element suffix swap)

Array:  [1, 3, 2]
         0  1  2

Step 1 — Find pivot:
  i=1: nums[1]=3, nums[2]=2 → 3 >= 2, skip
  i=0: nums[0]=1, nums[1]=3 → 1 < 3 ✓ → pivot = index 0

Step 2 — Find successor in suffix [3, 2] (indices 1, 2):
  j=2: nums[2]=2 > nums[0]=1 ✓ → j=2 (smallest in suffix larger than 1)
  Swap nums[0] and nums[2]: [2, 3, 1]

Step 3 — Reverse suffix from index i+1=1 to end:
  Suffix [3, 1] → reversed → [1, 3]
  Array: [2, 1, 3]

Result: [2, 1, 3] ✓

This third trace is important — it shows that after the swap, the suffix ([3, 1]) is still descending, confirming why a reverse (not a sort) works.

Common Mistakes

These four bugs appear in first-attempt solutions constantly. Knowing them ahead of time is worth at least 10 minutes saved in an interview.

Mistake 1: Scanning the Array From Left to Right in Step 1

Finding the leftmost position where nums[i] < nums[i+1] is wrong. You need the rightmost. Scanning left-to-right and stopping at the first ascending pair means you change a prefix element that was not the minimal-disruption choice. You will skip over many permutations that should appear between the current one and your result.

# WRONG
i = 0
while i < n - 1 and nums[i] < nums[i + 1]:
    i += 1

# CORRECT
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1

Mistake 2: Swapping the Pivot With the Wrong Element

A common error is swapping with the first element in the suffix that is larger than the pivot (scanning left-to-right), rather than the rightmost (scanning right-to-left). Because the suffix is in descending order, the first larger element from the left is also the largest — swapping with it makes the biggest possible jump, not the smallest.

# WRONG — finds leftmost (largest) element > pivot
j = i + 1
while j < n and nums[j] > nums[i]:
    j += 1
j -= 1

# CORRECT — finds rightmost (smallest) element > pivot
j = n - 1
while nums[j] <= nums[i]:
    j -= 1

Mistake 3: Sorting the Suffix Instead of Reversing It

Sorting the suffix at the end works and gives the right answer, but it costs O(n log n) instead of O(n). More importantly, it betrays that the candidate does not understand why the suffix is already structured for a reverse. The entire reason the reverse works is that the suffix is guaranteed to be descending — make sure you can explain that guarantee, not just apply a sort as a fallback.

# WORKS but O(n log n) — avoid in interviews
nums[i+1:] = sorted(nums[i+1:])

# CORRECT: O(n) reverse — suffix is already descending
left, right = i + 1, n - 1
while left < right:
    nums[left], nums[right] = nums[right], nums[left]
    left += 1
    right -= 1

Mistake 4: Not Handling the No-Pivot Case

Forgetting to check if i >= 0 before Step 2 leads to an index-out-of-bounds error or incorrect behavior on fully-descending inputs. Always guard:

if i >= 0:
    # Step 2: find j and swap
    ...
# Step 3 always runs (reverse from i+1 to end)
# When i = -1, i+1 = 0, so the whole array is reversed — correct!

Notice the elegant fall-through: when i = -1 (no pivot found), reversing from i+1 = 0 to the end reverses the entire array, which is exactly the wrap-around behavior needed. You do not need a special else branch — just let the reverse step handle both cases.

Solutions

Python

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Modifies nums in-place to the next lexicographic permutation.
        If already the largest permutation, wraps to the smallest (ascending).
        Time: O(n)  Space: O(1)
        """
        n = len(nums)

        # ── Step 1: Find the pivot ──────────────────────────────────────────
        # Scan right-to-left for the first index i where nums[i] < nums[i+1].
        # Everything to the right of i is in descending order (no room to grow).
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        # ── Step 2: Find and swap the successor ────────────────────────────
        # Only runs if a pivot was found (i >= 0).
        # Find the rightmost element in the suffix that is strictly > nums[i].
        # Because the suffix is descending, rightmost = smallest eligible element.
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            # Swap pivot with its smallest-valid successor
            nums[i], nums[j] = nums[j], nums[i]

        # ── Step 3: Reverse the suffix ─────────────────────────────────────
        # The suffix [i+1 ... n-1] is still in descending order after the swap.
        # Reversing it gives the smallest possible (ascending) arrangement.
        # When i == -1 (no pivot), this reverses the entire array → wrap-around.
        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

JavaScript

/**
 * Rearranges nums in-place to the next lexicographic permutation.
 * If already the largest permutation, wraps to ascending order.
 * Time: O(n)  Space: O(1)
 *
 * @param {number[]} nums
 * @return {void}
 */
var nextPermutation = function(nums) {
    const n = nums.length;

    // ── Step 1: Find the pivot ────────────────────────────────────────────
    // Scan right-to-left for the first index i where nums[i] < nums[i+1].
    // When found, the suffix [i+1...n-1] is confirmed to be descending.
    let i = n - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    // ── Step 2: Find and swap the successor ──────────────────────────────
    // Only execute if a pivot was found.
    // Scan right-to-left for the rightmost element strictly greater than nums[i].
    // Rightmost = smallest eligible in the descending suffix (minimum increase).
    if (i >= 0) {
        let j = n - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        // Swap: advance prefix by the smallest possible amount
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }

    // ── Step 3: Reverse the suffix ────────────────────────────────────────
    // Suffix is still descending after the swap. Reverse it to get ascending.
    // When i === -1, left = 0, so the entire array is reversed (wrap-around).
    let left = i + 1;
    let right = n - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
};

Complexity Analysis

The algorithm is optimal — you cannot find the pivot without examining each element at least once, and reversing a sequence requires visiting each element at least once. Both bounds are tight.

In practice the algorithm is fast: on already-sorted arrays, the pivot is found at n-2 (first step from the right), and only the last two elements are touched.

Follow-up Questions

1. Previous Permutation (LeetCode 1053)

The mirror image of this problem. Instead of finding the rightmost ascent, find the rightmost descent — the rightmost i where nums[i] > nums[i-1]. Then find the largest element to its right that is smaller than nums[i], swap, and reverse the suffix. All the same logic applies, just with the inequality directions flipped.

2. Permutation Sequence — k-th Permutation (LeetCode 60)

Given n and k, return the k-th permutation of [1, 2, ..., n] directly — without generating all permutations. The trick is factorial number system decomposition: at each position, there are (n-1)! permutations for each choice of the first digit. Use k // (n-1)! to pick the digit, update k = k % (n-1)!, and repeat. This is O(n²) and far more efficient than running nextPermutation k times.

3. All Permutations (LeetCode 46)

Generate every permutation of an array. The classical backtracking approach does this in O(n! · n). Alternatively, you can seed with the sorted array and call nextPermutation exactly n! - 1 times — useful as a teaching exercise but not the intended approach for LC 46.

4. Next Permutation With Duplicates (LeetCode 31 variant)

The standard algorithm already handles duplicates correctly because Step 1 uses strict inequality (nums[i] < nums[i+1], not <=) and Step 2 uses strict inequality (nums[j] > nums[i], not >=). This ensures we advance by exactly one permutation even when digits repeat.

This Pattern Solves

The "scan from the right, find the rightmost point of change, make the minimal adjustment, then normalize the remainder" pattern appears in several other problems:

Once you internalize the "rightmost change + normalize suffix" pattern, problems like LC 556 and LC 738 become immediate applications rather than separate puzzles to solve.

Key Takeaway

Next Permutation is not a memorization problem — it is a reasoning problem. The three-step algorithm falls out naturally from asking: where is the rightmost place I can make a minimal upward change? (find the pivot), what is the smallest valid swap partner? (find the successor), and how do I minimize everything to the right? (reverse the already-descending suffix).

The O(1) space, O(n) time solution is both provably optimal and elegant — but only if you understand why each step works. An interviewer who asks follow-up questions ("why reverse instead of sort?", "why rightmost and not leftmost?") is testing exactly that understanding. Walk through the reasoning above, and those questions become easy.

The single most important habit this problem teaches: scan from the right when you want to minimize disruption. That reflex surfaces in dozens of harder problems.