Problem Description
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.
Key Insights
- Queens can move any number of squares along a row, column, or diagonal.
- The problem requires checking each queen's position relative to the king's position to determine if it can attack.
- Only queens that are in line with the king (same row, column, or diagonal) will be considered for potential attacks.
- The board is small (8x8), which allows for straightforward iteration over the queens.
Space and Time Complexity
Time Complexity: O(N), where N is the number of queens. We check each queen's position once. Space Complexity: O(1), since we are using a fixed amount of extra space for the output regardless of the input size.
Solution
To solve the problem, we will iterate through each queen's position and check if it can directly attack the king. We will look for queens that share the same row, column, or diagonal as the king and collect their positions in a list to return. The approach uses basic conditional checks to determine if a queen can attack the king based on their coordinates.