⚡Flashcard Drill➔
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

  1. Place the piece, then examine all eight directions.
  2. In each direction, skip over consecutive opponent pieces.
  3. If at least one opponent piece was skipped and the next cell holds your colour, the move is legal.
  4. 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: skipped must 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems