N-Queens

▶

Steps

setup

Start Backtracking at Row 0

The algorithm begins at row 0 with empty board and no columns or diagonals attacked (cols=0, diag1=0, diag2=0).

💡 Starting with no queens placed means all columns are available for the first queen placement.

Line:

backtrack(0, 0, 0, 0)

💡 Initial call sets the stage for recursive exploration of queen placements row by row.

fill_cells

Calculate Available Positions at Row 0

Compute available_positions by negating attacked columns and diagonals and masking with (1 << n) - 1 to keep only n bits.

💡 This bitmask shows which columns in row 0 are safe to place a queen.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 All columns are available initially since no attacks exist.

insert

Place Queen at Row 0, Column 0

Extract rightmost 1-bit from available_positions to place queen at column 0, update board and bitmasks accordingly.

💡 Choosing the leftmost available column first is a systematic way to explore all options.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask operations efficiently select the next column to try without scanning all bits.

traverse

Recurse to Row 1 with Updated Bitmasks

Call backtrack for row 1, updating cols, diag1, diag2 to mark attacks from queen at (0,0).

💡 Updating bitmasks propagates attack constraints to the next row.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 Bitmasks track attacked columns and diagonals compactly, enabling fast pruning.

fill_cells

Calculate Available Positions at Row 1

Compute available_positions for row 1 considering attacks from previous queen placements.

💡 This step shows which columns are safe for the queen in row 1.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Bitmask shows only columns 2 and 3 are free at row 1.

insert

Place Queen at Row 1, Column 2

Select rightmost available bit (column 2) to place queen, update board and bitmasks.

💡 Systematic choice of next available column continues the search.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask extraction efficiently picks the next column without iteration.

traverse

Recurse to Row 2 with Updated Bitmasks

Call backtrack for row 2 with updated cols, diag1, diag2 reflecting attacks from queens at (0,0) and (1,2).

💡 Bitmasks propagate constraints to the next row to prune invalid placements.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion deepens with updated attack masks narrowing available columns.

fill_cells

Calculate Available Positions at Row 2

Compute available_positions for row 2 considering attacks from queens placed so far.

💡 This shows which columns are safe for the queen in row 2.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Only column 1 is available at row 2 after pruning.

insert

Place Queen at Row 2, Column 1

Place queen at column 1, update board and bitmasks accordingly.

💡 Placing queen at the only available column continues the search.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask operations continue to efficiently select positions.

traverse

Recurse to Row 3 with Updated Bitmasks

Call backtrack for row 3 with updated bitmasks reflecting attacks from queens placed so far.

💡 Constraints propagate to the last row to find valid placements.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion reaches the last row with updated constraints.

fill_cells

Calculate Available Positions at Row 3

Compute available_positions for row 3 considering attacks from queens placed so far.

💡 This determines if a queen can be placed in row 3.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Only column 3 is available at row 3.

insert

Place Queen at Row 3, Column 3

Place queen at column 3, update board and bitmasks.

💡 Placing queen at the only available column completes a valid solution.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 This placement leads to a complete valid solution.

reconstruct

Record Complete Solution at Row 4

Reached base case row == n, record current board configuration as a valid solution.

💡 Base case signals a full valid placement of queens on the board.

Line:

if row == n:
    solutions.append([''.join(r) for r in board])
    return

💡 The algorithm successfully found one of the two solutions for n=4.

delete

Backtrack from Row 3, Try Next Position

Remove queen from (3,3) and try next available positions at row 3 (none left), so backtrack further.

💡 Backtracking removes last queen to explore alternative placements.

Line:

board[row][col] = '.'

💡 Backtracking systematically explores all options by undoing previous choices.

delete

Backtrack from Row 2, Try Next Position

Remove queen from (2,1), try next available positions at row 2 (none left), backtrack to row 1.

💡 Backtracking continues to explore all possible queen placements.

Line:

board[row][col] = '.'

💡 Backtracking ensures no valid solution is missed.

