Watch 10 video solutions for Queens That Can Attack the King, a medium level problem involving Array, Matrix, Simulation. This walkthrough by Nick White has 11,053 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
On a 0-indexed 8 x 8 chessboard, there can be multiple black queens and one white king.
You are given a 2D integer array queens where queens[i] = [xQueeni, yQueeni] represents the position of the ith black queen on the chessboard. You are also given an integer array king of length 2 where king = [xKing, yKing] represents the position of the white king.
Return the coordinates of the black queens that can directly attack the king. You may return the answer in any order.
Example 1:
Input: queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0] Output: [[0,1],[1,0],[3,3]] Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).
Example 2:
Input: queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3] Output: [[2,2],[3,4],[4,4]] Explanation: The diagram above shows the three queens that can directly attack the king and the three queens that cannot attack the king (i.e., marked with red dashes).
Constraints:
1 <= queens.length < 64queens[i].length == king.length == 20 <= xQueeni, yQueeni, xKing, yKing < 8Problem Overview: Given positions of multiple queens and a single king on an 8×8 chessboard, return all queens that can directly attack the king. A queen attacks along rows, columns, and diagonals, but another queen blocks the path. The task is to find the closest attacking queen in each of the eight possible directions.
Approach 1: Direction-based BFS Search (O(q + 8n) time, O(q) space)
Store all queen positions in a set or hash structure for constant-time lookup. From the king’s position, simulate movement in the eight chess directions: up, down, left, right, and the four diagonals. Move step by step along each direction until you either leave the board or encounter a queen. The first queen encountered in a direction is the only one that can attack because any others are blocked. This approach behaves like a directional BFS/linear scan and works well because each direction is explored independently.
The key insight: only the nearest queen in each direction matters. Instead of checking every queen against the king, you expand outward from the king and stop immediately when a queen appears. With an 8×8 board, the maximum steps per direction are small, making the scan extremely efficient. The algorithm relies on constant-time membership checks and simple coordinate updates.
Approach 2: Grid Marking with Search (O(q + 8n) time, O(n²) space)
Create an 8×8 grid and mark queen locations directly in the matrix. Once the board is populated, start from the king and scan outward in the same eight directions. Each step checks the grid cell: if it contains a queen, add it to the result and stop scanning that direction. If the cell is empty, continue until the board boundary.
This version favors clarity. The grid acts as a quick lookup structure, and the directional search mirrors how a chess engine evaluates moves. The tradeoff is slightly higher memory usage due to the board matrix, though on an 8×8 grid the cost is negligible. This approach is easy to implement in languages where matrix operations are straightforward, especially when working with Matrix traversal patterns.
Both solutions rely on simple directional simulation rather than complex graph traversal. The operations involve iterating through coordinates and checking occupancy, which fits naturally with Array storage and board-style Simulation problems.
Recommended for interviews: The direction-based search from the king is what interviewers expect. It demonstrates understanding of chess movement rules and avoids unnecessary comparisons between every queen and the king. A brute-force pairwise check shows the basic idea, but scanning the eight directions highlights algorithmic thinking and leads to the optimal linear-style solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direction-based BFS Search | O(q + 8n) | O(q) | Best general solution; efficient with hash lookup of queen positions |
| Grid Marking with Search | O(q + 8n) | O(n²) | Useful when representing the board explicitly as a matrix |