Queens That Can Attack the King
MedPrompt
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 < 8- All the given positions are unique.
Approaches
2 approaches with complexity analysis and trade-offs.
This is a straightforward but inefficient approach. It examines every queen one by one. For each queen, it checks if it lies on an attack line with the king. If it does, it then iterates through all other queens to see if any of them are positioned between the current queen and the king, thereby blocking the attack.
Algorithm
-
- Initialize an empty list
result.
- Initialize an empty list
-
- For each
queenin the inputqueensarray:
- a. Check if the
queenand thekingare on the same row, column, or diagonal. If not, skip to the next queen. - b. Assume the path is clear by setting a flag
isBlocked = false. - c. Start a nested loop to iterate through all other queens (
blockerQueen). - d. Check if
blockerQueenlies on the line segment strictly between thekingand the currentqueen. - e. If a
blockerQueenis found, setisBlocked = trueand break the inner loop. - f. After the inner loop, if
isBlockedis stillfalse, add the currentqueento theresultlist.
- For each
-
- Return the
resultlist.
- Return the
Walkthrough
The algorithm iterates through each queen, let's call it queenA. For queenA, it first verifies if it shares a row, column, or diagonal with the king. If it does, a potential attack line exists. The algorithm then enters a nested loop, iterating through every other queen, queenB. Inside the nested loop, it checks if queenB also lies on the same attack line and is closer to the king than queenA. The distance can be calculated using Chebyshev distance (max(|x1-x2|, |y1-y2|)), which is natural for queen moves. If such a blocking queenB is found, queenA cannot attack the king, and we can stop checking other potential blockers for queenA. If the inner loop completes without finding any blocking queens, queenA can attack the king, and its coordinates are added to the result list. This process is repeated for all queens.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { List<List<Integer>> result = new ArrayList<>(); int kx = king[0]; int ky = king[1]; for (int[] queen : queens) { int qx = queen[0]; int qy = queen[1]; // Check if queen is on an attack line with the king if (qx != kx && qy != ky && Math.abs(qx - kx) != Math.abs(qy - ky)) { continue; // Not on an attack line } boolean isBlocked = false; // Check for other queens blocking the path for (int[] otherQueen : queens) { if (otherQueen == queen) continue; int ox = otherQueen[0]; int oy = otherQueen[1]; // Check if otherQueen is on the same line and between king and queen if (isBetween(kx, ky, qx, qy, ox, oy)) { isBlocked = true; break; } } if (!isBlocked) { result.add(Arrays.asList(qx, qy)); } } return result; } // Helper to check if (ox, oy) is between (kx, ky) and (qx, qy) private boolean isBetween(int kx, int ky, int qx, int qy, int ox, int oy) { // Check for collinearity and direction boolean sameDirection = Integer.signum(qx - kx) == Integer.signum(ox - kx) && Integer.signum(qy - ky) == Integer.signum(oy - ky); if (!sameDirection) return false; // Check if on the same line (row, col, or diagonal) boolean onLine = (kx == qx && kx == ox) || // same column (ky == qy && ky == oy) || // same row (Math.abs(kx - ox) == Math.abs(ky - oy)); // same diagonal if (!onLine) return false; // Check if otherQueen is closer to the king return Math.abs(ox - kx) < Math.abs(qx - kx) || Math.abs(oy - ky) < Math.abs(qy - ky); }}Complexity
Time
O(Q^2), where Q is the number of queens. For each of the Q queens, we iterate through up to Q-1 other queens.
Space
O(1), as we only use a few variables to store state. The space for the result list is not counted, and it's at most 8 elements.
Trade-offs
Pros
Simple to reason about conceptually.
Requires minimal extra space (O(1)).
Cons
Highly inefficient with a time complexity of O(Q^2), where Q is the number of queens.
The logic to check if a queen is 'between' two other points can be complex and error-prone.
This is a much more efficient approach that mirrors how attacks actually work on a chessboard. Instead of checking from each queen's perspective, we start at the king's position and search outwards in the eight possible attack directions (horizontal, vertical, and diagonals). The first queen encountered in each direction is an attacking queen, and any queen behind it is blocked.
Algorithm
-
- Create a lookup structure for queen positions. A 2D boolean array
board[8][8]is a good choice.
- Create a lookup structure for queen positions. A 2D boolean array
-
- Iterate through the input
queensarray and mark the corresponding positions astrueon theboard.
- Iterate through the input
-
- Initialize an empty list
result.
- Initialize an empty list
-
- Define an array of 8 direction vectors (e.g.,
{-1, 0}for North,{1, 1}for South-East, etc.).
- Define an array of 8 direction vectors (e.g.,
-
- For each of the 8 directions:
- a. Start a loop from the king's position
(kx, ky). - b. In each iteration, move one step in the current direction to a new position
(nx, ny). - c. If
(nx, ny)is off the board, break the loop for this direction. - d. If the
boardat(nx, ny)istrue, it means we've found a queen. Add(nx, ny)toresult, and break the loop for this direction (as it's the closest one).
-
- Return the
resultlist.
- Return the
Walkthrough
The core idea is to find the first queen along each of the 8 attack rays originating from the king. First, we need an efficient way to check if a square contains a queen. We can convert the list of queen positions into a data structure that allows for fast lookups, such as a HashSet of coordinates or a 2D boolean array representing the board. Using a 2D array boolean[][] board = new boolean[8][8] is straightforward given the fixed board size. We populate this lookup structure by iterating through the input queens array once. Next, we define the 8 directions of movement, for example, as an array of coordinate pairs: {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}. Then, for each of these 8 directions, we start a search from the king's coordinates. We move one step at a time in the current direction, checking each square. If we land on a square that contains a queen (using our lookup structure), we've found an attacking queen. We add its coordinates to our result list and then stop searching in this direction (since this queen blocks any others further away). If our search goes off the board, we also stop searching in that direction. After checking all 8 directions, the result list will contain all queens that can attack the king.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { List<List<Integer>> result = new ArrayList<>(); boolean[][] board = new boolean[8][8]; for (int[] queen : queens) { board[queen[0]][queen[1]] = true; } int kx = king[0]; int ky = king[1]; // 8 directions: N, S, W, E, NW, NE, SW, SE int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}; for (int[] dir : directions) { int x = kx; int y = ky; while (true) { x += dir[0]; y += dir[1]; // Check if out of bounds if (x < 0 || x >= 8 || y < 0 || y >= 8) { break; } // Check if we found a queen if (board[x][y]) { result.add(Arrays.asList(x, y)); break; // Found the first queen in this direction, stop searching } } } return result; }}Complexity
Time
O(Q + D^2) where Q is the number of queens and D is the dimension of the board (8). It takes O(Q) to populate the lookup board. The search from the king takes at most 8 * D steps. Since D is a constant (8), the overall complexity simplifies to O(Q).
Space
O(D^2) to store the 8x8 board, where D is the board dimension (8). If a `HashSet` were used instead, the space would be O(Q). Given the constraints, these are comparable and small.
Trade-offs
Pros
Very efficient, with a time complexity that depends linearly on the number of queens and the board size, which are small constants.
The logic is clean and directly models the problem from the king's perspective.
Avoids complex geometric calculations for checking if a piece is 'in between' others.
Cons
Requires extra space for the lookup structure (O(D^2) for a board or O(Q) for a set), whereas the brute-force approach uses O(1) space.
Solutions
Solution
class Solution {public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) { final int n = 8; var s = new boolean[n][n]; for (var q : queens) { s[q[0]][q[1]] = true; } List<List<Integer>> ans = new ArrayList<>(); for (int a = -1; a <= 1; ++a) { for (int b = -1; b <= 1; ++b) { if (a != 0 || b != 0) { int x = king[0] + a, y = king[1] + b; while (x >= 0 && x < n && y >= 0 && y < n) { if (s[x][y]) { ans.add(List.of(x, y)); break; } x += a; y += b; } } } } return ans; }}class Solution: def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]: n = 8 s = {(i, j) for i, j in queens} ans = [] for a in range(- 1, 2): for b in range(- 1, 2): if a or b: 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 return ansclass Solution {public: vector<vector<int>> queensAttacktheKing(vector<vector<int>> &queens, vector<int> &king) { int n = 8; bool s[8][8]{}; for (auto &q : queens) { s[q[0]][q[1]] = true; } vector<vector<int>> ans; for (int a = -1; a <= 1; ++a) { for (int b = -1; b <= 1; ++b) { if (a || b) { int x = king[0] + a, y = king[1] + b; while (x >= 0 && x < n && y >= 0 && y < n) { if (s[x][y]) { ans.push_back({x, y}); break; } x += a; y += b; } } } } return ans; }};Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.