N-Queens

🎯

N-Queens

hardBACKTRACKINGAmazonFacebookGoogle

Imagine you are organizing a chess tournament and need to place n queens on an n×n chessboard so that no two queens threaten each other. How can you arrange them safely?

💡 This is a classic backtracking problem where you try to place queens row by row, checking constraints. Beginners struggle because the search space is huge and pruning invalid positions efficiently is key.

📋

Problem Statement

Given an integer n, return all distinct solutions to the n-queens puzzle. Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively. No two queens can attack each other horizontally, vertically, or diagonally.

1 ≤ n ≤ 10Output all distinct solutions in any order

💡

Example

Input"4"

Output[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

There are two distinct ways to place 4 queens so that none attack each other.

• n = 1 → [['Q']]
• n = 2 → [] (no solutions)
• n = 3 → [] (no solutions)
• n = 8 → multiple solutions (classic chessboard size)

⚠️

Common Mistakes

Not checking diagonal conflicts correctly

Invalid solutions with attacking queens are included

✅ Check both diagonals using row-col and row+col indices

Modifying board without backtracking (not resetting)

Subsequent recursive calls see corrupted board state

✅ Reset board cell to '.' after recursive call returns

Using global variables without resetting between test cases

Solutions accumulate incorrectly or cause errors

✅ Initialize all data structures inside the main function or reset before each run

Incorrect bitmask operations (e.g., wrong shifts)

Missed or extra attacks cause wrong pruning and wrong answers

✅ Use correct left shift for one diagonal and right shift for the other

Not handling n < 1 or trivial cases

Code may crash or return incorrect results

✅ Add base case checks for n=1 or invalid inputs

🧠

Brute Force (Pure Recursion with Board Validation)

💡 This approach tries every possible placement of queens on the board and checks if the board is valid after each placement. It is slow but helps understand the problem deeply.

Intuition

Place queens row by row, and for each row try every column. After placing a queen, check if the board is still valid by scanning all previously placed queens.

Algorithm

1. Start from the first row.
2. Try placing a queen in each column of the current row.
3. After placing, check if the board is valid (no two queens attack).
4. If valid, recurse to the next row; if all rows are placed, record the solution.

💡 The main challenge is the validation step after each placement, which is costly and repeated many times.

</>

Code

def solveNQueens(n):
    def is_valid(board, row, col):
        for i in range(row):
            for j in range(n):
                if board[i][j] == 'Q':
                    if j == col or abs(row - i) == abs(col - j):
                        return False
        return True

    def backtrack(row, board, solutions):
        if row == n:
            solutions.append([''.join(r) for r in board])
            return
        for col in range(n):
            board[row][col] = 'Q'
            if is_valid(board, row, col):
                backtrack(row + 1, board, solutions)
            board[row][col] = '.'

    board = [['.' for _ in range(n)] for _ in range(n)]
    solutions = []
    backtrack(0, board, solutions)
    return solutions

# Example usage:
if __name__ == '__main__':
    print(solveNQueens(4))

Line Notes

def is_valid(board, row, col):Defines a helper to check if placing a queen at (row, col) is safe

for i in range(row):Check all previously placed queens in rows above current row

if j == col or abs(row - i) == abs(col - j):Check same column or diagonal conflicts

if row == n:Base case: all rows have queens placed, record solution

import java.util.*;
public class NQueensBrute {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
        backtrack(0, board, solutions, n);
        return solutions;
    }

    private void backtrack(int row, char[][] board, List<List<String>> solutions, int n) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            solutions.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            board[row][col] = 'Q';
            if (isValid(board, row, col, n)) {
                backtrack(row + 1, board, solutions, n);
            }
            board[row][col] = '.';
        }
    }

    private boolean isValid(char[][] board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'Q') {
                    if (j == col || Math.abs(row - i) == Math.abs(col - j)) return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        NQueensBrute solver = new NQueensBrute();
        System.out.println(solver.solveNQueens(4));
    }
}

Line Notes

public List<List<String>> solveNQueens(int n)Entry point to solve the problem and store solutions

for (int col = 0; col < n; col++)Try placing queen in each column of current row

if (isValid(board, row, col, n))Check if current placement is safe before recursing

if (row == n)All queens placed, add current board to solutions

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;
        vector<string> board(n, string(n, '.'));
        backtrack(0, board, solutions, n);
        return solutions;
    }

