MediumNo. 1222
Queens That Can Attack the King — LeetCode 1222 Python Solution
- Pattern
- Matrix and Grid
- Topics
- Array, Matrix, Simulation
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- 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).
Python solution
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}
ans = []
for a in range(-1, 2):
for b in range(-1, 2):
if a or b:
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
return ansComplexity
- Time
- O(n2)
- Space · auxiliary
- O(n2)
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 1222. Queens That Can Attack the King is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Matrix.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0054 | Spiral Matrix | Medium |
| 0059 | Spiral Matrix II | Medium |
| 0289 | Game of Life | Medium |
| 0498 | Diagonal Traverse | Medium |
| 0566 | Reshape the Matrix | Easy |
| 0867 | Transpose Matrix | Easy |
Frequently asked questions
- How hard is LeetCode 1222. Queens That Can Attack the King?
LeetCode 1222. Queens That Can Attack the King is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1222. Queens That Can Attack the King?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 1222. Queens That Can Attack the King?
The Python solution on this page uses O(n2) auxiliary space.
- What topics does LeetCode 1222. Queens That Can Attack the King cover?
LeetCode 1222. Queens That Can Attack the King is tagged Array, Matrix and Simulation on LeetCode.