{x}
blog image

Queens That Can Attack the King

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:

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:

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

Solution Explanation: Queens That Can Attack the King

This problem involves finding all queens on a chessboard that can attack a white king. The solution uses a direct search approach, iterating through all eight possible directions from the king's position and checking for the presence of a queen in each direction.

Approach:

  1. Data Structure: A boolean 2D array s (or a set in Python) is used to efficiently represent the chessboard. s[i][j] is true if a queen is at position (i, j), and false otherwise. This allows for quick lookups of queen positions.

  2. Direction Iteration: The code systematically checks eight directions from the king's position: up, down, left, right, and four diagonal directions. This is accomplished using nested loops with a and b iterating from -1 to 1 (excluding a = b = 0).

  3. Linear Search in Each Direction: For each direction, a while loop moves along that direction from the king's position. It continues until it either finds a queen (s[x][y] == true), reaches the edge of the board, or encounters an empty square.

  4. Queen Detection and Result: If a queen is found (s[x][y] == true), its coordinates [x, y] are added to the ans list (or equivalent data structure) which holds the attacking queens. The inner loop then breaks because the direction is exhausted.

  5. Return Value: Finally, the list ans containing the coordinates of the queens that can attack the king is returned.

Time Complexity: O(n), where n is the size of the board (8x8 in this case). The worst-case scenario involves checking all squares along each of the eight directions, giving a total of at most 8 * 7 = 56 steps. The time complexity remains constant regardless of the number of queens.

Space Complexity: O(1). The space used is dominated by the boolean array s which is of fixed size (64 booleans). The size of the ans array is at most 8 (when all 8 directions have attacking queens). Thus, the space usage is constant and independent of the input size.

Code Explanation (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}  # Efficient set representation
        ans = []
        for a in range(-1, 2):
            for b in range(-1, 2):
                if a or b:  # Skip the (0, 0) case (king's position)
                    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  # Found a queen, stop searching this direction
        return ans

The other language implementations follow the same logic, differing only in syntax and data structures. For example, Java uses a 2D boolean array, while C++ uses a boolean 2D array, Go uses a 2D boolean array and TypeScript utilizes a nested boolean array. The core algorithm remains consistent across all provided languages.