insert

Place Queen at Row 1, Column 3

Try next available position at row 1: column 3, update board and bitmasks.

💡 Exploring alternative queen placements at row 1.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Backtracking explores all branches by trying all available positions.

traverse

Recurse to Row 2 with Updated Bitmasks (Second Branch)

Call backtrack for row 2 with updated bitmasks from queens at (0,0) and (1,3).

💡 Constraints update for new queen placement to prune invalid positions.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion explores a new branch with different constraints.

fill_cells

Calculate Available Positions at Row 2 (Second Branch)

Compute available_positions for row 2 with updated bitmasks.

💡 Shows which columns are safe for queen placement in this branch.

Line:

available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))

💡 Only column 1 is available at row 2 in this branch.

insert

Place Queen at Row 2, Column 1 (Second Branch)

Place queen at column 1, update board and bitmasks.

💡 Placing queen at the only available column continues the search.

Line:

position = available_positions & (-available_positions)
available_positions &= available_positions - 1
col = (position & -position).bit_length() - 1
board[row][col] = 'Q'

💡 Bitmask operations continue to efficiently select positions.

traverse

Recurse to Row 3 (Second Branch)

Call backtrack for row 3 with updated bitmasks from queens at (0,0), (1,3), (2,1).

💡 Constraints update for last row to find valid placements.

Line:

backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)

💡 The recursion explores the last row in this branch.

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

    def backtrack(row, cols, diag1, diag2):
        if row == n:  # STEP 13: base case, record solution
            solutions.append([''.join(r) for r in board])
            return
        available_positions = ((1 << n) - 1) & (~(cols | diag1 | diag2))  # STEP 2,5,8,11,18
        while available_positions:
            position = available_positions & (-available_positions)  # STEP 3,6,9,12,16,19
            available_positions &= available_positions - 1  # STEP 3,6,9,12,16,19
            col = (position & -position).bit_length() - 1
            board[row][col] = 'Q'  # STEP 3,6,9,12,16,19
            backtrack(row + 1, cols | position, (diag1 | position) << 1, (diag2 | position) >> 1)  # STEP 4,7,10,13,17,20
            board[row][col] = '.'  # STEP 14,15

    backtrack(0, 0, 0, 0)  # STEP 1
    return solutions

if __name__ == '__main__':
    print(solveNQueens(4))

📊

N-Queens - Watch the Algorithm Execute, Step by Step

Watching each recursive call and bitmask update reveals how the algorithm efficiently prunes invalid queen placements and backtracks to find all solutions.

enteringrow=0cols=0diag1=0diag2=0

Call Path (current → root)

backtrack(row=0, cols=0, diag1=0, diag2=0)

choosingrow=0cols=0diag1=0diag2=0

Call Path (current → root)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b1111

choosingrow=0cols=0diag1=0diag2=0

Call Path (current → root)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0001

Remaining

0b1110

Partial: [(0,0)]

enteringrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0)]

choosingrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b1100

Partial: [(0,0)]

choosingrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0100

Remaining

0b1000

Partial: [(0,0), (1,2)]

enteringrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,2)]

choosingrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b0010

Partial: [(0,0), (1,2)]

choosingrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0010

Partial: [(0,0), (1,2), (2,1)]

enteringrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,2), (2,1)]

choosingrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b1000

Partial: [(0,0), (1,2), (2,1)]

choosingrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b1000

Partial: [(0,0), (1,2), (2,1), (3,3)]

backtrackingrow=4cols=15diag1=36diag2=1

Call Path (current → root)

