#1222

Medium

LeetCode Problem Workspace

Queens That Can Attack the King

Identify all black queens on an 8x8 chessboard that can attack the white king using array and matrix simulation techniques.

array matrix simulation

Problem Statement

Given an 8x8 chessboard, multiple black queens and one white king are placed on distinct squares. Each queen's position is provided as a 2D array queens where queens[i] = [xQueeni, yQueeni], and the king's position is given as king = [xKing, yKing].

Return a list of all black queens that can attack the king directly along any row, column, or diagonal. The order of output does not matter, but each queen must be reported only once, and queens blocked by others should be ignored.

Examples

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]]

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]]

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 < 64
queens[i].length == king.length == 2
0 <= xQueeni, yQueeni, xKing, yKing < 8
All the given positions are unique.

Solution Approach

Use direction vectors from the king

Define the eight directions a queen can attack: horizontally, vertically, and diagonally. For each direction, iterate outward from the king's position until a queen is found or the edge of the board is reached. This ensures only the closest attacking queen in each direction is considered.

Optimize queen lookup with a set

Store all queen positions in a set for O(1) lookup. As you scan each direction, check if the current cell is in the set. Once a queen is found in a direction, add it to the result list and stop scanning that direction to avoid duplicates.

Combine array and matrix traversal

Treat the chessboard as a matrix for traversal while using array coordinates for position calculations. Update row and column indices according to direction vectors, handling edge cases where indices exceed the 0-7 range. This merges array indexing with matrix simulation for clarity and correctness.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(64) since each of the eight directions can cover at most 8 squares, and lookup in a set is O(1). Space complexity is O(N) for storing the queen positions in a set, where N is the number of queens.

What Interviewers Usually Probe

Candidate should quickly identify eight directions from the king.
Look for correct handling of blocked paths by other queens.
Expect usage of sets for efficient position lookup.

Common Pitfalls or Variants

Common pitfalls

Forgetting to stop scanning after the first queen in a direction.
Confusing row and column indices when scanning diagonals.
Attempting to check all queens against the king without direction pruning, causing inefficiency.

Follow-up variants

Return only queens attacking from rows and columns, ignoring diagonals.
Chessboard size can be generalized beyond 8x8, requiring dynamic bounds checking.
Include multiple kings and determine attacking queens for each.

FAQ

What is the main pattern for Queens That Can Attack the King?

The problem follows an array plus matrix pattern where traversal from the king in all directions identifies attacking queens.

How do I handle queens blocked by others?

Scan outward from the king in each direction and stop at the first queen; any further queens in that line are ignored.

Can the board size be changed from 8x8?

Yes, the same approach works on any NxN board as long as the indices are correctly bounded during traversal.

Is the order of returned queens important?

No, queens can be returned in any order as long as all that can attack the king are included.

What data structure optimizes queen lookup?

Using a set to store queen positions allows O(1) checks while scanning each direction, preventing repeated calculations.

terminal

Solution

Solution 1: Direct Search

First, we store all the positions of the queens in a hash table or a two-dimensional array $s$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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 ans

Continue Practicing

#1260 shift 2d grid #1275 find winner on a tic tac toe game #999 available captures for rook