Problem Description

You have an 8x8 chessboard (0-indexed) with multiple black queens and one white king placed on it.

Given:

• queens: A 2D array where queens[i] = [xQueen_i, yQueen_i] represents the position of the i-th black queen
• king: An array of length 2 where king = [xKing, yKing] represents the position of the white king

Your task is to find all black queens that can directly attack the king.

In chess, a queen can attack any piece that lies in the same row, column, or diagonal (in any of the 8 directions: up, down, left, right, and the four diagonal directions). However, a queen cannot attack through another piece - if there's another queen blocking the path between an attacking queen and the king, only the closest queen to the king in that direction can attack.

The solution works by:

1. Storing all queen positions in a set for quick lookup
2. From the king's position, searching outward in all 8 possible directions (represented by direction vectors where a and b range from -1 to 1)
3. For each direction, moving step by step until either:
   • A queen is found (add it to the answer and stop searching in that direction)
   • The edge of the board is reached
4. Only the first queen encountered in each direction can attack the king, as it would block any queens behind it

Return the coordinates of all queens that can attack the king. The order of the returned coordinates doesn't matter.

Intuition

The key insight is to think from the king's perspective rather than checking each queen individually. Instead of asking "which queens can attack the king?", we ask "what can the king see in each direction?"

Think about standing at the king's position and looking outward in all 8 directions. In each direction, you can only be attacked by the first queen you encounter - any queens behind that first one are blocked. This is similar to shining a flashlight in each direction from the king's position; the light stops at the first queen it hits.

This leads us to the approach of radiating outward from the king's position. We need to check all 8 directions: horizontal (left, right), vertical (up, down), and diagonal (4 diagonal directions). These directions can be represented by direction vectors (a, b) where both a and b range from -1 to 1, excluding (0, 0) which represents no movement.

For each direction, we keep moving one square at a time (x + a, y + b) until we either:

• Find a queen - this queen can attack the king, so we record it and stop looking further in that direction
• Hit the edge of the board - no queen can attack from this direction

By using a set to store queen positions, we can check in O(1) time whether a square contains a queen as we traverse each direction. This is much more efficient than checking every queen against every possible attacking path.

The maximum number of queens that can attack the king is 8 (one from each direction), and we only need to traverse at most 7 squares in each direction on an 8x8 board, making this approach very efficient.

Solution Approach

The implementation follows a direct search strategy from the king's position:

Step 1: Store Queen Positions

s = {(i, j) for i, j in queens}

We create a set s containing tuples of queen positions. Using a set gives us O(1) lookup time to check if a position contains a queen.

Step 2: Generate Direction Vectors

for a in range(-1, 2):
    for b in range(-1, 2):
        if a or b:

We iterate through all possible direction combinations where a and b can be -1, 0, or 1. This gives us 9 combinations, but we skip (0, 0) using the condition if a or b, leaving us with 8 valid directions:

• (-1, -1): upper-left diagonal
• (-1, 0): up
• (-1, 1): upper-right diagonal
• (0, -1): left
• (0, 1): right
• (1, -1): lower-left diagonal
• (1, 0): down
• (1, 1): lower-right diagonal

Step 3: Search in Each Direction

x, y = king
while 0 <= x + a < n and 0 <= y + b < n:
    x, y = x + a, y + b
    if (x, y) in s:
        ans.append([x, y])
        break

For each direction:

• Start from the king's position (x, y)
• Keep moving in the direction (a, b) by updating x = x + a and y = y + b
• Check boundary conditions 0 <= x + a < n and 0 <= y + b < n to ensure we stay on the board
• If we find a queen at position (x, y) (checked using (x, y) in s):
  • Add this queen's position to our answer list
  • Break out of the while loop since this queen blocks any other queens behind it in this direction
• If we reach the board's edge without finding a queen, the while loop ends naturally

Step 4: Return Results The algorithm returns all queens that can directly attack the king. The maximum size of the answer is 8 (one queen from each direction).

Time Complexity: O(1) - Since the board size is fixed at 8×8, we check at most 8 directions × 7 squares = 56 positions.

Space Complexity: O(Q) where Q is the number of queens, for storing the queen positions in the set.

Example Walkthrough

Let's work through a small example on a 5x5 board (for simplicity) with the king at position [2, 2] and queens at positions [[0, 0], [0, 2], [1, 1], [3, 4], [4, 2]].

Step 1: Visualize the Board

  0 1 2 3 4
0 Q . Q . .
1 . Q . . .
2 . . K . .
3 . . . . Q
4 . . Q . .

Step 2: Create Queen Position Set

s = {(0, 0), (0, 2), (1, 1), (3, 4), (4, 2)}

Step 3: Search from King's Position in All 8 Directions

Starting from king at [2, 2], we check each direction:

1. Direction (-1, -1) (upper-left diagonal):

   • Move to [1, 1] → Found queen! Add [1, 1] to answer and stop.

