# Queens That Can Attack the King
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/queens-that-can-attack-the-king)
Canonical: https://scaleengineer.com/dsa/problems/queens-that-can-attack-the-king
**Data structures:** Array, Matrix
**Companies:** [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
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] = [xQueeni, yQueeni]` represents the position of the `ith` 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:**

![](https://assets.leetcode.com/uploads/2022/12/21/chess1.jpg) 

**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:**

![](https://assets.glich.co/dsa/queens-that-can-attack-the-king/image1.jpg) 

**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:**

* `1 <= queens.length < 64`
* `queens[i].length == king.length == 2`
* `0 <= xQueeni, yQueeni, xKing, yKing < 8`
* All the given positions are **unique**.

# Approaches
## Brute-Force with Pairwise Blocking Check
This is a straightforward but inefficient approach. It examines every queen one by one. For each queen, it checks if it lies on an attack line with the king. If it does, it then iterates through all *other* queens to see if any of them are positioned between the current queen and the king, thereby blocking the attack.
**Time:** O(Q^2), where Q is the number of queens. For each of the Q queens, we iterate through up to Q-1 other queens. · **Space:** O(1), as we only use a few variables to store state. The space for the result list is not counted, and it's at most 8 elements.
**Pros:** Simple to reason about conceptually.; Requires minimal extra space (O(1)).
**Cons:** Highly inefficient with a time complexity of O(Q^2), where Q is the number of queens.; The logic to check if a queen is 'between' two other points can be complex and error-prone.
### Explanation
The algorithm iterates through each queen, let's call it `queenA`. For `queenA`, it first verifies if it shares a row, column, or diagonal with the king. If it does, a potential attack line exists. The algorithm then enters a nested loop, iterating through every other queen, `queenB`. Inside the nested loop, it checks if `queenB` also lies on the same attack line *and* is closer to the king than `queenA`. The distance can be calculated using Chebyshev distance (`max(|x1-x2|, |y1-y2|)`), which is natural for queen moves. If such a blocking `queenB` is found, `queenA` cannot attack the king, and we can stop checking other potential blockers for `queenA`. If the inner loop completes without finding any blocking queens, `queenA` can attack the king, and its coordinates are added to the result list. This process is repeated for all queens.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> result = new ArrayList<>();
        int kx = king[0];
        int ky = king[1];

        for (int[] queen : queens) {
            int qx = queen[0];
            int qy = queen[1];

            // Check if queen is on an attack line with the king
            if (qx != kx && qy != ky && Math.abs(qx - kx) != Math.abs(qy - ky)) {
                continue; // Not on an attack line
            }

            boolean isBlocked = false;
            // Check for other queens blocking the path
            for (int[] otherQueen : queens) {
                if (otherQueen == queen) continue;
                int ox = otherQueen[0];
                int oy = otherQueen[1];

                // Check if otherQueen is on the same line and between king and queen
                if (isBetween(kx, ky, qx, qy, ox, oy)) {
                    isBlocked = true;
                    break;
                }
            }

            if (!isBlocked) {
                result.add(Arrays.asList(qx, qy));
            }
        }
        return result;
    }

    // Helper to check if (ox, oy) is between (kx, ky) and (qx, qy)
    private boolean isBetween(int kx, int ky, int qx, int qy, int ox, int oy) {
        // Check for collinearity and direction
        boolean sameDirection = Integer.signum(qx - kx) == Integer.signum(ox - kx) && 
                                Integer.signum(qy - ky) == Integer.signum(oy - ky);

        if (!sameDirection) return false;

        // Check if on the same line (row, col, or diagonal)
        boolean onLine = (kx == qx && kx == ox) || // same column
                         (ky == qy && ky == oy) || // same row
                         (Math.abs(kx - ox) == Math.abs(ky - oy)); // same diagonal

        if (!onLine) return false;

        // Check if otherQueen is closer to the king
        return Math.abs(ox - kx) < Math.abs(qx - kx) || Math.abs(oy - ky) < Math.abs(qy - ky);
    }
}
```
### Algorithm
- 1. Initialize an empty list `result`.
- 2. For each `queen` in the input `queens` array:
    - a. Check if the `queen` and the `king` are on the same row, column, or diagonal. If not, skip to the next queen.
    - b. Assume the path is clear by setting a flag `isBlocked = false`.
    - c. Start a nested loop to iterate through all other queens (`blockerQueen`).
    - d. Check if `blockerQueen` lies on the line segment strictly between the `king` and the current `queen`.
    - e. If a `blockerQueen` is found, set `isBlocked = true` and break the inner loop.
    - f. After the inner loop, if `isBlocked` is still `false`, add the current `queen` to the `result` list.
- 3. Return the `result` list.

## Search Outwards from the King
This is a much more efficient approach that mirrors how attacks actually work on a chessboard. Instead of checking from each queen's perspective, we start at the king's position and search outwards in the eight possible attack directions (horizontal, vertical, and diagonals). The first queen encountered in each direction is an attacking queen, and any queen behind it is blocked.
**Time:** O(Q + D^2) where Q is the number of queens and D is the dimension of the board (8). It takes O(Q) to populate the lookup board. The search from the king takes at most 8 * D steps. Since D is a constant (8), the overall complexity simplifies to O(Q). · **Space:** O(D^2) to store the 8x8 board, where D is the board dimension (8). If a `HashSet` were used instead, the space would be O(Q). Given the constraints, these are comparable and small.
**Pros:** Very efficient, with a time complexity that depends linearly on the number of queens and the board size, which are small constants.; The logic is clean and directly models the problem from the king's perspective.; Avoids complex geometric calculations for checking if a piece is 'in between' others.
**Cons:** Requires extra space for the lookup structure (O(D^2) for a board or O(Q) for a set), whereas the brute-force approach uses O(1) space.
### Explanation
The core idea is to find the *first* queen along each of the 8 attack rays originating from the king. First, we need an efficient way to check if a square contains a queen. We can convert the list of queen positions into a data structure that allows for fast lookups, such as a `HashSet` of coordinates or a 2D boolean array representing the board. Using a 2D array `boolean[][] board = new boolean[8][8]` is straightforward given the fixed board size. We populate this lookup structure by iterating through the input `queens` array once. Next, we define the 8 directions of movement, for example, as an array of coordinate pairs: `{{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}}`. Then, for each of these 8 directions, we start a search from the king's coordinates. We move one step at a time in the current direction, checking each square. If we land on a square that contains a queen (using our lookup structure), we've found an attacking queen. We add its coordinates to our result list and then stop searching in this direction (since this queen blocks any others further away). If our search goes off the board, we also stop searching in that direction. After checking all 8 directions, the result list will contain all queens that can attack the king.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[][] board = new boolean[8][8];
        for (int[] queen : queens) {
            board[queen[0]][queen[1]] = true;
        }

        int kx = king[0];
        int ky = king[1];

        // 8 directions: N, S, W, E, NW, NE, SW, SE
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {-1, 1}, {1, -1}, {1, 1}};

        for (int[] dir : directions) {
            int x = kx;
            int y = ky;
            while (true) {
                x += dir[0];
                y += dir[1];

                // Check if out of bounds
                if (x < 0 || x >= 8 || y < 0 || y >= 8) {
                    break;
                }

                // Check if we found a queen
                if (board[x][y]) {
                    result.add(Arrays.asList(x, y));
                    break; // Found the first queen in this direction, stop searching
                }
            }
        }
        return result;
    }
}
```
### Algorithm
- 1. Create a lookup structure for queen positions. A 2D boolean array `board[8][8]` is a good choice.
- 2. Iterate through the input `queens` array and mark the corresponding positions as `true` on the `board`.
- 3. Initialize an empty list `result`.
- 4. Define an array of 8 direction vectors (e.g., `{-1, 0}` for North, `{1, 1}` for South-East, etc.).
- 5. For each of the 8 directions:
    - a. Start a loop from the king's position `(kx, ky)`.
    - b. In each iteration, move one step in the current direction to a new position `(nx, ny)`.
    - c. If `(nx, ny)` is off the board, break the loop for this direction.
    - d. If the `board` at `(nx, ny)` is `true`, it means we've found a queen. Add `(nx, ny)` to `result`, and break the loop for this direction (as it's the closest one).
- 6. Return the `result` list.

# Solutions
### Java

```java
class Solution {
public
  List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
    final int n = 8;
    var s = new boolean[n][n];
    for (var q : queens) {
      s[q[0]][q[1]] = true;
    }
    List<List<Integer>> ans = new ArrayList<>();
    for (int a = -1; a <= 1; ++a) {
      for (int b = -1; b <= 1; ++b) {
        if (a != 0 || b != 0) {
          int x = king[0] + a, y = king[1] + b;
          while (x >= 0 && x < n && y >= 0 && y < n) {
            if (s[x][y]) {
              ans.add(List.of(x, y));
              break;
            }
            x += a;
            y += b;
          }
        }
      }
    }
    return ans;
  }
}

```

### Python

```python
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

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> queensAttacktheKing(vector<vector<int>> &queens,
                                          vector<int> &king) {
    int n = 8;
    bool s[8][8]{};
    for (auto &q : queens) {
      s[q[0]][q[1]] = true;
    }
    vector<vector<int>> ans;
    for (int a = -1; a <= 1; ++a) {
      for (int b = -1; b <= 1; ++b) {
        if (a || b) {
          int x = king[0] + a, y = king[1] + b;
          while (x >= 0 && x < n && y >= 0 && y < n) {
            if (s[x][y]) {
              ans.push_back({x, y});
              break;
            }
            x += a;
            y += b;
          }
        }
      }
    }
    return ans;
  }
};

```