1222. Queens That Can Attack the King LeetCode Solution
In this guide, you will get 1222. Queens That Can Attack the King LeetCode Solution with the best time and space complexity. The solution to Queens That Can Attack the King problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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).
1 <= queens.length < 64
queens[i].length == king.length == 2
0 <= xQueeni, yQueeni, xKing, yKing < 8
All the given positions are unique.
Complexity Analysis
Time Complexity:
Space Complexity:
1222. Queens That Can Attack the King LeetCode Solution in C++
class Solution {
public:
vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens,
vector<int>& king) {
vector<vector<int>> ans;
unordered_set<int> queensSet;
for (vector<int>& queen : queens)
queensSet.insert(hash(queen[0], queen[1]));
vector<vector<int>> directions = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
{0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (vector<int> d : directions)
for (int i = king[0] + d[0], j = king[1] + d[1];
<= i && i < 8 && 0 <= j && j < 8; i += d[0], j += d[1])
if (queensSet.contains(hash(i, j))) {
ans.push_back({i, j});
break;
}
return ans;
}
private:
int hash(int i, int j) {
return i * 8 + j;
}
}; /* code provided by PROGIEZ */
1222. Queens That Can Attack the King LeetCode Solution in Java
class Solution {
public List<List<Integer>> queensAttacktheKing(int[][] queens, int[] king) {
List<List<Integer>> ans = new ArrayList<>();
Set<Integer> queensSet = new HashSet<>();
for (int[] queen : queens)
queensSet.add(hash(queen[0], queen[1]));
int[][] directions =
new int[][] {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
for (int[] d : directions)
for (int i = king[0] + d[0], j = king[1] + d[1]; 0 <= i && i < 8 && 0 <= j && j < 8;
i += d[0], j += d[1])
if (queensSet.contains(hash(i, j))) {
ans.add(Arrays.asList(i, j));
break;
}
return ans;
}
private int hash(int i, int j) {
return i * 8 + j;
}
} // code provided by PROGIEZ
1222. Queens That Can Attack the King LeetCode Solution in Python
class Solution:
def queensAttacktheKing(self, queens: list[list[int]],
king: list[int]) -> list[list[int]]:
ans = []
queens = {(i, j) for i, j in queens}
for d in [
[-1, -1],
[-1, 0],
[-1, 1],
[0, -1],
[0, 1],
[1, -1],
[1, 0],
[1, 1]]:
i = king[0] + d[0]
j = king[1] + d[1]
while 0 <= i < 8 and 0 <= j < 8:
if (i, j) in queens:
ans.append([i, j])
break
i += d[0]
j += d[1]
return ans # code by PROGIEZ
