Next Permutation

📋

Next Permutation

Edge cases:

</>

IDE

def next_permutation(nums: list[int]) -> None:public void nextPermutation(int[] nums)void nextPermutation(vector<int>& nums)function nextPermutation(nums)

def next_permutation(nums):
    # Write your solution here
    pass

class Solution {
    public void nextPermutation(int[] nums) {
        // Write your solution here
    }
}

#include <vector>
using namespace std;

void nextPermutation(vector<int>& nums) {
    // Write your solution here
}

function nextPermutation(nums) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1,2,3]No change made when next permutation exists; missed pivot detection.✅ Scan from right to left to find first decreasing element as pivot; swap and reverse suffix.

Wrong: [3,2,1]Always reversing entire array regardless of pivot; ignoring pivot swap step.✅ Only reverse suffix after swapping pivot with next larger element.

Wrong: [1,3,2,3]Swapping pivot with wrong element or not reversing suffix after swap.✅ Swap pivot with next larger element strictly greater than pivot; then reverse suffix.

Wrong: [5,4,3,2,1]Failing to reverse entire array when no pivot found (highest permutation).✅ If no pivot found, reverse entire array to get lowest permutation.

Wrong: TLE or timeoutUsing brute force generating all permutations for large n.✅ Implement O(n) pivot-swap-reverse algorithm instead of brute force.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly before moving on.

Review your algorithm for common pitfalls like greedy mistakes and indexing errors.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"nums":[2,1,3]}

Expectednull

⏱ Performance - must finish in 2000ms

The next permutation after [1,2,3] is [1,3,2].

💡 Think about finding the first decreasing element from the right.

💡 Use the suffix scan to find the pivot and swap with the next larger element.

💡 Reverse the suffix after the pivot to get the next permutation.

Why it failed: Output incorrect - likely missed finding the pivot or reversing suffix. Fix by scanning from right to left to find first decreasing element, swap with next larger, then reverse suffix.

✓ Correct next permutation computed using pivot and suffix reversal.

t1_02basic

Input{"nums":[2,1,3,3]}

Expectednull

⏱ Performance - must finish in 2000ms

Next permutation after [1,3,2,3] is [1,3,3,2], swapping pivot 2 with 3 and reversing suffix.

💡 Check for duplicates when finding the pivot and next larger element.

💡 Pivot is the first element from right that is smaller than its successor.

💡 Swap pivot with next larger element and reverse suffix after pivot.

Why it failed: Incorrect output - likely failed to handle duplicates correctly when swapping or reversing suffix. Fix by ensuring swap is with next larger element strictly greater than pivot.

✓ Correctly handles duplicates and computes next permutation.

t2_01edge

Input{"nums":[1]}

Expectednull

⏱ Performance - must finish in 2000ms

Single element array has only one permutation; next permutation is itself.

💡 Consider the smallest input size and what next permutation means here.

💡 No pivot can be found in a single element array.

💡 Return the array as is since no next permutation exists.

Why it failed: Incorrect output - likely code assumes at least two elements to find pivot. Fix by handling single element arrays by returning input unchanged.

✓ Correctly returns single element array unchanged.

t2_02edge

Input{"nums":[2,2,2]}

Expectednull

⏱ Performance - must finish in 2000ms

All elements equal means no lexicographically larger permutation; output is same array.

💡 Check if all elements are equal or no pivot found.

💡 If no pivot, reverse entire array (which is same here).

💡 Result is the same array since all permutations are identical.

Why it failed: Incorrect output - likely code tries to swap pivot but none exists. Fix by reversing entire array if no pivot found, which results in same array here.

✓ Correctly returns same array when all elements equal.

t2_03edge

Input{"nums":[1,2,3,5,4]}

Expectednull

⏱ Performance - must finish in 2000ms

Strictly descending order is highest permutation; next is lowest ascending order.

💡 If no pivot found, reverse entire array to get lowest permutation.

