Queens That Can Attack the King
Problem
An 8×8 board contains some white queens and a single black king. Return the coordinates of all queens that can attack the king, i.e., the first queen encountered along each of the 8 directions from the king.
queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0][[0,1],[1,0],[3,3]]def queens_attack_king(queens, king):
qs = {(r, c) for r, c in queens}
res = []
for dr in (-1, 0, 1):
for dc in (-1, 0, 1):
if dr == 0 and dc == 0:
continue
r, c = king[0] + dr, king[1] + dc
while 0 <= r < 8 and 0 <= c < 8:
if (r, c) in qs:
res.append([r, c])
break
r += dr
c += dc
return resfunction queensAttackKing(queens, king) {
const set = new Set(queens.map(([r, c]) => r * 8 + c));
const res = [];
for (let dr = -1; dr <= 1; dr++) {
for (let dc = -1; dc <= 1; dc++) {
if (dr === 0 && dc === 0) continue;
let r = king[0] + dr, c = king[1] + dc;
while (r >= 0 && r < 8 && c >= 0 && c < 8) {
if (set.has(r * 8 + c)) { res.push([r, c]); break; }
r += dr; c += dc;
}
}
}
return res;
}class Solution {
public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
boolean[][] board = new boolean[8][8];
for (int[] q : queens) board[q[0]][q[1]] = true;
List<List<Integer>> res = new ArrayList<>();
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int r = king[0] + dr, c = king[1] + dc;
while (r >= 0 && r < 8 && c >= 0 && c < 8) {
if (board[r][c]) { res.add(Arrays.asList(r, c)); break; }
r += dr; c += dc;
}
}
}
return res;
}
}vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
bool board[8][8] = {};
for (auto& q : queens) board[q[0]][q[1]] = true;
vector<vector<int>> res;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
int r = king[0] + dr, c = king[1] + dc;
while (r >= 0 && r < 8 && c >= 0 && c < 8) {
if (board[r][c]) { res.push_back({r, c}); break; }
r += dr; c += dc;
}
}
}
return res;
}Explanation
A queen attacks along straight lines: horizontally, vertically, and diagonally. From the king there are exactly 8 such directions. The catch is that only the nearest queen in each direction can attack — anything behind it is blocked.
So we put all queen positions into a fast lookup (qs set). Then for each of the 8 directions, given as a step (dr, dc), we march outward one square at a time starting just next to the king.
The moment we land on a square that contains a queen, we record it and break — that queen blocks the rest of the ray. If we walk off the 8×8 board first, that direction has no attacker.
The nested dr, dc loops over -1, 0, 1 generate all 8 directions; we just skip (0, 0), which would mean "no movement."
Example: king at [0,0]. Going right we hit [0,1]; going down we hit [1,0]; going down-diagonally we hit [3,3]. Other rays run off the board, so the answer is [[0,1],[1,0],[3,3]].