Leetcode #1958: Check if Move is Legal
In this guide, we solve Leetcode #1958 Check if Move is Legal in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
You are given a 0-indexed 8 x 8 grid board, where board[r][c] represents the cell (r, c) on a game board. On the board, free cells are represented by '.', white cells are represented by 'W', and black cells are represented by 'B'.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Array, Enumeration, Matrix
Intuition
Grid problems are easiest when you define clear row/column boundaries.
A consistent traversal order prevents off-by-one errors.
Approach
Iterate by rows, columns, or layers depending on the requirement.
Keep bounds updated as the traversal progresses.
Steps:
- Define bounds or directions.
- Visit cells in order.
- Update result and move bounds.
Example
Input: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"
Output: true
Explanation: '.', 'W', and 'B' are represented by the colors blue, white, and black respectively, and cell (rMove, cMove) is marked with an 'X'.
The two good lines with the chosen cell as an endpoint are annotated above with the red rectangles.
Python Solution
class Solution:
def checkMove(
self, board: List[List[str]], rMove: int, cMove: int, color: str
) -> bool:
for a in range(-1, 2):
for b in range(-1, 2):
if a == 0 and b == 0:
continue
i, j = rMove, cMove
cnt = 0
while 0 <= i + a < 8 and 0 <= j + b < 8:
cnt += 1
i, j = i + a, j + b
if cnt > 1 and board[i][j] == color:
return True
if board[i][j] in (color, "."):
break
return False
Complexity
The time complexity is , where is the number of rows and is the number of columns in , with in this problem. The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.