💡 Descending order means no lexicographically larger permutation.

💡 Reverse array to get ascending order as next permutation.

Why it failed: Incorrect output - likely code fails to reverse entire array when no pivot found. Fix by reversing whole array if pivot not found.

✓ Correctly reverses descending array to ascending order.

t2_04edge

Input{"nums":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Empty array input should return empty array as no permutations exist.

💡 Check for empty input and handle gracefully.

💡 No pivot or swap possible in empty array.

💡 Return empty array unchanged.

Why it failed: Incorrect output - likely code does not handle empty input. Fix by returning input unchanged if empty.

✓ Correctly handles empty input by returning empty array.

t3_01corner

Input{"nums":[1,1,5]}

Expectednull

⏱ Performance - must finish in 2000ms

Greedy trap: swapping wrong element leads to incorrect next permutation; correct pivot is index 0, swap with 5, reverse suffix.

💡 Beware of greedy mistakes picking wrong pivot or swap candidate.

💡 Pivot is first decreasing element from right, not just any smaller element.

💡 Swap pivot with next larger element and reverse suffix after pivot.

Why it failed: Greedy trap: swapping wrong element or not reversing suffix leads to incorrect output. Fix by correctly identifying pivot and swapping with next larger element, then reversing suffix.

✓ Correctly avoids greedy trap and computes next permutation.

t3_02corner

Input{"nums":[1,2,4,1,3,2,3]}

Expectednull

⏱ Performance - must finish in 2000ms

Handles suffix with duplicates correctly; pivot at index 2 (3), swap with 4, reverse suffix.

💡 Check suffix scanning carefully when duplicates exist.

💡 Pivot is first decreasing element from right; swap with next larger element.

💡 Reverse suffix after pivot to get next permutation.

Why it failed: Incorrect output due to mishandling duplicates in suffix or wrong pivot selection. Fix by scanning suffix correctly and reversing after pivot swap.

✓ Correctly handles duplicates in suffix and computes next permutation.

t3_03corner

Input{"nums":[3,2,1]}

Expectednull

⏱ Performance - must finish in 2000ms

Off-by-one error test: pivot at index 0, swap with 3, reverse suffix [1] to get [3,1,2].

💡 Check indexing carefully when finding pivot and swap candidate.

💡 Pivot is first decreasing element from right; swap with next larger element.

💡 Reverse suffix after pivot to get next permutation.

Why it failed: Off-by-one error causes wrong pivot or swap index. Fix by carefully indexing from right and reversing suffix correctly.

✓ Correctly handles indexing and computes next permutation.

t4_01performance

Input{"nums":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(n) time complexity expected; brute force O(n!) will TLE.

💡 Brute force generating all permutations is infeasible for n=100.

💡 Use O(n) approach: find pivot, swap, reverse suffix.

💡 In-place modification with two pointers and suffix reversal is optimal.

Why it failed: TLE due to brute force factorial complexity. Fix by implementing O(n) pivot-swap-reverse algorithm.

✓ Efficient O(n) solution passes performance test.

Practice

1. You need to generate all unique permutations of an array that may contain duplicate elements. Which approach guarantees generating all unique permutations efficiently without producing duplicates during generation?

easy

A. Use a greedy algorithm that picks the smallest unused element at each step.

B. Use backtracking with sorting and a mechanism to skip duplicates during recursion.

C. Use dynamic programming to build permutations from smaller subproblems.

D. Generate all permutations and then filter duplicates using a hash set.

Solution

1. Step 1: Understand the problem constraints

   The problem requires generating all unique permutations of an array with duplicates, so duplicates must be avoided during generation to be efficient.

2. Step 2: Evaluate approaches

   Greedy algorithms do not guarantee all permutations; DP is not suitable here; generating all permutations and filtering duplicates is correct but inefficient. Backtracking with sorting and skipping duplicates during recursion ensures duplicates are pruned early.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with duplicate skipping is the standard optimal approach [OK]

Hint: Skip duplicates during backtracking after sorting [OK]

Common Mistakes:

• Thinking greedy or DP can generate unique permutations efficiently

2. Consider the following code snippet implementing the optimal backtracking solution for Word Search. Given the board = [["A","B","C"],["D","E","F"],["G","H","I"]] and word = "BEF", what is the return value of exist(board, word)?

easy

A. True

B. False

C. Raises IndexError

D. Infinite recursion

Solution

1. Step 1: Trace dfs starting at cell (0,1) 'B'

   Word starts with 'B', found at (0,1). dfs(0,1,0) matches 'B'.

2. Step 2: Explore neighbors for next chars 'E' and 'F'

   From (0,1), neighbors checked: (1,1) 'E' matches next char, then (1,2) 'F' matches last char. All matched, return True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   All characters found sequentially with valid moves [OK]

Hint: Trace dfs calls carefully to confirm path exists [OK]

Common Mistakes:

• Assuming no path due to adjacency confusion
• Missing in-place marking effect

3. Consider the following buggy code for generating letter combinations. Which line contains the subtle bug that causes incorrect or incomplete results?

from collections import deque

def letterCombinations(digits):
    if digits == '':
        return ['']
    digit_map = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
                 '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
    queue = deque([''])
    for digit in digits:
        letters = digit_map[digit]
        for _ in range(len(queue)):
            prev = queue.popleft()
            for char in letters:
                queue.append(prev + char)
    return list(queue)

medium

A. Line 7: letters = digit_map[digit]

B. Line 2: if digits == '': return ['']

C. Line 10: prev = queue.popleft()

D. Line 1: from collections import deque

Solution

1. Step 1: Analyze empty input handling

   Returning [''] for empty input is incorrect; the problem expects an empty list [] when input is empty.

2. Step 2: Check other lines

   Digit mapping, queue operations, and imports are correct and do not cause bugs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Empty input should return [] not [''] to match problem spec [OK]

Hint: Empty input must return empty list, not list with empty string [OK]

Common Mistakes:

• Returning [''] instead of [] for empty input
• Assuming digits '1' or '0' map to letters

4. Examine the following code snippet for the Word Search II problem. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line: currNode = node.children.get(letter)

B. Line: Missing marking of board[r][c] as visited before recursion

C. Line: if currNode.word:

D. Line: board[r][c] = letter at the end

Solution

1. Step 1: Identify visited marking necessity

   Backtracking requires marking the current cell as visited (e.g., replacing letter with '#') to avoid revisiting the same cell in the current path.

2. Step 2: Locate missing visited marking

   The code lacks the line that marks board[r][c] as visited before recursive calls, causing revisits and potential infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without visited marking, recursion revisits same cells [OK]

Hint: Visited marking prevents revisiting same cell in recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells or unmark after recursion.

5. Suppose the N-Queens problem is modified so that queens can be placed multiple times in the same column (i.e., column constraint is relaxed), but diagonal attacks still apply. Which modification to the bitmask backtracking algorithm correctly adapts to this variant?

hard

A. Remove the column bitmask tracking and only track diagonal attacks in recursion

B. Keep column bitmask but allow multiple queens by resetting it each row

C. Use a greedy approach placing queens in any column without pruning

D. Track columns as before but ignore diagonal bitmasks

Solution

1. Step 1: Understand relaxed constraints

   Since columns can have multiple queens, column bitmask is no longer needed to prune placements.

2. Step 2: Adapt pruning to only diagonal attacks

   Keep diag1 and diag2 bitmasks to prune diagonal conflicts, but remove column mask from available_positions calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Removing column mask allows multiple queens per column while still pruning diagonals [OK]

Hint: Relaxed constraints remove column pruning, keep diagonal pruning [OK]

Common Mistakes:

• Resetting column mask each row incorrectly
• Ignoring diagonal pruning
• Using greedy without pruning