private:
    void backtrack(int row, vector<string>& board, vector<vector<string>>& solutions, int n) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            board[row][col] = 'Q';
            if (isValid(board, row, col, n)) {
                backtrack(row + 1, board, solutions, n);
            }
            board[row][col] = '.';
        }
    }

    bool isValid(const vector<string>& board, int row, int col, int n) {
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'Q') {
                    if (j == col || abs(row - i) == abs(col - j)) return false;
                }
            }
        }
        return true;
    }
};

int main() {
    Solution sol;
    auto res = sol.solveNQueens(4);
    for (auto& board : res) {
        for (auto& row : board) cout << row << endl;
        cout << endl;
    }
    return 0;
}

Line Notes

vector<string> board(n, string(n, '.'))Initialize board with '.' indicating empty cells

for (int col = 0; col < n; col++)Try placing queen in each column of current row

if (isValid(board, row, col, n))Validate placement before deeper recursion

if (row == n)All queens placed, add current board to solutions

function solveNQueens(n) {
    const solutions = [];
    const board = Array.from({ length: n }, () => '.'.repeat(n).split(''));

    function isValid(row, col) {
        for (let i = 0; i < row; i++) {
            for (let j = 0; j < n; j++) {
                if (board[i][j] === 'Q') {
                    if (j === col || Math.abs(row - i) === Math.abs(col - j)) return false;
                }
            }
        }
        return true;
    }

    function backtrack(row) {
        if (row === n) {
            solutions.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            board[row][col] = 'Q';
            if (isValid(row, col)) {
                backtrack(row + 1);
            }
            board[row][col] = '.';
        }
    }

    backtrack(0);
    return solutions;
}

// Example usage:
console.log(solveNQueens(4));

Line Notes

const board = Array.from({ length: n }, () => '.'.repeat(n).split(''))Initialize 2D board with '.' for empty cells

for (let col = 0; col < n; col++)Try placing queen in each column of current row

if (isValid(row, col))Check if current placement is safe before recursing

if (row === n)All queens placed, add current board to solutions

⏱

Complexity

TimeO(n! * n)

SpaceO(n^2)

We try placing queens row by row, each row has up to n columns. Checking validity takes O(n) per placement, leading to factorial time in worst case.

💡 For n=4, this means roughly 4! * 4 = 96 operations, which is manageable, but for n=10 it explodes to millions.

Interview Verdict: TLE for large n, but good for understanding

This approach is too slow for big boards but is essential to grasp the problem and backtracking basics.

🧠

Backtracking with Column and Diagonal Pruning

💡 This approach improves brute force by tracking columns and diagonals where queens are already placed, avoiding repeated scanning of the board.

Intuition

Instead of scanning the entire board to check conflicts, keep sets or arrays to mark attacked columns and diagonals, so checking is O(1).

Algorithm

1. Initialize sets to track attacked columns, and two diagonals (row-col and row+col).
2. Place queens row by row, skipping columns that are attacked.
3. When placing a queen, mark the column and diagonals as attacked.
4. Backtrack by unmarking after recursive calls; record solutions when all rows are placed.

💡 The key is to avoid scanning the board repeatedly by using extra data structures to track attacks.

</>

Code

def solveNQueens(n):
    solutions = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row):
        if row == n:
            solutions.append([''.join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1)
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    backtrack(0)
    return solutions

# Example usage:
if __name__ == '__main__':
    print(solveNQueens(4))

Line Notes

cols = set()Tracks columns already occupied by queens

diag1 = set() # row - colTracks one diagonal direction to detect attacks

if col in cols or (row - col) in diag1 or (row + col) in diag2:Skip positions attacked by any queen

cols.add(col)Mark column as attacked when placing a queen

import java.util.*;
public class NQueensPruned {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> solutions = new ArrayList<>();
        Set<Integer> cols = new HashSet<>();
        Set<Integer> diag1 = new HashSet<>();
        Set<Integer> diag2 = new HashSet<>();
        char[][] board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
        backtrack(0, n, board, cols, diag1, diag2, solutions);
        return solutions;
    }

    private void backtrack(int row, int n, char[][] board, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2, List<List<String>> solutions) {
        if (row == n) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            solutions.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;
            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            backtrack(row + 1, n, board, cols, diag1, diag2, solutions);
            board[row][col] = '.';
            cols.remove(col);
            diag1.remove(row - col);
            diag2.remove(row + col);
        }
    }

    public static void main(String[] args) {
        NQueensPruned solver = new NQueensPruned();
        System.out.println(solver.solveNQueens(4));
    }
}