backtrack(row=4, cols=15, diag1=36, diag2=1)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,2), (2,1), (3,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

backtrackingrow=3cols=7diag1=18diag2=0

Call Path (current → root)

backtrack(row=3, cols=7, diag1=18, diag2=0)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b1000

Partial: [(0,0), (1,2), (2,1)]

Found 1: [.Q..,...Q,Q...,..Q.]

backtrackingrow=2cols=5diag1=8diag2=1

Call Path (current → root)

backtrack(row=2, cols=5, diag1=8, diag2=1)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0010

Partial: [(0,0), (1,2)]

Found 1: [.Q..,...Q,Q...,..Q.]

choosingrow=1cols=1diag1=2diag2=0

Call Path (current → root)

backtrack(row=1, cols=1, diag1=2, diag2=0)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b01000b1000

Partial: [(0,0), (1,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

enteringrow=2cols=9diag1=20diag2=1

Call Path (current → root)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

choosingrow=2cols=9diag1=20diag2=1

Call Path (current → root)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Remaining

0b0010

Partial: [(0,0), (1,3)]

Found 1: [.Q..,...Q,Q...,..Q.]

choosingrow=2cols=9diag1=20diag2=1

Call Path (current → root)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Tried

0b0010

Partial: [(0,0), (1,3), (2,1)]

Found 1: [.Q..,...Q,Q...,..Q.]

enteringrow=3cols=11diag1=44diag2=0

Call Path (current → root)

backtrack(row=3, cols=11, diag1=44, diag2=0)

backtrack(row=2, cols=9, diag1=20, diag2=1)

backtrack(row=1, cols=9, diag1=20, diag2=1)

backtrack(row=0, cols=0, diag1=0, diag2=0)

Partial: [(0,0), (1,3), (2,1)]

Found 1: [.Q..,...Q,Q...,..Q.]

Key Takeaways

✓ Bitmasking efficiently tracks attacked columns and diagonals, enabling fast pruning of invalid queen placements.

This insight is hard to see from code alone because bitwise operations are compact and non-intuitive without visualization.

✓ The recursion tree shows how the algorithm explores each row, tries all available columns, and backtracks when no options remain.

Visualizing each recursive call clarifies the systematic search and pruning process.

✓ Solutions are collected only at the base case when all rows have queens placed, demonstrating how partial answers build up to complete solutions.

Understanding when and how solutions are recorded is clearer when watching the recursion unfold step-by-step.

Practice

1. You need to design a cache system that evicts the least frequently used items first, and among those with the same frequency, evicts the least recently used. Which algorithmic approach best guarantees optimal eviction behavior for this problem?

easy

A. Maintain frequency counts and timestamps for each item, evicting the item with the lowest frequency and oldest timestamp when needed.

B. Sort all cache items by their values and evict the item with the smallest value when capacity is full.

C. Use a standard LRU cache eviction policy based on recency only, ignoring frequency counts.

D. Use a simple FIFO queue to evict the oldest inserted item when capacity is reached.

Solution

1. Step 1: Understand eviction criteria

   The problem requires evicting the least frequently used item first, and if multiple items share the same frequency, evict the least recently used among them.

2. Step 2: Identify approach that tracks frequency and recency

   Only an approach that maintains both frequency counts and timestamps can correctly identify the LFU and LRU items for eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Eviction based on frequency and recency -> correct LFU cache behavior [OK]

Hint: LFU needs frequency + recency tracking [OK]

Common Mistakes:

• Confusing LFU with LRU eviction policy
• Using FIFO which ignores frequency
• Sorting by value instead of usage metrics

2. What is the time complexity of the optimal Alien Dictionary solution using Kahn's algorithm with early cycle detection and edge deduplication, given C as the total number of characters in all words and U as the number of unique characters?

medium

A. O(C log U) due to sorting characters during graph construction

B. O(U^2) due to checking all pairs of characters

C. O(C * U) because each character is compared with all unique characters

D. O(C + U + E) where E is number of edges, since graph construction and BFS visit all characters and edges once

Solution

1. Step 1: Analyze graph construction cost

   Each adjacent word pair is compared up to min length, total comparisons proportional to total characters C.

2. Step 2: Analyze topological sort cost

   BFS visits each node (U) and each edge (E) once; E ≤ C since edges come from character comparisons.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall complexity O(C + U + E) matches linear graph traversal [OK]

Hint: Graph traversal cost dominates, not pairwise character comparisons [OK]

Common Mistakes:

• Assuming quadratic due to character pairs
• Confusing edges with nodes
• Forgetting BFS linearity

3. Consider the following buggy LFUCache code snippet. Which line contains the subtle bug that causes incorrect eviction behavior?

def put(self, key: int, value: int) -> None:
    if self.capacity == 0:
        return
    self.time += 1
    if key in self.cache:
        _, freq, _ = self.cache[key]
        self.cache[key] = (value, freq + 1, self.time)
        return
    if len(self.cache) == self.capacity:
        min_freq = min(freq for _, freq, _ in self.cache.values())
        lfu_keys = [k for k, (_, freq, _) in self.cache.items() if freq == min_freq]
        lru_key = min(lfu_keys, key=lambda k: self.cache[k][2])
        del self.cache[lru_key]
    self.cache[key] = (value, 1, self.time)

medium

A. Missing update of minimum frequency after eviction

B. Line: self.cache[key] = (value, freq + 1, self.time) when key exists

C. Line: min_freq = min(freq for _, freq, _ in self.cache.values())

D. Line: self.time += 1

Solution

1. Step 1: Identify eviction and frequency update

   The code evicts the LFU and LRU key correctly but does not update any variable tracking the minimum frequency after eviction.

2. Step 2: Understand impact of missing minFreq update

   Without updating minFreq, subsequent evictions or frequency increments may behave incorrectly, evicting wrong keys.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing minFreq update causes eviction errors [OK]

Hint: Eviction needs minFreq update to maintain correctness [OK]

Common Mistakes:

• Assuming eviction alone suffices
• Updating frequency but not minFreq
• Confusing time increment with frequency update

4. What is the time complexity of the optimized approach that uses sorting, offline queries, and a bitwise trie for the Maximum XOR With Element From Array problem, given n elements in nums and q queries, assuming 32-bit integers?

medium

A. O((n + q) * log(maxNum))

B. O((n + q) * 32)

C. O(n * log(maxNum) * q)

D. O(n * q)

Solution

1. Step 1: Analyze sorting and offline queries

   Sorting nums and queries takes O(n log n + q log q), dominated by O((n + q) log (n + q)) which is less than main complexity.

2. Step 2: Analyze trie operations

   Each insertion and query takes O(log(maxNum)) = O(32) for 32-bit integers. Total insertions = n, total queries = q.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Combined complexity is O((n + q) * log(maxNum)) [OK]

Hint: Trie ops per element and query scale with log(maxNum) [OK]

Common Mistakes:

• Confusing n*q brute force with optimized approach
• Ignoring log(maxNum) factor
• Assuming linear time per query

5. Suppose the problem is modified so that nodes can be revisited multiple times without penalty, but the goal remains to visit all nodes at least once with the shortest path length. Which modification to the bidirectional BFS with state compression algorithm is necessary to handle this variant correctly?

hard

A. Remove the visited bitmask and track only the current node in BFS states

B. Modify the bitmask to track the count of visits per node instead of a binary visited flag

C. Use a simple BFS without bitmask since revisits are allowed and shortest path is trivial

D. Keep the visited bitmask but allow revisiting states with the same mask and node multiple times

Solution

1. Step 1: Understand problem change

   Allowing multiple revisits without penalty means the visited state must track how many times each node is visited if that affects path validity.

2. Step 2: Modify state representation

   Binary bitmask is insufficient; need to track counts per node, e.g., using a vector or multi-bit encoding per node, to correctly represent states and avoid incorrect pruning.

3. Step 3: Implication on BFS

   State space grows, but correctness requires this richer state representation to find shortest path under new rules.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting visits per node is necessary when revisits are allowed without penalty [OK]

Hint: Bitmask alone can't track multiple visits; need counts per node [OK]

Common Mistakes:

• Removing bitmask entirely loses track of visited nodes
• Allowing revisits without state changes causes incorrect pruning
• Assuming simple BFS suffices without state tracking