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 combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. You are given a string containing only digits. Your task is to split it into exactly four parts such that each part represents a valid IP address segment (0 to 255, no leading zeros except for '0'). Which algorithmic approach guarantees finding all valid IP addresses efficiently?

easy

A. Sorting the digits and then partitioning into four segments

B. Greedy approach that picks the shortest valid segment at each step

C. Dynamic programming to count the number of valid segmentations

D. Backtracking with pruning to explore all valid segmentations

Solution

1. Step 1: Understand the problem constraints

   The problem requires enumerating all valid IP addresses, which involves exploring multiple segmentations of the string.

2. Step 2: Evaluate algorithm suitability

   Greedy approaches fail because they may miss valid segmentations; DP counting does not generate all solutions; sorting digits destroys original order. Backtracking with pruning systematically explores all valid partitions.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Backtracking explores all partitions with pruning to avoid invalid segments [OK]

Hint: Backtracking explores all segmentations with pruning [OK]

Common Mistakes:

• Assuming greedy can find all valid IPs
• Using DP counting without generating solutions

3. Consider the following snippet from an optimized Sudoku solver using backtracking with heuristics. Given the board below, what is the length of candidates for the first empty cell chosen after sorting empties by candidate count? Board: [['5', '3', '.', '.', '7', '.', '.', '.', '.'], ['6', '.', '.', '1', '9', '5', '.', '.', '.'], ['.', '9', '8', '.', '.', '.', '.', '6', '.'], ['8', '.', '.', '.', '6', '.', '.', '.', '3'], ['4', '.', '.', '8', '.', '3', '.', '.', '1'], ['7', '.', '.', '.', '2', '.', '.', '.', '6'], ['.', '6', '.', '.', '.', '.', '2', '8', '.'], ['.', '.', '.', '4', '1', '9', '.', '.', '5'], ['.', '.', '.', '.', '8', '.', '.', '7', '9']] Code snippet:

def get_candidates(r, c):
    b = (r//3)*3 + c//3
    return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
first_empty = empties[0]
candidates_len = len(get_candidates(first_empty[0], first_empty[1]))

What is the value of candidates_len?

easy

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Identify first empty cell after sorting

   Check empties and compute candidates for each; the cell with fewest candidates is chosen first.

2. Step 2: Calculate candidates for first empty cell (0,2)

   Row 0 has {'5','3','7'}, column 2 has {'8'}, box 0 has {'5','3','6','9','8'}. Candidates are digits not in any of these sets: '1','2','4'. So length is 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Counting candidates for (0,2) yields 3 [OK]

Hint: Count candidates by excluding row, column, box digits [OK]

Common Mistakes:

• Forgetting box constraints
• Miscounting candidates for first empty cell

4. Examine the following buggy code snippet for Expression Add Operators. Which line contains the subtle bug that causes incorrect results on inputs with leading zeros?

def addOperators(num: str, target: int) -> List[str]:
    res = []
    path = []
    def backtrack(index: int, evaluated: int, last_operand: int):
        if index == len(num):
            if evaluated == target:
                res.append(''.join(path))
            return
        for i in range(index, len(num)):
            # Bug: missing leading zero check
            curr_str = num[index:i+1]
            curr = int(curr_str)
            length_before = len(path)
            if index == 0:
                path.append(curr_str)
                backtrack(i+1, curr, curr)
                path[length_before:] = []
            else:
                path.append('+'); path.append(curr_str)
                backtrack(i+1, evaluated + curr, curr)
                path[length_before:] = []
    backtrack(0, 0, 0)
    return res

medium

A. Line with 'if i != index and num[index] == '0':' missing here

B. Line with 'curr_str = num[index:i+1]' (substring extraction)

C. Line with 'path[length_before:] = []' (backtracking cleanup)

D. Line with 'path.append('+'); path.append(curr_str)' (operator insertion)

Solution

1. Step 1: Identify handling of leading zeros

   The code lacks the check 'if i != index and num[index] == '0': break' which prevents invalid operands like "05".

2. Step 2: Confirm bug location

   This missing check is critical and should be placed before parsing curr_str to avoid invalid expressions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing leading zero check causes invalid operands [OK]

Hint: Leading zero check missing causes invalid operands [OK]

Common Mistakes:

• Confusing backtracking cleanup lines as bug
• Thinking substring extraction is buggy

5. Consider the following code snippet intended to generate unique permutations of an array with duplicates. Which line contains a subtle bug that causes duplicate permutations to be generated?

def permuteUnique(nums):
    nums.sort()
    res = []
    def backtrack(start=0):
        if start == len(nums):
            res.append(nums[:])
            return
        for i in range(start, len(nums)):
            if i > start and nums[i] == nums[i-1]:
                continue
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
    backtrack()
    return res

medium

A. Line with 'if i > start and nums[i] == nums[i-1]: continue' (duplicate skipping condition)

B. Line with 'nums.sort()' (sorting input before recursion)

C. Line with 'nums[start], nums[i] = nums[i], nums[start]' before recursion (swap)

D. Line with 'for i in range(start, len(nums)):' (iteration over indices)

Solution

1. Step 1: Analyze duplicate skipping condition

   The condition 'if i > start and nums[i] == nums[i-1]: continue' attempts to skip duplicates but does not consider whether the previous duplicate was used, causing some duplicates to be missed.

2. Step 2: Verify other lines

   Sorting input is correct; swapping before and after recursion is correct; iteration over indices is standard. The bug is in the duplicate skipping logic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect duplicate skipping causes duplicate permutations [OK]

Hint: Skipping duplicates requires tracking usage, not just comparing adjacent elements [OK]

Common Mistakes:

• Skipping duplicates by only comparing adjacent elements without usage tracking