Queens That Can Attack the King — Problem & Solution
Queens That Can Attack the King solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Queens That Can Attack the King is a medium coding problem on arrays, matrix and simulation, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Matrix, Simulation
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
On an 8 × 8 chessboard (rows and columns numbered 0 to 7) there are several black queens and one white king. queens[i] = [r, c] is the square of the i-th queen and king = [r, c] is the square of the king.
A queen attacks along its row, its column and both diagonals, but cannot see through another queen. Return the squares of every queen that directly attacks the king, sorted by row and then by column.
Example 1
Input: queens = [[0,0],[1,1],[2,4],[3,0],[4,4],[0,4]], king = [2,2]
Output: [[0,4],[1,1],[2,4],[4,4]]
Explanation: `[0,0]` is hidden behind `[1,1]` on the same diagonal, and `[3,0]` shares no line with the king.
Example 2
Input: queens = [[5,5]], king = [0,0]
Output: [[5,5]]
Example 3
Input: queens = [[1,2],[3,7]], king = [0,0]
Output: []
Constraints
1 <= queens.length < 64queens[i].length == king.length == 20 <= queens[i][j], king[j] < 8all the given positions are distinct
Hints for Queens That Can Attack the King
Hint 1
Think from the king's point of view rather than from each queen's.
Hint 2
From the king, look outwards in all 8 directions.
Hint 3
In each direction, the first queen met (if any) attacks the king; everything behind it is blocked. Collect those, then sort.
How to solve Queens That Can Attack the King
Only the nearest queen in each of the king's 8 directions can attack, so walking outwards from the king finds all attackers in at most 56 steps.
Approach
- Mark the queens' squares on an 8 × 8 grid.
- For each direction
(dr, dc)withdr, dcin{-1, 0, 1}(not both 0), step from the king until leaving the board or reaching a marked square. - Record the marked square found in each direction.
- Return the recorded squares sorted by row, then column (scanning the grid row by row over the recorded marks does this for free).
Why it works
A queen attacks the king exactly when it shares a line with the king and no piece lies between them — i.e. it is the first piece along that line from the king's side. The walk checks each line from the king outward and stops at the first queen, which is exactly that condition.
Complexity
- Time —
O(q) to mark plus O(1) for the walks - Space —
O(1) — the board has 64 squares
Pitfalls
- Queens behind another queen on the same line are blocked.
- There are 8 directions — the four diagonals are easy to forget.
- The answer can be empty.
Reference solution
Python
from typing import List
def queensAttacktheKing(queens: List[List[int]], king: List[int]) -> List[List[int]]:
board = [[False] * 8 for _ in range(8)]
for r, c in queens:
board[r][c] = True
hit = [[False] * 8 for _ in range(8)]
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 board[r][c]:
hit[r][c] = True
break
r += dr
c += dc
return [[r, c] for r in range(8) for c in range(8) if hit[r][c]]Java
public static int[][] queensAttacktheKing(int[][] queens, int[] king) {
boolean[][] board = new boolean[8][8], hit = new boolean[8][8];
for (int[] q : queens) board[q[0]][q[1]] = true;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
for (int r = king[0] + dr, c = king[1] + dc; r >= 0 && c >= 0 && r < 8 && c < 8; r += dr, c += dc) {
if (board[r][c]) { hit[r][c] = true; break; }
}
}
}
List<int[]> out = new ArrayList<>();
for (int a = 0; a < 8; a++) for (int b = 0; b < 8; b++) if (hit[a][b]) out.add(new int[]{a, b});
return out.toArray(new int[0][]);
}C++
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
bool board[8][8] = {}, hit[8][8] = {};
for (auto& q : queens) board[q[0]][q[1]] = true;
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr == 0 && dc == 0) continue;
for (int r = king[0] + dr, c = king[1] + dc; r >= 0 && c >= 0 && r < 8 && c < 8; r += dr, c += dc) {
if (board[r][c]) { hit[r][c] = true; break; }
}
}
}
vector<vector<int>> out;
for (int a = 0; a < 8; a++) for (int b = 0; b < 8; b++) if (hit[a][b]) out.push_back({a, b});
return out;
}JavaScript
var queensAttacktheKing = function(queens, king) {
var board = [], hit = [];
for (var i = 0; i < 8; i++) { board.push(new Array(8).fill(false)); hit.push(new Array(8).fill(false)); }
for (var q = 0; q < queens.length; q++) board[queens[q][0]][queens[q][1]] = true;
for (var dr = -1; dr <= 1; dr++) {
for (var dc = -1; dc <= 1; dc++) {
if (dr === 0 && dc === 0) continue;
for (var r = king[0] + dr, c = king[1] + dc; r >= 0 && c >= 0 && r < 8 && c < 8; r += dr, c += dc) {
if (board[r][c]) { hit[r][c] = true; break; }
}
}
}
var out = [];
for (var a = 0; a < 8; a++) for (var b = 0; b < 8; b++) if (hit[a][b]) out.push([a, b]);
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Matrix and Grid Traversal