Line Notes

Set<Integer> cols = new HashSet<>()Tracks columns with queens for O(1) conflict checks

if (cols.contains(col) || diag1.contains(row - col) || diag2.contains(row + col)) continue;Skip attacked positions quickly

cols.add(col);Mark column as attacked when placing queen

cols.remove(col);Unmark column when backtracking

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> solutions;
        vector<string> board(n, string(n, '.'));
        unordered_set<int> cols, diag1, diag2;
        backtrack(0, n, board, cols, diag1, diag2, solutions);
        return solutions;
    }

private:
    void backtrack(int row, int n, vector<string>& board, unordered_set<int>& cols, unordered_set<int>& diag1, unordered_set<int>& diag2, vector<vector<string>>& solutions) {
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col)) continue;
            board[row][col] = 'Q';
            cols.insert(col);
            diag1.insert(row - col);
            diag2.insert(row + col);
            backtrack(row + 1, n, board, cols, diag1, diag2, solutions);
            board[row][col] = '.';
            cols.erase(col);
            diag1.erase(row - col);
            diag2.erase(row + col);
        }
    }
};

int main() {
    Solution sol;
    auto res = sol.solveNQueens(4);
    for (auto& board : res) {
        for (auto& row : board) cout << row << endl;
        cout << endl;
    }
    return 0;
}

Line Notes

unordered_set<int> cols, diag1, diag2;Use hash sets for constant time conflict checks

if (cols.count(col) || diag1.count(row - col) || diag2.count(row + col)) continue;Skip invalid positions immediately

cols.insert(col);Mark column attacked when placing queen

cols.erase(col);Unmark column when backtracking

function solveNQueens(n) {
    const solutions = [];
    const cols = new Set();
    const diag1 = new Set(); // row - col
    const diag2 = new Set(); // row + col
    const board = Array.from({ length: n }, () => '.'.repeat(n).split(''));

    function backtrack(row) {
        if (row === n) {
            solutions.push(board.map(r => r.join('')));
            return;
        }
        for (let col = 0; col < n; col++) {
            if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
            board[row][col] = 'Q';
            cols.add(col);
            diag1.add(row - col);
            diag2.add(row + col);
            backtrack(row + 1);
            board[row][col] = '.';
            cols.delete(col);
            diag1.delete(row - col);
            diag2.delete(row + col);
        }
    }

    backtrack(0);
    return solutions;
}

console.log(solveNQueens(4));

Line Notes

const cols = new Set();Track attacked columns efficiently

if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;Skip invalid queen placements quickly

cols.add(col);Mark column attacked when placing queen

cols.delete(col);Remove column attack mark when backtracking

⏱

Complexity

TimeO(n!)

SpaceO(n)

Pruning reduces the number of invalid placements checked, so time is roughly factorial but faster than brute force. Space is O(n) for sets and recursion stack.

💡 For n=8, this approach can find solutions in under a second, unlike brute force which would be too slow.

Interview Verdict: Accepted and efficient for typical interview constraints

This is the standard approach to code in interviews for N-Queens due to its efficiency and clarity.

🧠

Bitmask Optimization for N-Queens

💡 This approach uses bitmasks to represent columns and diagonals, enabling very fast conflict checks and minimal memory usage, suitable for larger n.

Intuition

Represent columns and diagonals as bits in integers. Use bitwise operations to quickly find free positions and update attacks.

Algorithm

1. Use three integers to track attacked columns, and two diagonals.
2. At each row, compute available positions by bitwise negation and AND.
3. Iterate over available positions by extracting the rightmost set bit.
4. Place queen, update bitmasks with bitwise OR and shifts, recurse.
5. Backtrack by restoring bitmasks; record solutions when done.

💡 Bitmasking reduces overhead of sets and arrays, making conflict checks O(1) and iteration over candidates very fast.

</>

Code

def solveNQueens(n):
    solutions = []
    board = [['.' for _ in range(n)] for _ in range(n)]

    def backtrack(row, cols, diag1, diag2):
        if row == n:
            solutions.append([''.join(r) for r in board])
            return
        available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))
        while available_positions:
            position = available_positions & (-available_positions)  # rightmost 1-bit
            available_positions &= available_positions - 1  # remove rightmost 1-bit
            col = (position & -position).bit_length() - 1
            board[row][col] = 'Q'
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)
            board[row][col] = '.'

    backtrack(0, 0, 0, 0)
    return solutions

