Queens That Can Attack The King
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] = [x_Queeni, y_Queeni] 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.
Problem Explanation
This problem requires one to be aware of the standard chess move for the queen. In chess, the queen can move to any cell of the row and column it is standing in and even to any cell in both of its diagonals.
This problem involves an 8x8 chessboard where black queens and a white king are placed at specified coordinates.
You need to determine which queens can directly attack the king based on standard chess movement rules. Queens can attack in any horizontal, vertical, or diagonal direction.
The goal is to identify and return the coordinates of all queens that can attack the king directly, considering any obstacles posed by other queens along the path.
Examples
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).
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 <= xQueen_i, yQueen_i, xKing, yKing < 8
- All the given positions are unique.
This problem is all about analyzing the attack patterns of queens on a chessboard and determining which ones can directly threaten the king. We'll focus on checking rows, columns, and diagonals for potential threats. Let’s break this down and solve it systematically.
Brute Force Approach
Intuition
Let's think of considering all the queens that are on the same row, column or on the same diagonal as our king then we can count them in our answer but will it be the correct solution?
Well .. No, Considering all the queens say on same row we miss the point of the question where we only count those queens who are directly attacking our king if there are multiple queens on the same row only one infront can directly attack our queen while rest are blocked by other queens, this is a key edge case while considering to solve this problem.
Since queens can move horizontally, vertically, and diagonally, we need to check all eight possible directions from the king’s position. If multiple queens are in the same row, column, or diagonal as the king, only the closest one can attack, as the others are blocked. Therefore, we start from the king's position and expand outward step by step in each direction until we either find a queen or reach the edge of the board. As soon as we find a queen in a direction, we stop further exploration in that direction because that queen is the only one that can attack from that path. This approach ensures that we check all possible directions and capture the closest attacking queens.
Why do we stop searching a direction as soon as we find a queen?
Once we find a queen in a direction, no other queen beyond it can attack the king because queens cannot jump over other queens. The first queen blocks the path, making any other queen behind it irrelevant for that direction.
What if the king is at the edge or corner of the board?
If the king is at the edge or a corner, some of the eight directions will be out of bounds immediately. For example, a king in the top-left corner (0, 0) cannot move left or up, so only the remaining directions need to be checked. This does not change the logic of the solution but reduces the number of directions to explore.
Approach
- Initialize Board:
- Create an 8x8 chessboard initialized to false (representing no queens).
- Mark Queen Positions:
- For each queen in the list queens, mark the corresponding position on the board as true.
- Initialize Result List:
- Create an empty list ans to store the positions of queens that can attack the king.
- Check 8 Directions:
- For each direction (i, j) from (-1, -1) to (1, 1), except the position (0, 0) (which is the king's position):
- Initialize (x, y) to the king's position plus the direction (i, j).
- While (x, y) is within the bounds of the chessboard:
- If there is a queen at (x, y), add its position to the result list ans and stop further checks in this direction.
- Otherwise, move one step further in the direction (i, j).
- Return Result:
- Return the list ans containing the positions of queens that can attack the king.
Dry Run
Let’s perform a detailed dry run of the code using the given input:
Input:
- Queens: [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]]
- King: [0,0]
Output (Expected): [[0,1],[1,0],[3,3]]
Step-by-Step Execution
- Initialize the chessboard:
An 8x8 grid board is created and initialized with all values set to false (indicating no queens are present initially). - Mark queens on the board:
For each queen in queens:
Board state after marking queens:
T F T F T F F F
T F F F F F F F
F F F F F T F F
F F F T F F F F
T F F F F F F F
F F F F F F F F
F F F F F F F F
F F F F F F F F - Mark board[0][1] = true → Queen at position (0,1).
- Mark board[1][0] = true → Queen at position (1,0).
- Mark board[4][0] = true → Queen at position (4,0).
- Mark board[0][4] = true → Queen at position (0,4).
- Mark board[3][3] = true → Queen at position (3,3).
- Mark board[2][4] = true → Queen at position (2,4).
- Initialize the result container:
ans = [] (to store queens that can attack the king). - Check 8 directions around the king:
Iterate over all directions (i, j) where i and j range from -1 to 1 (excluding (0,0)).
Direction-wise ExecutionDirection (-1, -1):
- Start at (x, y) = (0 + -1, 0 + -1) = (-1, -1).
- Out of bounds immediately, skip this direction.
Direction (-1, 0):
- Start at (x, y) = (-1, 0).
- Out of bounds immediately, skip this direction.
Direction (-1, 1):
- Start at (x, y) = (-1, 1).
- Out of bounds immediately, skip this direction.
Direction (0, -1):
- Start at (x, y) = (0, -1).
- Out of bounds immediately, skip this direction.
Direction (0, 1):
- Start at (x, y) = (0, 1):
- board[0][1] = true → Queen found at (0,1).
- Add [0,1] to ans.
- Stop checking further in this direction.
- ans = [[0,1]].
Direction (1, -1):
- Start at (x, y) = (1, -1).
- Out of bounds immediately, skip this direction.
Direction (1, 0):
- Start at (x, y) = (1, 0):
- board[1][0] = true → Queen found at (1,0).
- Add [1,0] to ans.
- Stop checking further in this direction.
- ans = [[0,1],[1,0]].
Direction (1, 1):
- Start at (x, y) = (1, 1):
- board[1][1] = false → No queen.
- Move to (x, y) = (2, 2).
- board[2][2] = false → No queen.
- Move to (x, y) = (3, 3).
- board[3][3] = true → Queen found at (3,3).
- Add [3,3] to ans.
- Stop checking further in this direction.
- ans = [[0,1],[1,0],[3,3]].
Final Output:
The positions of queens that can attack the king are [[0,1],[1,0],[3,3]].
Return: [[0,1],[1,0],[3,3]].
Code for All Languages
C++
class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
// Initialize an 8x8 chessboard with all values set to false (no queens)
vector<vector<bool>> board(8, vector<bool>(8, false));
// Mark the positions of all queens on the chessboard as true
for (auto& q : queens)
board[q[0]][q[1]] = true;
// To store the result of queens that can attack the king
vector<vector<int>> ans;
// Check 8 possible directions (horizontal, vertical, and diagonal)
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
// Skip the king's own position
if (i == 0 && j == 0) continue;
// Initialize the position to start checking from the king's position
int x = king[0] + i, y = king[1] + j;
// Move in the direction (i, j) until out of bounds or a queen is found
while (min(x, y) >= 0 && max(x, y) < 8) {
// If a queen is found, add its position to the result and stop checking further
if (board[x][y]) {
ans.push_back({x, y});
break;
}
// Move one step further in the current direction
x += i;
y += j;
}
}
}
// Return the positions of queens that can attack the king
return ans;
}
};
Java
import java.util.*;
class Solution {
public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
// Initialize an 8x8 chessboard with all values set to false (no queens)
boolean[][] board = new boolean[8][8];
// Mark the positions of all queens on the chessboard as true
for (int[] q : queens)
board[q[0]][q[1]] = true;
// To store the result of queens that can attack the king
List<List<Integer>> ans = new ArrayList<>();
// Check 8 possible directions (horizontal, vertical, and diagonal)
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
// Skip the king's own position
if (i == 0 && j == 0) continue;
// Initialize the position to start checking from the king's position
int x = king[0] + i, y = king[1] + j;
// Move in the direction (i, j) until out of bounds or a queen is found
while (x >= 0 && y >= 0 && x < 8 && y < 8) {
// If a queen is found, add its position to the result and stop checking further
if (board[x][y]) {
ans.add(Arrays.asList(x, y));
break;
}
// Move one step further in the current direction
x += i;
y += j;
}
}
}
// Return the positions of queens that can attack the king
return ans;
}
}
Python
from typing import List
class Solution:
def queensAttacktheKing(self, queens: List[List[int]], king: List[int]) -> List[List[int]]:
# Initialize an 8x8 chessboard with all values set to False (no queens)
board = [[False] * 8 for _ in range(8)]
# Mark the positions of all queens on the chessboard as True
for q in queens:
board[q[0]][q[1]] = True
# To store the result of queens that can attack the king
ans = []
# Check 8 possible directions (horizontal, vertical, and diagonal)
for i in range(-1, 2):
for j in range(-1, 2):
# Skip the king's own position
if i == 0 and j == 0:
continue
# Initialize the position to start checking from the king's position
x, y = king[0] + i, king[1] + j
# Move in the direction (i, j) until out of bounds or a queen is found
while 0 <= x < 8 and 0 <= y < 8:
# If a queen is found, add its position to the result and stop checking further
if board[x][y]:
ans.append([x, y])
break
# Move one step further in the current direction
x += i
y += j
# Return the positions of queens that can attack the king
return ans
Javascript
var queensAttacktheKing = function(queens, king) {
// Initialize an 8x8 chessboard with all values set to false (no queens)
let board = Array.from({ length: 8 }, () => Array(8).fill(false));
// Mark the positions of all queens on the chessboard as true
for (let q of queens) {
board[q[0]][q[1]] = true;
}
// To store the result of queens that can attack the king
let ans = [];
// Check 8 possible directions (horizontal, vertical, and diagonal)
for (let i = -1; i <= 1; i++) {
for (let j = -1; j <= 1; j++) {
// Skip the king's own position
if (i === 0 && j === 0) continue;
// Initialize the position to start checking from the king's position
let x = king[0] + i, y = king[1] + j;
// Move in the direction (i, j) until out of bounds or a queen is found
while (x >= 0 && x < 8 && y >= 0 && y < 8) {
// If a queen is found, add its position to the result and stop checking further
if (board[x][y]) {
ans.push([x, y]);
break;
}
// Move one step further in the current direction
x += i;
y += j;
}
}
}
// Return the positions of queens that can attack the king
return ans;
};Time Complexity : O(n)
The time complexity of the code is O(n), where n is the number of queens. Initializing the 8x8 chessboard is done in constant time because the board size is fixed.
Marking the positions of n queens on the board takes O(n), as it involves updating the board for each queen.
The directional search for queens that can attack the king checks up to 8 directions, and in each direction, it may traverse up to 8 squares. However, since the board size is fixed, this search is constant in time.
Constructing the result list of attacking queens also takes O(n), as it depends on the number of queens.
Overall, the dominant factor is the O(n) operation for marking the queens and constructing the result, making the total time complexity O(n).
Space Complexity : O(1)
Auxiliary Space Complexity
The auxiliary space is the extra space used by the algorithm apart from the input and output. In this code, the auxiliary space includes:
- An 8x8 chessboard (board) of boolean values, which takes 8×8=64 cells. Since each boolean value requires 1 byte, the space used by the board is 64 bytes or O(1), as the board size is fixed.
- A result vector ans, which stores the positions of the queens that can attack the king. In the worst case, there are at most 8 attacking queens, so the space used by ans is 8×28 integers (two coordinates per queen). This is also O(1) because the maximum size is fixed and independent of the input size.
Thus, the auxiliary space is O(1).
Total Space Complexity
The total space includes:
- The space for the input, which is the list of queens (queens) and the king's position (king). The space for queens is proportional to the number of queens, n, as each queen requires two integers for its position. So, the space for queens is O(n).
- The space for king, which is always O(1), as it contains a fixed number of integers (two).
- The auxiliary space, as calculated above, is O(1).
Thus, the total space is O(n), dominated by the space required for the input list of queens.
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
We are tasked with determining the minimum number of moves required for a white rook and a white bishop to capture a black queen on a 1-indexed 8x8 chessboard. The rook moves vertically or horizontally, while the bishop moves diagonally, both restricted by obstacles. The goal is to calculate the shortest path to the queen for either piece.
We need to determine the number of black pawns ('p') that a white rook ('R') can attack on an 8x8 chessboard. The rook moves horizontally or vertically until it encounters a piece or the board's edge, and it cannot pass through other pieces like bishops ('B') or pawns ('p'). The task is to count how many pawns are reachable in one move.