N-Queens

📋

Problem

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?

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

Edge cases: n = 1 → [['Q']]n = 2 → [] (no solutions)n = 3 → [] (no solutions)

</>

IDE

def solveNQueens(n: int) -> list:public List<List<String>> solveNQueens(int n)vector<vector<string>> solveNQueens(int n)function solveNQueens(n)

def solveNQueens(n):
    # Write your solution here
    pass

class Solution {
    public List<List<String>> solveNQueens(int n) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<string>> solveNQueens(int n) {
    // Write your solution here
    return {};
}

function solveNQueens(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [["Q...","Q...","Q...","Q..."]]Placing multiple queens in the same column or row without pruning.✅ Add checks to ensure only one queen per row and column; prune columns already used.

Wrong: [["....","....","....","...."]]Returning empty boards or not placing any queens.✅ Ensure backtracking places queens and appends valid boards to solutions.

Wrong: [[".Q..","Q...","..Q.","...Q"]]Incorrect diagonal conflict checks allowing attacking queens.✅ Check both major and minor diagonals for conflicts before placing a queen.

Wrong: Partial or fewer solutions than expected for n=8 or n=10Greedy approach or incomplete backtracking pruning.✅ Implement full backtracking with column and diagonal pruning to explore all solutions.

Wrong: Timeout or no output for n=10Inefficient brute force without pruning or memoization.✅ Use pruning of columns and diagonals and consider bitmask optimization to reduce complexity.

✓

Test Cases

Focus on handling smallest and no-solution cases correctly.

Watch out for common algorithmic traps like greedy placement or off-by-one errors.

Optimize your solution with pruning and efficient conflict detection to handle large inputs.

t1_01basic

Input4

Expected[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

⏱ Performance - must finish in 2000ms

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

💡 Try placing queens row by row and check conflicts.

💡 Use backtracking with pruning columns and diagonals.

💡 Track columns and diagonals to avoid invalid placements.

Why it failed: Incorrect output: likely missing some solutions or invalid placements. Fix by ensuring backtracking explores all valid columns per row and checks diagonal conflicts properly.

✓ Correctly found all distinct solutions for n=4.

t1_02basic

Input5

Expected[["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]

⏱ Performance - must finish in 2000ms

There are 10 distinct solutions for n=5 where no two queens attack each other.

💡 Extend the backtracking approach to n=5.

💡 Check all columns and prune invalid diagonals efficiently.

💡 Use sets or arrays to track columns and diagonals for pruning.

Why it failed: Output missing solutions or includes invalid boards. Fix by correctly pruning columns and diagonals and exploring all valid placements.

✓ Correctly found all 10 distinct solutions for n=5.

t2_01edge

Input1

Expected[["Q"]]

⏱ Performance - must finish in 2000ms

Only one queen on a 1x1 board; trivial solution.

💡 Check base case when n=1.

💡 Ensure your code handles smallest board correctly.

💡 Return [['Q']] immediately or via backtracking.

Why it failed: Fails to handle n=1 base case; returns empty or incorrect. Fix by adding base case or allowing single queen placement.

✓ Correctly returns single solution for n=1.

t2_02edge

Input2

Expected[]

⏱ Performance - must finish in 2000ms

No solutions exist for n=2 as queens always attack each other.

💡 Check if your code can detect no-solution cases.

💡 Backtracking should return empty list if no valid placements.

💡 Verify pruning logic does not falsely allow invalid boards.

Why it failed: Incorrectly returns solutions for n=2 where none exist. Fix pruning and validation logic to reject all invalid boards.

✓ Correctly returns empty list for n=2.

t2_03edge

Input3

Expected[]

⏱ Performance - must finish in 2000ms

No solutions exist for n=3 as queens always attack each other.

💡 Similar to n=2, ensure no invalid boards are returned.

💡 Check diagonal and column pruning carefully.

💡 Return empty list if no valid configurations found.

Why it failed: Returns invalid or partial solutions for n=3. Fix pruning to correctly identify no valid placements.

✓ Correctly returns empty list for n=3.

t3_01corner

Input8

Expectednull

⏱ Performance - must finish in 2000ms

Classic 8-queens problem with 92 distinct solutions.

💡 Avoid greedy placement; backtracking explores all options.

💡 Use column and diagonal pruning to reduce search space.

💡 Implement full backtracking, not greedy, to find all solutions.

Why it failed: Greedy approach returns fewer than 92 solutions. Fix by implementing full backtracking with pruning instead of greedy column selection.

✓ Correctly finds all 92 solutions for n=8.

t3_02corner

Input4

Expected[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

⏱ Performance - must finish in 2000ms

Test to catch confusion between 0/1 constraints and unbounded placement of queens.

💡 Each row must have exactly one queen, no repeats.

💡 Do not place multiple queens in the same row or column.

💡 Ensure backtracking places exactly one queen per row.

Why it failed: Allows multiple queens in one row or column. Fix by enforcing one queen per row and pruning columns already used.

✓ Correctly enforces one queen per row and column.

t3_03corner

Input5

Expected[["Q....","..Q..","....Q",".Q...","...Q."],["Q....","...Q.",".Q...","....Q","..Q.."],[".Q...","...Q.","Q....","..Q..","....Q"],[".Q...","....Q","..Q..","Q....","...Q."],["..Q..","Q....","...Q.",".Q...","....Q"],["..Q..","....Q",".Q...","...Q.","Q...."],["...Q.","Q....","..Q..","....Q",".Q..."],["...Q.",".Q...","....Q","..Q..","Q...."],["....Q",".Q...","...Q.","Q....","..Q.."],["....Q","..Q..","Q....","...Q.",".Q..."]]

⏱ Performance - must finish in 2000ms

Test to catch off-by-one errors in indexing or recursion depth.

💡 Check loop boundaries carefully for rows and columns.

💡 Ensure recursion stops exactly at row == n.

💡 Verify indexing when placing and removing queens.

Why it failed: Off-by-one error causes missing or extra solutions. Fix loop and recursion conditions to match 0-based indexing and stop at row == n.

✓ Correctly handles indexing and recursion depth.

t4_01performance

Input10

Expectednull

⏱ Performance - must finish in 2000ms

Test with n=10 to verify backtracking with pruning completes within time limit (O(n!)).

💡 Use pruning of columns and diagonals to reduce search space.

💡 Avoid recomputing conflicts by tracking columns and diagonals.

💡 Bitmask optimization can further speed up the solution.

Why it failed: TLE due to brute force without pruning or inefficient conflict checks. Fix by implementing column and diagonal pruning or bitmask optimization.

✓ Solution runs within time limit using pruning/backtracking.

Practice

1. You are given an array nums and multiple queries, each query containing two integers x and m. For each query, you want to find the maximum XOR of x with any element in nums that is less than or equal to m. Which algorithmic approach guarantees an optimal solution for large inputs?

easy

A. Greedy approach selecting the largest element less than or equal to m for XOR

B. Brute force nested loops checking all pairs for each query

C. Dynamic programming with memoization over all possible XOR values

D. Sorting nums and queries, then using a bitwise trie with offline queries and two pointers

Solution

1. Step 1: Understand problem constraints

   Brute force is too slow for large inputs; greedy fails because max element ≤ m does not guarantee max XOR.

2. Step 2: Identify optimal approach

   Sorting and offline queries allow incremental trie insertion of eligible elements, enabling efficient max XOR queries.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting + trie + offline queries is known optimal [OK]

Hint: Offline queries + trie + sorting -> optimal [OK]

Common Mistakes:

• Assuming greedy max element ≤ m yields max XOR
• Trying DP over XOR values
• Using brute force for large inputs

2. Given a string s and a string t, you need to find the smallest substring in s that contains all characters of t including duplicates. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with frequency counting and two pointers to expand and shrink the window

B. Brute force checking all substrings and verifying character counts

C. Dynamic programming to store minimum substrings ending at each index

D. Greedy approach by always picking the next occurrence of required characters

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the minimum window substring containing all characters of t in s. Checking all substrings (brute force) is too slow.

2. Step 2: Identify optimal approach

   Sliding window with frequency counting and two pointers allows expanding and shrinking the window efficiently, achieving O(n) time. DP or greedy approaches either don't guarantee minimal window or are inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with frequency counting is the classic optimal solution [OK]

Hint: Sliding window with frequency counting solves this optimally [OK]

Common Mistakes:

• Thinking brute force or greedy is efficient enough

3. What is the time complexity of the optimized recursive approach with global tracking for the Binary Tree Maximum Path Sum problem, assuming the tree has n nodes and height h?

medium

A. O(n^2) because at each node, sums of all paths in subtrees are computed

B. O(n \times h) due to recursive calls and path computations at each node

C. O(n) because each node is visited once and constant work is done per node

D. O(h) because recursion depth limits the number of calls

Solution

1. Step 1: Identify that each node is visited exactly once in the recursive traversal.

   The helper function is called once per node, doing constant work (max, addition) per call.

2. Step 2: Confirm that no nested loops or repeated subtree computations occur.

   The recursion does not recompute subtrees multiple times, so total work is proportional to n.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node -> O(n) [OK]

Hint: Each node processed once with constant work [OK]

Common Mistakes:

• Assuming O(n^2) due to path sums
• Confusing recursion depth with total calls
• Ignoring constant work per node

4. The following code attempts to implement the bidirectional BFS with state compression for the shortest path visiting all nodes problem. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

medium

A. Line updating next_mask in backward BFS: next_mask = mask & ~(1 << nei)

B. Line initializing visited1 dictionary

C. Line updating next_mask in forward BFS: next_mask = mask

D. Line checking if (node, mask) in visited2

Solution

1. Step 1: Analyze forward BFS mask update

   The forward BFS must update the visited mask to include the neighbor node: next_mask = mask | (1 << nei). The code incorrectly assigns next_mask = mask, missing the neighbor.

2. Step 2: Consequences of bug

   Without updating the mask, states do not reflect actual visited nodes, causing incorrect results or infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct bitmask update is critical for state correctness [OK]

Hint: Forward BFS must update visited mask to include neighbor [OK]

Common Mistakes:

• Forgetting to update bitmask when moving to neighbor
• Confusing forward and backward mask updates
• Not checking visited states properly

5. Suppose the skyline problem is extended so that buildings can overlap and have negative heights (representing underground structures). Which modification to the divide and conquer algorithm is necessary to correctly handle this variant?

hard

A. No modification needed; the existing merge logic works for negative heights

B. Modify the merge step to consider absolute values of heights when computing max height

C. Use a brute force height map simulation instead, as divide and conquer cannot handle negative heights

D. Adjust the merge step to track both max and min heights at each x-coordinate and merge accordingly

Solution

1. Step 1: Understand negative height impact

   Negative heights mean skyline can go below ground, so max height alone is insufficient.

2. Step 2: Modify merge logic

   Need to track both max and min heights to merge skylines correctly, handling positive and negative overlaps.

3. Step 3: Evaluate options

   Ignoring negative heights or using absolute values breaks correctness; brute force is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Tracking both max and min heights handles negative overlaps correctly [OK]

Hint: Negative heights require tracking min as well as max heights [OK]

Common Mistakes:

• Assuming negative heights can be handled as positive
• Ignoring negative heights in merge logic
• Switching to brute force unnecessarily