Leetcode 1222: Queens That Can Attack the King
On an 8x8 chessboard, there are multiple black queens and one white king. You are given the positions of the black queens and the white king. Your task is to find all the black queens that can directly attack the white king. A queen can attack the king if they share the same row, column, or diagonal.
Problem
Approach
Steps
Complexity
Input: You are given two inputs: a 2D array 'queens' where each element represents the position of a black queen, and a 1D array 'king' representing the position of the white king.
Example: queens = [[2, 3], [1, 1], [5, 2], [0, 7], [4, 6]], king = [2, 2]
Constraints:
• 1 <= queens.length < 64
• queens[i].length == king.length == 2
• 0 <= xQueeni, yQueeni, xKing, yKing < 8
• All the given positions are unique.
Output: Return a list of coordinates of the black queens that can attack the king.
Example: [[2, 3], [5, 2], [1, 1]]
Constraints:
• The output should include all the black queens that can attack the king, in any order.
Goal: Find all queens that can attack the white king.
Steps:
• 1. Mark the positions of all black queens on the chessboard.
• 2. Iterate over all possible directions from the king's position.
• 3. Check if there is a queen in each direction.
• 4. If a queen is found, add it to the result list and stop checking further in that direction.
Goal: You must work within the limits of the 8x8 chessboard and handle up to 63 black queens.
Steps:
• The chessboard is fixed in size at 8x8.
• There can be up to 63 queens on the board.
Assumptions:
• Each position is unique, meaning no two queens or the king can occupy the same square.
• Input: Input: queens = [[2, 3], [1, 1], [5, 2], [0, 7], [4, 6]], king = [2, 2]
• Explanation: The queens at positions (2, 3), (5, 2), and (1, 1) are in the same row, column, or diagonal as the king. Thus, they can directly attack the king.
Approach: The approach to solving this problem is to simulate the chessboard and check the positions of the queens relative to the king, considering all 8 directions.
Observations:
• A queen can attack in any of the 8 directions (up, down, left, right, and the four diagonals).
• We can traverse each direction from the king and check for queens in the line of attack.
Steps:
• 1. Create a chessboard with the queens' positions marked.
• 2. Iterate through each direction from the king's position.
• 3. For each direction, move step-by-step and check if a queen is encountered. Stop if a queen is found or if the edge of the board is reached.
Empty Inputs:
• There are no queens on the board.
Large Inputs:
• There are 63 queens on the board, with the king in the center.
Special Values:
• The king is at a corner or edge of the board.
Constraints:
• The problem guarantees unique positions, so no two queens or the king will occupy the same space.
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& k) {
vector<vector<bool>> b(8, vector<bool>(8, false));
for(auto q: queens)
b[q[0]][q[1]] = true;
vector<vector<int>> res;
for(int i = -1; i <= 1; i++)
for(int j = -1; j <= 1; j++) {
if ( i == 0 && j == 0) continue;
int x = k[0] + i, y = k[1] + j;
while(min(x, y) >= 0 && max(x, y) < 8) {
if(b[x][y]) {
res.push_back({x, y});
break;
}
x += i;
y += j;
}
}
return res;
}
1 : Function Definition
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& k) {
This is the function definition. The function accepts a list of queen positions and the king's position as inputs.
2 : Matrix Initialization
vector<vector<bool>> b(8, vector<bool>(8, false));
Here, we initialize a 2D boolean vector `b` of size 8x8 representing the chessboard, where each position is initially set to `false`.
3 : Queen Position Setup
for(auto q: queens)
This loop iterates through all queen positions to mark them as `true` on the chessboard `b`.
4 : Mark Queen on Board
b[q[0]][q[1]] = true;
This line marks the corresponding position on the chessboard as `true` for each queen.
5 : Result Initialization
vector<vector<int>> res;
This initializes a vector `res` that will hold the positions of queens that can attack the king.
6 : Direction Loop Setup
for(int i = -1; i <= 1; i++)
This loop will check all 8 possible directions (vertical, horizontal, and diagonal) around the king.
7 : Direction Loop Inner
for(int j = -1; j <= 1; j++) {
This loop works in conjunction with the previous loop to examine each direction surrounding the king.
8 : Skip Center Position
if ( i == 0 && j == 0) continue;
This line ensures that the center position (the king's position) is skipped, as we want to check surrounding squares.
9 : Calculate Adjacent Position
int x = k[0] + i, y = k[1] + j;
This calculates the adjacent position relative to the king's position by adding the offsets `i` and `j`.
10 : Position Check Loop
while(min(x, y) >= 0 && max(x, y) < 8) {
This while loop checks if the calculated position is within the bounds of the chessboard (8x8 grid).
11 : Queen Detection
if(b[x][y]) {
Here, we check if there is a queen at the calculated position.
12 : Add Attack Position
res.push_back({x, y});
If a queen is found, the position is added to the result list `res`.
13 : Break Loop
break;
Once a queen is found in a given direction, the loop breaks to avoid further searching in that direction.
14 : Move to Next Position
x += i;
This moves the check to the next position in the current direction by adding `i` to `x`.
15 : Move to Next Position (y)
y += j;
Similarly, this moves the check to the next position in the current direction by adding `j` to `y`.
16 : Return Result
return res;
The function returns the list `res`, which contains the positions where queens can attack the king.
Best Case: O(1) - If no queens are in line with the king.
Average Case: O(8) - Each direction will take at most 8 steps.
Worst Case: O(8) - In the worst case, we check all 8 directions.
Description: The time complexity is primarily dependent on the 8 possible directions from the king's position.
Best Case: O(1)
Worst Case: O(1) - The board is fixed at 8x8, and we only store the positions of the queens and king.
Description: The space complexity is constant because the chessboard size is fixed and we only need space for the queens and the king.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus