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.
The idea here is to simulate the movement of the queens on the chessboard. We understand that a queen on a chessboard can attack any opponent piece situated in any of the 8 possible directions: horizontal, vertical, and diagonal. We begin by initializing a set that includes positions of all queens for constant-time lookup.
Next, starting from the king's position, we perform a breadth-first search (BFS) in all 8 directions. We stop whenever we encounter a queen or reach the edge of the board (out of bounds). The positions of queens we encounter are added to the result list, as they can directly attack the king.
This approach ensures we efficiently explore all attack paths while respecting the board's boundaries.
Initialize a set 'queens_set' for quick lookup of queen positions. Initialize a list 'result' to store queens that can attack the king. Use direction vectors to simulate the queen's movement. Traverse each direction from the king's position, checking for queens along the way. Whenever a queen is found, add its position to 'result' and stop further exploration in that direction.
Python
JavaScript
Time Complexity: O(8 * max(queens.length, 8)). This considers up to 8 directions, scanning up to the edge of the board for potential queens. Hence, constant time traversal per direction.
Space Complexity: O(queens.length). Since we store queen positions in a set.
This approach involves marking the chessboard grid with queens and performing a linear search for each potential attack direction from the king's position. We first create a board array to represent the chessboard and mark the board at the queen's positions.
For each direction from the king's position, we continue marking the path until we either find a queen or reach the end of the board. This way, if a queen is found along a path, it can directly attack the king.
Initialize a boolean 2D array 'board' to true at positions occupied by a queen. Search in all 8 directions starting from the king. At each valid position in a direction, check for the presence of a queen using the 'board' array. If a queen is found, add its coordinate to the result list and stop further exploration in that direction.
Time Complexity: O(8 * max(queens.length, 8)), since we process each direction until finding an attack-capable queen or boundary.
Space Complexity: O(1), aside from the fixed size board.
First, we store all the positions of the queens in a hash table or a two-dimensional array s.
Next, starting from the position of the king, we search in the eight directions: up, down, left, right, upper left, upper right, lower left, and lower right. If there is a queen in a certain direction, we add its position to the answer and stop continuing to search in that direction.
After the search is over, we return the answer.
The time complexity is O(n^2), and the space complexity is O(n^2). In this problem, n = 8.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Direction-based BFS Search | Time Complexity: O(8 * max(queens.length, 8)). This considers up to 8 directions, scanning up to the edge of the board for potential queens. Hence, constant time traversal per direction. Space Complexity: O(queens.length). Since we store queen positions in a set. |
| Grid Marking with Search | Time Complexity: O(8 * max(queens.length, 8)), since we process each direction until finding an attack-capable queen or boundary. Space Complexity: O(1), aside from the fixed size board. |
| Direct Search | — |
| 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 |
LeetCode 1222. Queens That Can Attack the King (Algorithm Explained) • Nick White • 11,053 views views
Watch 9 more video solutions →Practice Queens That Can Attack the King with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor