LeetCode 1222 - Queens That Can Attack the King

In this problem, we are given the positions of several black queens and exactly one white king on a standard 8 x 8 chessboard. The board uses 0-indexed coordinates, meaning every position is represented as [row, column], where both values range from 0 to 7.

leetcodemediumarraymatrixsimulation

LeetCode Problem 1222

Difficulty: 🟡 Medium
Topics: Array, Matrix, Simulation

Solution

Problem Understanding

In this problem, we are given the positions of several black queens and exactly one white king on a standard 8 x 8 chessboard. The board uses 0-indexed coordinates, meaning every position is represented as [row, column], where both values range from 0 to 7.

A queen in chess can attack along eight possible directions:

  • Up
  • Down
  • Left
  • Right
  • Top-left diagonal
  • Top-right diagonal
  • Bottom-left diagonal
  • Bottom-right diagonal

However, queens cannot attack through other queens. If another queen appears between a queen and the king, then the farther queen is blocked.

The task is to return all queens that can directly attack the king.

For example, if the king is at [3,3], then any queen located in the same row, same column, or same diagonal may be able to attack. But only the closest queen in each direction matters, because any farther queen is blocked by the closer one.

The input consists of:

  • queens, a list of queen positions
  • king, the king's position

The output should contain the coordinates of all queens that can directly attack the king. The order does not matter.

The constraints are very small:

  • At most 63 queens can exist
  • The board size is fixed at 8 x 8

These constraints tell us that even relatively inefficient solutions would still run quickly. However, the problem is fundamentally about directional searching and board simulation, so designing a clean and optimal solution is important.

Several edge cases are important:

  • Multiple queens may exist in the same direction from the king
  • Only the nearest queen in a direction can attack
  • Queens may surround the king from all eight directions
  • Some queens may share neither row, column, nor diagonal with the king
  • The king may be near the edge or corner of the board
  • There is always exactly one king
  • All positions are unique, so no two pieces overlap

Approaches

Brute Force Approach

A straightforward solution is to examine every queen and determine whether it attacks the king.

For each queen, we can check:

  • Same row
  • Same column
  • Same diagonal

If a queen satisfies one of these conditions, we then need to verify that no other queen blocks the path between that queen and the king.

To do this, we would scan every square between the queen and the king. If another queen appears along that path, then the queen cannot directly attack.

This method is correct because it explicitly verifies every attacking condition and every possible obstruction. However, it repeatedly scans paths and repeatedly checks queens, leading to unnecessary work.

Although the board is tiny, this approach is conceptually inefficient because it performs many redundant checks.

Optimal Approach

The key observation is that the king can only be attacked from eight possible directions.

Instead of examining every queen independently, we can start from the king and move outward in each direction one square at a time.

The first queen encountered in a direction is guaranteed to be the only queen that can attack from that direction, because any farther queen would be blocked.

This transforms the problem into directional simulation:

  1. Store all queen positions in a hash set for constant time lookup
  2. Explore the board in the eight directions
  3. Stop when:
  • We leave the board, or
  • We encounter the first queen in that direction

Because the board size is fixed at 8 x 8, each directional scan is extremely small.

Approach Time Complexity Space Complexity Notes
Brute Force O(Q²) O(Q) Checks every queen and possible blockers
Optimal O(Q + 8 × 8) O(Q) Simulates outward from the king in eight directions

Here, Q is the number of queens.

Algorithm Walkthrough

Step 1: Store all queen positions in a hash set

We convert every queen coordinate into a tuple and store it in a set.

This allows constant time lookup when checking whether a square contains a queen.

For example:

queen_set = {(0,1), (1,0), (3,3)}

Using a set is important because we repeatedly query board positions during directional scans.

Step 2: Define the eight movement directions

We create a list containing all possible queen attack directions:

directions = [
    (-1, 0),  # up
    (1, 0),   # down
    (0, -1),  # left
    (0, 1),   # right
    (-1, -1), # top-left
    (-1, 1),  # top-right
    (1, -1),  # bottom-left
    (1, 1)    # bottom-right
]

Each pair represents (row_change, column_change).

Step 3: Explore outward from the king

