NeetCode #579LC-1958MediumGraphs
← Back to All Problems#579 · #1958 · Check if Move is Legal(检查操作是否合法)
📌 Problem Statement & Constraints
You are given an 8x8 board with
'W', 'B' and '.', and a move at (rMove, cMove) with color. The move is legal if it forms a bracket: one or more opponent pieces in a straight line, terminated by one of your own pieces, in at least one of the eight directions. Return whether the move is legal. Constraints: 0 <= rMove, cMove <= 7, color is 'W' or 'B'.💡 Core Algorithmic Approaches
- Place the piece, then examine all eight directions.
- In each direction, skip over consecutive opponent pieces.
- If at least one opponent piece was skipped and the next cell holds your colour, the move is legal.
- Restore the board afterwards (or work on a copy).
💻 Benchmark Python3 Implementation
class Solution:
def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
opp = "W" if color == "B" else "B"
board[rMove][cMove] = color # place the piece
dirs = [(-1, -1), (-1, 0), (-1, 1), (0, -1),
(0, 1), (1, -1), (1, 0), (1, 1)]
legal = False
for dr, dc in dirs:
r, c = rMove + dr, cMove + dc
skipped = 0
while 0 <= r < 8 and 0 <= c < 8 and board[r][c] == opp:
r += dr
c += dc
skipped += 1 # at least one opponent piece
if skipped and 0 <= r < 8 and 0 <= c < 8 and board[r][c] == color:
legal = True # bracketed
break
board[rMove][cMove] = "." # restore
return legal⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1): a fixed 8x8 board and 8 directions.
💾 Space Complexity
O(1): constant.
⚠️ Interview Pitfalls & Follow-ups
- Not requiring at least one opponent piece:
skippedmust be positive. - Checking only the four cardinal directions: all eight count.
- Forgetting the bounds check after the loop: the terminating cell must be on the board.
- Not restoring the board: the caller's state would be corrupted (the judge may reuse the board).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.