Is Queens That Can Attack the King easy or hard?

The problem is rated Medium on LeetCode but conceptually straightforward. The main challenge is recognizing that only eight directions need to be explored and that the closest queen in each direction determines whether the king is attacked.

Queens That Can Attack the King Python/Java solution

Python solutions typically store queens in a set of tuples and iterate through the eight direction vectors. Java implementations often use a boolean matrix or HashSet for queen lookup and perform the same directional scan from the king’s position.

How to solve Queens That Can Attack the King in O(n)?

Place all queens in a hash set for constant-time lookup. Starting from the king, simulate movement in the eight directions (horizontal, vertical, and diagonal). Move one cell at a time until you hit a queen or the board edge. Because only the nearest queen in each direction matters, the search completes in linear directional time.

What is the best approach for Queens That Can Attack the King?

The most efficient method scans outward from the king in the eight possible queen directions. Store queen positions in a hash set, then move step by step until a queen or board boundary is reached. The first queen encountered in each direction is the only valid attacker. This runs in O(q + 8n) time with O(q) space.

Is Queens That Can Attack the King asked at Google/Amazon/Meta?

Problems involving chess-style movement and grid simulation frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test directional traversal, board representation, and efficient lookups using sets or matrices.

What data structure is used in Queens That Can Attack the King?

A hash set is commonly used to store queen coordinates for O(1) membership checks. Some implementations also use a 2D matrix to mark queen locations. The algorithm itself relies on directional iteration across the grid.

What is the time complexity of Queens That Can Attack the King?

The typical solution runs in O(q + 8n) time, where q is the number of queens and n is the board dimension (8 in the standard problem). Building a lookup set for queens takes O(q), and scanning the eight directions from the king requires at most 8 × n steps.

Description Hints 2 Solution Video 11:27

1222. Queens That Can Attack the King

Medium72.6% acceptance2 companies

On a 0-indexed 8 x 8 chessboard, there can be multiple black queens and one white king.

You are given a 2D integer array queens where queens[i] = [xQueen_i, yQueen_i] represents the position of the i^th black queen on the chessboard. You are also given an integer array king of length 2 where king = [xKing, yKing] represents the position of the white king.

Return the coordinates of the black queens that can directly attack the king. You may return the answer in any order.

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