How do you solve N-Queens II on LeetCode?

N-Queens II (LeetCode #52) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n!) time complexity and O(n) space complexity. Key insight: Backtracking is a powerful technique for solving constraint satisfaction problems like N-Queens.

What is the brute force solution for N-Queens II?

The brute force approach for N-Queens II is Brute Force, with O(n!) time complexity and O(n) space complexity. The brute force approach involves generating all possible arrangements of queens on the board and checking each arrangement to see if it is valid. This method is straightforward but inefficient, as it explores many invalid configurations. The optimal Optimal Solution approach improves this to O(n!).

What algorithm or data structure is used to solve N-Queens II?

N-Queens II uses the following concepts: Backtracking. The recommended patterns to study are: Backtracking, Recursion.

What are the interview tips for N-Queens II?

Explain your thought process clearly while coding; it shows your understanding. Be prepared to discuss the trade-offs between different approaches. Practice writing clean, efficient code, as readability is important in interviews.

What are common mistakes when solving N-Queens II?

Failing to backtrack correctly, which can lead to incorrect counts. Not considering diagonal attacks when checking for valid placements.

#52

N-Queens II

Hard

BacktrackingBacktrackingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n!)	O(n!)
Space	O(n)	O(n)

💡

Intuition

Time O(n!)Space O(n)

The optimal solution uses backtracking with pruning to efficiently explore possible placements of queens. By keeping track of columns and diagonals that are already attacked, we can skip invalid placements and reduce the search space significantly.

⚙️

Algorithm

4 steps

1Step 1: Use a recursive function to place queens row by row.
2Step 2: Maintain arrays to track columns and diagonals that are under attack.
3Step 3: For each row, try placing a queen in each column and recursively place queens in the next row.
4Step 4: If a valid configuration is found, increment the solution count.

solution.py20 lines

1# Full working Python code
2class Solution:
3    def totalNQueens(self, n: int) -> int:
4        def backtrack(row, cols, diag1, diag2):
5            if row == n:
6                return 1
7            count = 0
8            for col in range(n):
9                if col in cols or (row - col) in diag1 or (row + col) in diag2:
10                    continue
11                cols.add(col)
12                diag1.add(row - col)
13                diag2.add(row + col)
14                count += backtrack(row + 1, cols, diag1, diag2)
15                cols.remove(col)
16                diag1.remove(row - col)
17                diag2.remove(row + col)
18            return count
19
20        return backtrack(0, set(), set(), set())

ℹ

Complexity note: The time complexity remains O(n!) due to the nature of the problem, but we significantly reduce the number of checks by using sets to track attacked columns and diagonals. The space complexity is O(n) for the recursion stack and the sets.

1Backtracking is a powerful technique for solving constraint satisfaction problems like N-Queens.
2Using sets to track attacked columns and diagonals can significantly reduce the number of checks needed.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.