Problem Description

You are given a chessboard of size 8x8. There are several queens on the board, each at a unique position given by the array queens, where each element is a list [x, y] representing a queen's row and column. There is also a king at position king = [x, y].

A queen can attack the king if they are on the same row, column, or diagonal, and there are no other queens blocking the path between the queen and the king. Your task is to find all queens that can attack the king and return their positions as a list of lists.

Constraints:

• Each position is unique; no two queens or the king share the same cell.
• The input size is small (maximum 8 queens), so efficiency is not a major concern, but clarity and correctness are important.
• Do not reuse elements; each queen can only attack from their given position.

Thought Process

The problem asks us to find all queens that can attack the king directly, considering chess movement rules and possible blocking by other queens. The brute-force way would be to check every queen and see if it can attack the king without being blocked. However, since the board is small, we can optimize by only considering the 8 possible directions (horizontal, vertical, and diagonals) from the king's position and looking for the nearest queen in each direction.

Instead of checking every queen against the king, we can "radiate out" from the king in each direction, step by step, and stop as soon as we find a queen. This ensures we only find queens that are not blocked by others and makes our solution more direct and clear.

Solution Approach

Let's break down the solution step by step:

1. Store Queen Positions:
   • We use a set to store all queen positions for fast lookup (O(1) time).
2. Define Directions:
   • There are 8 directions a queen can attack: left, right, up, down, and the four diagonals.
   • We represent these as pairs of row and column deltas: (dx, dy).
3. Simulate from King:
   • For each direction, start at the king's position and move one step at a time.
   • If we encounter a queen, add its position to the result and stop searching in that direction.
   • If we go out of bounds, stop searching in that direction.
4. Return Result:
   • After checking all directions, return the list of attacking queens' positions.

This approach is clear, avoids unnecessary checks, and leverages the chessboard's properties for efficient scanning.

Example Walkthrough

Sample Input:
queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]]
king = [0,0]

Step-by-step:

• Start at [0,0] (the king).
• Check each of the 8 directions:
• Right ([0,1]): Move to [0,1] → found queen, add to result.
• Down ([1,0]): Move to [1,0] → found queen, add to result.
• Diagonal Down-Right ([1,1]): Move to [1,1], then [2,2], etc. No queen found.
• Other directions: No queens found before going out of bounds.
• Continue for all directions; only the closest queen in each direction counts.
• Output: [[0,1],[1,0]]

Time and Space Complexity

Brute-force Approach:

• For each queen, check if it can attack the king (O(n)), and for each such queen, check for blockers (O(n)), leading to O(n^2) time.

• We check up to 8 directions, and in each direction, at most 8 steps (board size), so O(8*8) = O(1) time (since board size is constant).
• Space: O(n) for storing queen positions in a set.

The optimized approach is efficient and leverages the fixed size of the chessboard.

Summary

In this problem, we efficiently identify all queens that can attack the king by scanning outward from the king in all eight directions, stopping at the first queen encountered in each. Using a set for fast lookup and simulating movement directionally ensures we only find unblocked queens. The solution is both elegant and practical, making good use of the chessboard's constraints and movement rules.

Code Implementation

class Solution:
    def queensAttacktheKing(self, queens, king):
        queen_set = set(tuple(q) for q in queens)
        directions = [(-1, -1), (-1, 0), (-1, 1),
                      (0, -1),          (0, 1),
                      (1, -1),  (1, 0), (1, 1)]
        res = []
        for dx, dy in directions:
            x, y = king
            while 0 <= x+dx < 8 and 0 <= y+dy < 8:
                x += dx
                y += dy
                if (x, y) in queen_set:
                    res.append([x, y])
                    break
        return res
    

class Solution {
public:
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        set<pair<int, int>> queenSet;
        for (auto &q : queens)
            queenSet.insert({q[0], q[1]});
        vector<vector<int>> res;
        vector<pair<int, int>> directions = {
            {-1,-1}, {-1,0}, {-1,1},
            {0,-1},          {0,1},
            {1,-1},  {1,0},  {1,1}
        };
        for (auto d : directions) {
            int x = king[0], y = king[1];
            while (x + d.first >= 0 && x + d.first < 8 && y + d.second >= 0 && y + d.second < 8) {
                x += d.first;
                y += d.second;
                if (queenSet.count({x, y})) {
                    res.push_back({x, y});
                    break;
                }
            }
        }
        return res;
    }
};
    

class Solution {
    public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
        Set<String> queenSet = new HashSet<>();
        for (int[] q : queens) {
            queenSet.add(q[0] + "," + q[1]);
        }
        int[][] directions = {
            {-1, -1}, {-1, 0}, {-1, 1},
            {0, -1},           {0, 1},
            {1, -1},  {1, 0},  {1, 1}
        };
        List<List<Integer>> res = new ArrayList<>();
        for (int[] dir : directions) {
            int x = king[0], y = king[1];
            while (x + dir[0] >= 0 && x + dir[0] < 8 && y + dir[1] >= 0 && y + dir[1] < 8) {
                x += dir[0];
                y += dir[1];
                if (queenSet.contains(x + "," + y)) {
                    res.add(Arrays.asList(x, y));
                    break;
                }
            }
        }
        return res;
    }
}
    

var queensAttacktheKing = function(queens, king) {
    const queenSet = new Set(queens.map(q => q[0] + ',' + q[1]));
    const directions = [
        [-1,-1], [-1,0], [-1,1],
        [0,-1],         [0,1],
        [1,-1], [1,0], [1,1]
    ];
    const res = [];
    for (const [dx, dy] of directions) {
        let [x, y] = king;
        while (x + dx >= 0 && x + dx < 8 && y + dy >= 0 && y + dy < 8) {
            x += dx;
            y += dy;
            if (queenSet.has(x + ',' + y)) {
                res.push([x, y]);
                break;
            }
        }
    }
    return res;
};