How do you solve Queens That Can Attack the King on LeetCode?

Queens That Can Attack the King (LeetCode #1222) 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: Queens can attack in straight lines and diagonals.

What is the brute force solution for Queens That Can Attack the King?

The brute force approach for Queens That Can Attack the King is Brute Force, with O(n²) time complexity and O(1) space complexity. In this approach, we check each queen's position to see if it can attack the king. This means checking all eight possible directions from the king's position to see if any queen lies directly in line with it. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Queens That Can Attack the King?

Queens That Can Attack the King uses the following concepts: Array, Matrix, Simulation. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Queens That Can Attack the King?

Think about the chessboard's geometry. Optimize by checking only necessary positions. Practice visualizing the problem with diagrams.

What are common mistakes when solving Queens That Can Attack the King?

Not considering all eight directions. Failing to stop checking once a queen is found.

#1222

Queens That Can Attack the King

Medium

ArrayMatrixSimulationHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Instead of checking all queens, we can check only the closest queen in each of the eight possible attacking directions. This reduces unnecessary checks and improves efficiency.

⚙️

Algorithm

5 steps

1Step 1: Create a set to store the positions of queens for quick lookup.
2Step 2: Define the eight possible directions (up, down, left, right, and the four diagonals).
3Step 3: For each direction, move step by step until hitting a queen or going out of bounds.
4Step 4: If a queen is found, add its position to the result list.
5Step 5: Return the list of attacking queens.

solution.py13 lines

1def queensAttacktheKing(queens, king):
2    directions = [(1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
3    attacking_queens = []
4    queens_set = set(map(tuple, queens))
5    for dx, dy in directions:
6        x, y = king
7        while 0 <= x < 8 and 0 <= y < 8:
8            if (x, y) in queens_set:
9                attacking_queens.append([x, y])
10                break
11            x += dx
12            y += dy
13    return attacking_queens

ℹ

Complexity note: This complexity is due to the need to store queens in a set for quick access, and we only check in eight directions, making it linear with respect to the number of queens.

1Queens can attack in straight lines and diagonals.
2Only the closest queen in each direction matters.

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