2. Direction (-1, 0) (up):

   • Move to [1, 2] → No queen
   • Move to [0, 2] → Found queen! Add [0, 2] to answer and stop.

3. Direction (-1, 1) (upper-right diagonal):

   • Move to [1, 3] → No queen
   • Move to [0, 4] → No queen, reached edge.

4. Direction (0, -1) (left):

   • Move to [2, 1] → No queen
   • Move to [2, 0] → No queen, reached edge.

5. Direction (0, 1) (right):

   • Move to [2, 3] → No queen
   • Move to [2, 4] → No queen, reached edge.

6. Direction (1, -1) (lower-left diagonal):

   • Move to [3, 1] → No queen
   • Move to [4, 0] → No queen, reached edge.

7. Direction (1, 0) (down):

   • Move to [3, 2] → No queen
   • Move to [4, 2] → Found queen! Add [4, 2] to answer and stop.

8. Direction (1, 1) (lower-right diagonal):

   • Move to [3, 3] → No queen
   • Move to [4, 4] → No queen, reached edge.

Step 4: Result The queens that can attack the king are: [[1, 1], [0, 2], [4, 2]]

Note that:

• Queen at [0, 0] cannot attack because [1, 1] blocks the diagonal path
• Queen at [3, 4] cannot attack because it's not on the same row, column, or diagonal as the king

This demonstrates how the algorithm efficiently finds only the closest queen in each direction that can attack the king.

Solution Implementation

Time and Space Complexity

The time complexity is O(n²), and the space complexity is O(n²). In this problem, n = 8.

Time Complexity Analysis:

• Converting the queens list to a set takes O(q) time where q is the number of queens
• The nested loops iterate through 8 directions (from -1 to 1 for both a and b, excluding (0,0))
• For each direction, we traverse at most n cells on the board until we hit a boundary or find a queen
• Therefore, the total operations are 8 × n = O(n)
• However, since we need to convert queens to a set first, and in the worst case q can be O(n²) (all cells could have queens), the overall time complexity is O(n²)

Space Complexity Analysis:

• The set s stores all queen positions, which in the worst case could be all n² positions on the board, requiring O(n²) space
• The answer list ans can store at most 8 queens (one in each direction from the king), which is O(1)
• Therefore, the overall space complexity is O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Direction Generation Logic

A frequent mistake is using if a and b instead of if a or b when filtering out the (0, 0) direction. This would incorrectly skip the four cardinal directions (up, down, left, right) where either a or b is 0.

Incorrect:

for a in range(-1, 2):
    for b in range(-1, 2):
        if a and b:  # Wrong! This only includes diagonals

Correct:

for a in range(-1, 2):
    for b in range(-1, 2):
        if a or b:  # Correct - excludes only (0, 0)

2. Modifying Loop Variables Inside the While Loop

A critical error is reusing the king's position variables directly in the while loop, which causes the search to start from the wrong position for subsequent directions.

Incorrect:

x, y = king
for a in range(-1, 2):
    for b in range(-1, 2):
        if a or b:
            while 0 <= x + a < 8 and 0 <= y + b < 8:
                x, y = x + a, y + b  # Modifies x, y permanently!
                if (x, y) in s:
                    ans.append([x, y])
                    break

Correct:

for a in range(-1, 2):
    for b in range(-1, 2):
        if a or b:
            x, y = king  # Reset to king's position for each direction
            while 0 <= x + a < 8 and 0 <= y + b < 8:
                x, y = x + a, y + b
                if (x, y) in s:
                    ans.append([x, y])
                    break

3. Using List Instead of Set for Queen Positions

Checking if a position contains a queen using a list results in O(Q) lookup time per check, significantly slowing down the algorithm.

Inefficient:

# O(Q) lookup for each position check
for a in range(-1, 2):
    for b in range(-1, 2):
        if a or b:
            x, y = king
            while 0 <= x + a < 8 and 0 <= y + b < 8:
                x, y = x + a, y + b
                if [x, y] in queens:  # O(Q) operation!
                    ans.append([x, y])
                    break

Efficient:

# O(1) lookup using set
queen_positions = {(row, col) for row, col in queens}
# ... then use (x, y) in queen_positions

4. Forgetting to Break After Finding a Queen

Without the break statement, the search continues past the first queen found, potentially adding queens that are blocked and cannot actually attack the king.

Incorrect:

while 0 <= x + a < 8 and 0 <= y + b < 8:
    x, y = x + a, y + b
    if (x, y) in s:
        ans.append([x, y])
        # Missing break! Would continue searching and find blocked queens

5. Off-by-One Errors in Boundary Checking

Using <= instead of < for the upper boundary check causes index out of bounds errors.

Incorrect:

while 0 <= x + a <= 8 and 0 <= y + b <= 8:  # Wrong! Position 8 is out of bounds

Correct:

while 0 <= x + a < 8 and 0 <= y + b < 8:  # Correct boundary check