# Example usage:
if __name__ == '__main__':
    print(solveNQueens(4))

Line Notes

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))Calculate free columns by masking attacked positions

position = available_positions & (-available_positions)Extract rightmost free position to try

col = (position & -position).bit_length() - 1Convert bitmask position to column index

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)Update attacked columns and diagonals for next row

import java.util.*;
public class NQueensBitmask {
    private List<List<String>> solutions = new ArrayList<>();
    private int size;
    private char[][] board;

    public List<List<String>> solveNQueens(int n) {
        size = n;
        board = new char[n][n];
        for (int i = 0; i < n; i++) Arrays.fill(board[i], '.');
        backtrack(0, 0, 0, 0);
        return solutions;
    }

    private void backtrack(int row, int cols, int diag1, int diag2) {
        if (row == size) {
            List<String> solution = new ArrayList<>();
            for (char[] r : board) solution.add(new String(r));
            solutions.add(solution);
            return;
        }
        int availablePositions = ((1 << size) - 1) & ~(cols | diag1 | diag2);
        while (availablePositions != 0) {
            int position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            int col = Integer.numberOfTrailingZeros(position);
            board[row][col] = 'Q';
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);
            board[row][col] = '.';
        }
    }

    public static void main(String[] args) {
        NQueensBitmask solver = new NQueensBitmask();
        System.out.println(solver.solveNQueens(4));
    }
}

Line Notes

int availablePositions = ((1 << size) - 1) & ~(cols | diag1 | diag2);Calculate free columns using bitmasking

int position = availablePositions & (-availablePositions);Extract rightmost free bit to try

int col = Integer.numberOfTrailingZeros(position);Convert bitmask to column index

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);Update attacked columns and diagonals for next row

#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        size = n;
        board = vector<string>(n, string(n, '.'));
        backtrack(0, 0, 0, 0);
        return solutions;
    }

private:
    int size;
    vector<string> board;
    vector<vector<string>> solutions;

    void backtrack(int row, int cols, int diag1, int diag2) {
        if (row == size) {
            solutions.push_back(board);
            return;
        }
        int availablePositions = ((1 << size) - 1) & (~(cols | diag1 | diag2));
        while (availablePositions) {
            int position = availablePositions & (-availablePositions);
            availablePositions &= availablePositions - 1;
            int col = __builtin_ctz(position);
            board[row][col] = 'Q';
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);
            board[row][col] = '.';
        }
    }
};

int main() {
    Solution sol;
    auto res = sol.solveNQueens(4);
    for (auto& board : res) {
        for (auto& row : board) cout << row << endl;
        cout << endl;
    }
    return 0;
}

Line Notes

int availablePositions = ((1 << size) - 1) & (~(cols | diag1 | diag2));Calculate free columns using bitmasking

int position = availablePositions & (-availablePositions);Extract rightmost free bit to try

int col = __builtin_ctz(position);Count trailing zeros to get column index

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);Update attacked columns and diagonals for next row

function solveNQueens(n) {
    const solutions = [];
    const board = Array.from({ length: n }, () => '.'.repeat(n).split(''));

    function backtrack(row, cols, diag1, diag2) {
        if (row === n) {
            solutions.push(board.map(r => r.join('')));
            return;
        }
        let availablePositions = ((1 << n) - 1) & ~(cols | diag1 | diag2);
        while (availablePositions) {
            let position = availablePositions & -availablePositions;
            availablePositions &= availablePositions - 1;
            let col = Math.log2(position);
            board[row][col] = 'Q';
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);
            board[row][col] = '.';
        }
    }

    backtrack(0, 0, 0, 0);
    return solutions;
}

console.log(solveNQueens(4));

Line Notes

let availablePositions = ((1 << n) - 1) & ~(cols | diag1 | diag2);Calculate free columns using bitmasking

let position = availablePositions & -availablePositions;Extract rightmost free bit to try

let col = Math.log2(position);Convert bitmask to column index using log2

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1);Update attacked columns and diagonals for next row

⏱

Complexity

TimeO(n!)

SpaceO(n)

