Problem Breakdown
We are given an 8x8 chessboard with multiple Black Queens and one White King. The objective is to return the coordinates of all queens that can attack the King immediately, adhering to standard chess rules where pieces block lines of sight.
Key Mechanics:
- Attack Lines: A queen attacks along rows (horizontal), columns (vertical), and diagonals.
- Blocking Rule: If a Queen is encountered on a line from the King’s perspective, it blocks any other Queens behind it in that same direction. Only the closest Queen to the King in each of the 8 directions can attack.
- Inputs:
queens(List[List[int]]) andking(List[int]). Coordinates are integers between 0 and 7 inclusive.
Intuition
A naive approach might iterate through every queen to check if it shares a row, column, or diagonal with the King. However, this requires complex logic to determine blocking status for each pair of queens on the same line.
To solve this efficiently:
- Perspective Shift: Instead of iterating Queens to find lines (which is O(N) per direction), we iterate from the King’s position outward in all 8 possible directions. This naturally handles blocking—if a Queen is found first along a ray, that is the attacker for that direction, and any further pieces on that line are irrelevant because they are blocked by this one.
- Data Structure: Converting the
queenslist into a Hash Set of tuples allows O(1) existence checks during our scan across the board cells.
Approach
- Preprocessing: Convert the input
queenslist into a set of coordinate tuples(r, c)for fast lookup. - Direction Definition: Define the 8 possible movement vectors representing rows, columns, and diagonals:
- Horizontal:
(0, -1), (0, 1) - Vertical:
(-1, 0), (1, 0) - Diagonal:
(-1, -1), (-1, 1), (1, -1), (1, 1)
- Horizontal:
- Ray Casting: For each of the 8 directions starting from
(king[0], king[1]):- Initialize current position to one step away in that direction.
- Loop while coordinates are within board bounds
[0-7]. - Check if the current cell exists in our
queensset.- If Yes: Add this coordinate to results and break immediately (blocking rule).
- If No: Continue moving further along that direction vector.
- Return Results: Return the collected list of attacking queens.
Complexity Analysis
- Time Complexity: O(N) where N is
len(queens).- Building the set takes to process all input coordinates.
- The ray casting loop visits at most one cell per direction until a queen or edge is hit. Since there are 8 directions and max board length is 7, the maximum number of steps across all rays combined is bounded by the grid size (64 cells). Thus, scanning takes relative to N in terms of operations count on fixed-size boards, but technically we must read input which dominates. In standard algorithmic analysis for this problem type: Set construction is linear scan (), ray traversal is constant max steps per direction regardless of board size (bounded by 8x8). So strictly to build set + scanning = O(N).
- Space Complexity: O(N)
- We store all queen coordinates in a hash set. The ray traversal uses constant auxiliary space for direction vectors and current position variables.
Solution
from typing import List
class Solution:
def queensAttackTheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
# Convert list of lists to tuple-based set for O(1) lookup performance
queen_set = {tuple(q) for q in queens}
result = []
k_row, k_col = king
# Define the 8 directions (row_delta, col_delta) covering all lines and diagonals
directions = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
for dr, dc in directions:
r, c = k_row + dr, k_col + dc
# Traverse along the ray until we hit a queen or board edge
while 0 <= r < 8 and 0 <= c < 8:
if (r, c) in queen_set:
result.append([r, c])
break # Blocking rule: stop scanning this direction after first piece
r += dr
c += dc
return result
Edge Cases Handled
- King on Board Edges: The
whileloop condition (0 <= r < 8) naturally handles cases where the King is at(7, 7)or(0, 0), preventing index out of bounds errors. - No Attacking Queens: If no queens lie in any line from the king (or all are blocked by other pieces),
resultremains empty and returns an empty list correctly. - Multiple Queens on Same Line: The logic breaks immediately upon finding a queen (
break). This ensures that only the closest queen to the King is added, adhering strictly to chess blocking rules where intermediate pieces block attacks from behind them. - Duplicate Coordinates in Input: While constraints say “At most one piece per cell”, converting input list to set handles duplicates gracefully by keeping unique coordinates (though valid inputs shouldn’t have duplicate queens).