For every direction:

  1. Start at the king's position
  2. Move one square at a time
  3. Check whether the new square contains a queen
  4. If it does:
  • Add that queen to the answer
  • Stop exploring that direction
  1. If we leave the board, stop exploring

This works because the first queen encountered blocks all queens behind it.

Step 4: Return the collected queens

After processing all eight directions, the answer list contains every queen that can directly attack the king.

Why it works

A queen attacks the king only if:

  • It lies in one of the eight valid attack directions
  • No queen blocks the path

By scanning outward from the king in each direction, the algorithm guarantees that the first queen found is exactly the nearest queen in that direction. Since queens block one another, any farther queen cannot attack. Therefore, every collected queen is valid, and every valid attacking queen is found.

Python Solution

from typing import List

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        queen_positions = set()

        for row, col in queens:
            queen_positions.add((row, col))

        directions = [
            (-1, 0),
            (1, 0),
            (0, -1),
            (0, 1),
            (-1, -1),
            (-1, 1),
            (1, -1),
            (1, 1)
        ]

        result = []

        for row_delta, col_delta in directions:
            current_row = king[0]
            current_col = king[1]

            while True:
                current_row += row_delta
                current_col += col_delta

                if not (0 <= current_row < 8 and 0 <= current_col < 8):
                    break

                if (current_row, current_col) in queen_positions:
                    result.append([current_row, current_col])
                    break

        return result

The implementation begins by converting the queen coordinates into a hash set. This enables constant time position checks while scanning the board.

The directions list represents the eight attack directions a queen can move.

For each direction, the algorithm starts at the king and repeatedly advances one square. If the position leaves the board boundaries, the scan stops. If a queen is found, that queen is added to the result and the scan for that direction ends immediately.

The solution directly mirrors the board simulation process described in the algorithm walkthrough.

Go Solution

func queensAttacktheKing(queens [][]int, king []int) [][]int {
    queenPositions := make(map[[2]int]bool)

    for _, queen := range queens {
        queenPositions[[2]int{queen[0], queen[1]}] = true
    }

    directions := [][]int{
        {-1, 0},
        {1, 0},
        {0, -1},
        {0, 1},
        {-1, -1},
        {-1, 1},
        {1, -1},
        {1, 1},
    }

    result := [][]int{}

    for _, direction := range directions {
        row := king[0]
        col := king[1]

        for {
            row += direction[0]
            col += direction[1]

            if row < 0 || row >= 8 || col < 0 || col >= 8 {
                break
            }

            if queenPositions[[2]int{row, col}] {
                result = append(result, []int{row, col})
                break
            }
        }
    }

    return result
}

The Go implementation follows the same logic as the Python solution.

One important difference is that Go does not have tuples or sets built in, so a map[[2]int]bool is used to simulate a hash set of coordinates.

Slices are used for both the input and the result. Since the board size is tiny, there are no concerns about memory usage or integer overflow.

Worked Examples

Example 1

queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]]
king = [0,0]

Initial Setup

Queen set:

Position
(0,1)
(1,0)
(4,0)
(0,4)
(3,3)
(2,4)

King position:

(0,0)

Direction Scan

Direction Squares Checked First Queen Found Added to Result
Up (-1,0) Out of bounds immediately None No
Down (1,0) (1,0) (1,0) Yes
Left (0,-1) Out of bounds immediately None No
Right (0,1) (0,1) (0,1) Yes
Top-left (-1,-1) Out of bounds None No
Top-right (-1,1) Out of bounds None No
Bottom-left (1,-1) Out of bounds None No
Bottom-right (1,1) → (2,2) → (3,3) (3,3) (3,3) Yes

Final result:

[[1,0],[0,1],[3,3]]

Example 2

queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]]
king = [3,3]

Initial Setup

Queen set:

Position
(0,0)
(1,1)
(2,2)
(3,4)
(3,5)
(4,4)
(4,5)

King position:

(3,3)

Direction Scan

