Queens That Can Attack the King

Medium
1563.

Queens That Can Attack the King

Queens That Can Attack the King is a medium coding problem on arrays, matrix and simulation, asked in Amazon and Microsoft interviews.

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 < 64
  • queens[i].length == king.length == 2
  • 0 <= queens[i][j], king[j] < 8
  • all the given positions are distinct
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} queens
 * @param {number[]} king
 * @return {number[][]}
 */
var queensAttacktheKing = function(queens, king) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 < 64
  • queens[i].length == king.length == 2
  • 0 <= queens[i][j], king[j] < 8
  • all the given positions are distinct

Hints for Queens That Can Attack the King

  1. Hint 1

    Think from the king's point of view rather than from each queen's.

  2. Hint 2

    From the king, look outwards in all 8 directions.

  3. 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

  1. Mark the queens' squares on an 8 × 8 grid.
  2. For each direction (dr, dc) with dr, dc in {-1, 0, 1} (not both 0), step from the king until leaving the board or reaching a marked square.
  3. Record the marked square found in each direction.
  4. 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