Bitmasking reduces overhead and speeds up pruning, but the search space remains factorial. Space is minimal due to integer bitmasks.

💡 This approach can handle n up to 14 or 15 efficiently, beyond what sets or arrays can do comfortably.

Interview Verdict: Accepted and fastest approach for large n

Bitmasking is an advanced optimization often appreciated in interviews for demonstrating mastery of bitwise operations.

📊

All Approaches - One-Glance Tradeoffs

💡 The pruning approach (Approach 2) is the best balance of clarity and efficiency for interviews.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n! * n)	O(n^2)	Yes (deep recursion)	Yes	Mention only - never code
2. Backtracking with Column and Diagonal Pruning	O(n!)	O(n)	Yes (deep recursion)	Yes	Code this approach in interviews
3. Bitmask Optimization	O(n!)	O(n)	Yes (deep recursion)	Yes	Mention or code if comfortable with bitwise ops

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force approach to show understanding of the problem.Step 3: Introduce pruning with sets to optimize validation.Step 4: If comfortable, discuss bitmask optimization for further speed.Step 5: Code the pruning approach as it balances clarity and efficiency.Step 6: Test with edge cases and explain complexity.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Optimize: 7min. Total ~30min

What the Interviewer Tests

Ability to implement backtracking correctly, optimize pruning, use data structures effectively, and reason about complexity.

Common Follow-ups

• How to count the total number of solutions without storing them? → Use a counter instead of storing boards.
• Can you solve for n > 15 efficiently? → Bitmasking is required for performance.
• How to modify for N-Rooks or other pieces? → Adjust attack rules accordingly.
• Can you output one valid solution instead of all? → Stop recursion after first solution.

💡 These follow-ups test your flexibility with the algorithm and understanding of backtracking variations.

🔍

Pattern Recognition

When to Use

1) Need to place items on a grid with constraints; 2) Constraints involve rows, columns, diagonals; 3) Search space is large; 4) Backtracking with pruning is needed.

Signature Phrases

place n queensno two queens attackdistinct board configurations

NOT This Pattern When

Problems that only require greedy or DP without backtracking, e.g., coin change or LIS.

Similar Problems

Sudoku Solver - similar constraint satisfaction with backtrackingWord Search - backtracking on grid with path constraintsKnight's Tour - path finding with constraints on chessboard

Practice

1. You need to find the k-th lexicographically smallest permutation of numbers from 1 to n. Which approach guarantees an optimal solution without generating all permutations explicitly?

easy

A. Use a greedy algorithm that swaps elements to reach the k-th permutation directly.

B. Compute factorial values to determine each digit's position and build the permutation directly.

C. Use dynamic programming to count permutations and reconstruct the k-th sequence.

D. Generate all permutations using backtracking and return the k-th one.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the k-th permutation without enumerating all permutations, which is infeasible for large n.

2. Step 2: Identify the approach that uses factorial number system

   Using precomputed factorials, we can determine the index of each digit in the permutation directly, avoiding full enumeration.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Factorial-based direct computation is optimal and avoids timeouts [OK]

Hint: Factorials let you jump directly to the k-th permutation [OK]

Common Mistakes:

• Thinking greedy swaps can find k-th permutation efficiently
• Assuming DP is needed here
• Trying to generate all permutations for large n

2. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

3. You are given a string containing parentheses and letters. The goal is to remove the minimum number of parentheses to make the string valid (balanced parentheses) and return all possible results. Which algorithmic approach guarantees finding all valid strings with the minimum removals efficiently?

easy

A. Greedy approach that removes invalid parentheses from left to right without backtracking

B. Dynamic Programming that counts valid substrings and reconstructs solutions

C. Breadth-First Search (BFS) that explores all strings by removing one parenthesis at a time level-by-level

D. Brute force generating all subsequences and checking validity

Solution

1. Step 1: Understand problem constraints

   The problem requires minimal removals and all valid results, so partial or greedy removal may miss some minimal solutions.

2. Step 2: Analyze BFS approach

   BFS explores all strings by removing one parenthesis at a time, level-by-level, ensuring the first valid strings found have minimal removals and all such strings are collected.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   BFS guarantees minimal removals and completeness [OK]

Hint: Minimal removals require level-by-level BFS [OK]

Common Mistakes:

• Greedy misses some minimal solutions
• Brute force is correct but inefficient
• DP doesn't apply directly here

4. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

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