Direction Squares Checked First Queen Found Added
Up (-1,0) (2,3) → (1,3) → (0,3) None No
Down (1,0) (4,3) → (5,3) None No
Left (0,-1) (3,2) → (3,1) None No
Right (0,1) (3,4) (3,4) Yes
Top-left (-1,-1) (2,2) (2,2) Yes
Top-right (-1,1) (2,4) → (1,5) None No
Bottom-left (1,-1) (4,2) → (5,1) None No
Bottom-right (1,1) (4,4) (4,4) Yes

Final result:

[[3,4],[2,2],[4,4]]

Complexity Analysis

Measure Complexity Explanation
Time O(Q + 64) Building the set takes O(Q), scanning the board takes at most 64 moves
Space O(Q) The queen hash set stores all queen positions

The board has a fixed size of 8 x 8, so the directional scans are effectively constant time. Even in the worst case, each of the eight directions can move at most seven squares. Therefore, the runtime is dominated by constructing the queen set.

Test Cases

from typing import List

class Solution:
    def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
        queen_positions = set()

        for row, col in queens:
            queen_positions.add((row, col))

        directions = [
            (-1, 0),
            (1, 0),
            (0, -1),
            (0, 1),
            (-1, -1),
            (-1, 1),
            (1, -1),
            (1, 1)
        ]

        result = []

        for row_delta, col_delta in directions:
            row = king[0]
            col = king[1]

            while True:
                row += row_delta
                col += col_delta

                if not (0 <= row < 8 and 0 <= col < 8):
                    break

                if (row, col) in queen_positions:
                    result.append([row, col])
                    break

        return result

solution = Solution()

# Example 1
result = solution.queensAttacktheKing(
    [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]],
    [0,0]
)
assert sorted(result) == sorted([[0,1],[1,0],[3,3]])

# Example 2
result = solution.queensAttacktheKing(
    [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]],
    [3,3]
)
assert sorted(result) == sorted([[2,2],[3,4],[4,4]])

# Single queen attacks vertically
result = solution.queensAttacktheKing(
    [[2,4]],
    [5,4]
)
assert result == [[2,4]]

# Queen blocked by another queen
result = solution.queensAttacktheKing(
    [[1,1],[2,2]],
    [3,3]
)
assert result == [[2,2]]

# No queens can attack
result = solution.queensAttacktheKing(
    [[0,1],[1,3],[5,2]],
    [4,4]
)
assert result == []

# King in corner with multiple attackers
result = solution.queensAttacktheKing(
    [[0,1],[1,0],[1,1],[2,2]],
    [0,0]
)
assert sorted(result) == sorted([[0,1],[1,0],[1,1]])

# Queens in all eight directions
result = solution.queensAttacktheKing(
    [
        [3,2], [3,4],
        [2,3], [4,3],
        [2,2], [2,4],
        [4,2], [4,4]
    ],
    [3,3]
)
assert sorted(result) == sorted([
    [3,2], [3,4],
    [2,3], [4,3],
    [2,2], [2,4],
    [4,2], [4,4]
])

print("All tests passed!")
Test Why
Example 1 Validates basic directional attacks
Example 2 Validates row and diagonal scanning
Single queen attacks vertically Tests simple vertical attack
Queen blocked by another queen Ensures only nearest queen counts
No queens can attack Verifies empty result handling
King in corner with multiple attackers Tests boundary handling
Queens in all eight directions Ensures all directions are scanned correctly

Edge Cases

One important edge case occurs when multiple queens lie in the same direction from the king. A naive implementation might incorrectly include all of them. For example, if queens exist at [1,1] and [2,2] while the king is at [3,3], only [2,2] can attack because it blocks the farther queen. The directional scanning approach naturally handles this because it stops after finding the first queen.

Another important case is when the king is positioned on the edge or in a corner of the board. Some directions immediately leave the board. Implementations that do not carefully check boundaries may attempt invalid index access. This solution checks boundaries before every lookup, preventing out-of-range errors.

A third important edge case is when no queen can attack the king. Some implementations accidentally return partial matches from incorrect row or diagonal logic. This solution only returns queens discovered during valid directional scans, so if no queen is found in any direction, the result correctly remains empty.

A fourth edge case involves queens that share neither row, column, nor diagonal with the king. Such queens can never attack, regardless of distance. Because the algorithm only scans along valid queen movement directions, these irrelevant queens are automatically ignored.