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 are given a numeric string and a target integer. You need to insert binary operators (+, -, *) between digits to form expressions that evaluate to the target. Which algorithmic approach guarantees finding all valid expressions efficiently while handling operator precedence and avoiding invalid operands like those with leading zeros?

easy

A. Backtracking with pruning and careful operand parsing to explore all operator insertions

B. Breadth-first search enumerating all possible expressions without pruning

C. Dynamic programming that stores sub-expression results without operator precedence handling

D. Greedy approach that inserts operators at fixed intervals without backtracking

Solution

1. Step 1: Understand problem requirements

   The problem requires exploring all ways to insert operators to reach a target, respecting operator precedence and avoiding invalid operands like those with leading zeros.

2. Step 2: Identify suitable algorithm

   Backtracking with pruning and operand parsing systematically explores all valid expressions, correctly handles precedence (especially multiplication), and prunes invalid paths early.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid expressions with pruning [OK]

Hint: Backtracking explores all operator insertions with pruning [OK]

Common Mistakes:

• Assuming greedy or DP can handle operator precedence and invalid operands

2. You need to count all distinct ways to place n queens on an nxn chessboard so that no two queens threaten each other. Which algorithmic approach guarantees finding all valid solutions efficiently by exploring partial placements and pruning invalid ones early?

easy

A. Backtracking that tries all column placements per row and abandons invalid partial boards

B. Greedy algorithm that places queens row by row choosing the first safe column

C. Dynamic programming that stores counts of valid queen placements per row without conflict checks

D. Breadth-first search enumerating all board states level by level

Solution

1. Step 1: Understand problem constraints

   The problem requires counting all valid queen placements with no conflicts, which demands exploring all possibilities.

2. Step 2: Identify suitable algorithm

   Backtracking systematically tries each column per row and abandons partial solutions that violate constraints, ensuring correctness and pruning search space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Backtracking explores all valid configurations efficiently [OK]

Hint: Counting all valid placements requires backtracking [OK]

Common Mistakes:

• Assuming greedy placement always works
• Believing DP without conflict checks suffices

3. Given the following code for next permutation, what is the content of the array nums after calling next_permutation([1, 3, 2])?

easy

A. [1, 2, 3]

B. [2, 3, 1]

C. [2, 1, 3]

D. [1, 3, 2]

Solution

1. Step 1: Trace the pivot search

   Start with i = 1 (index of 3). Since nums[1]=3 >= nums[2]=2, decrement i to 0. nums[0]=1 < nums[1]=3, so pivot i=0.

2. Step 2: Find j to swap with pivot

   Start j=2 (value 2). nums[2]=2 > nums[0]=1, so j=2. Swap nums[0] and nums[2]: array becomes [2,3,1]. Then reverse suffix from i+1=1 to end: reverse [3,1] -> [1,3]. Final array: [2,1,3].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Array changes from [1,3,2] to [2,1,3] after next permutation [OK]

Hint: Pivot found at first decreasing from right, swap and reverse suffix [OK]

Common Mistakes:

• Swapping with wrong element
• Not reversing suffix after swap

4. You are given a 2D grid of letters and a list of words. You need to find all words that can be formed by sequentially adjacent letters (horizontally or vertically) without reusing the same cell in a single word. Which algorithmic approach best guarantees an efficient solution for this problem?

easy

A. Use dynamic programming to store subproblems of partial word matches.

B. Use a greedy search that picks the next letter with the highest frequency in the grid.

C. Use backtracking combined with a Trie data structure to prune invalid prefixes early.

D. Search each word independently using DFS without any prefix pruning.

Solution

1. Step 1: Understand problem constraints

   The problem requires searching multiple words in a grid with adjacency and no reuse constraints, which is expensive if done naively.

2. Step 2: Identify efficient pruning technique

   Backtracking with a Trie allows pruning search paths early when no word prefix matches, avoiding redundant searches.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Trie pruning reduces search space drastically compared to naive DFS [OK]

Hint: Trie + backtracking prunes invalid prefixes early [OK]

Common Mistakes:

• Thinking greedy or DP alone can solve adjacency constraints efficiently.

5. 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