#1958

Medium

LeetCode Problem Workspace

Check if Move is Legal

Determine if a move on an 8x8 board is legal by validating lines in all directions using array and matrix patterns.

Problem Statement

You are given an 8x8 game board represented as a 0-indexed grid, where each cell contains '.', 'W', or 'B'. '.' indicates an empty cell, 'W' a white piece, and 'B' a black piece. Your task is to determine if placing a piece at a specified empty cell is a legal move.

A move is legal if placing your piece results in at least one good line. A good line is a sequence of three or more cells where the endpoints match the placed piece color, and all intermediate cells contain the opposite color. Check all horizontal, vertical, and diagonal directions to validate the move according to this Array plus Matrix pattern.

Examples

Example 1

Input: board = [[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],[".",".",".","W",".",".",".","."],["W","B","B",".","W","W","W","B"],[".",".",".","B",".",".",".","."],[".",".",".","B",".",".",".","."],[".",".",".","W",".",".",".","."]], rMove = 4, cMove = 3, color = "B"

Output: true

'.', '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.

Example 2

Input: board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W"

Output: false

While there are good lines with the chosen cell as a middle cell, there are no good lines with the chosen cell as an endpoint.

Constraints

board.length == board[r].length == 8
0 <= rMove, cMove < 8
board[rMove][cMove] == '.'
color is either 'B' or 'W'.

Solution Approach

Scan All Directions

From the target cell, examine all eight directions: horizontal, vertical, and both diagonals. For each direction, collect consecutive cells until reaching a boundary or an empty cell to identify potential good lines.

Validate Good Lines

For each collected sequence, ensure the endpoints match the player's color and the middle cells contain only the opponent's color. The sequence length must be at least three to qualify as a good line, aligning with the move legality pattern.

Return Result

If any direction forms a valid good line, the move is legal and return true. If no direction satisfies the conditions, return false. This method leverages the matrix and array structure efficiently, covering all enumeration possibilities.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(1) since the board size is fixed at 8x8 and each direction has at most 7 cells to check. Space complexity is O(1) as only temporary variables are used for direction checks without extra structures.

What Interviewers Usually Probe

Asks if all eight directions are considered for a good line
Wants reasoning on why a move is illegal even if it creates a middle line
Checks understanding of endpoint vs middle cells in Array plus Matrix pattern

Common Pitfalls or Variants

Common pitfalls

Only checking one or two directions instead of all eight
Mistaking middle cell placement for endpoint legality
Not handling board boundaries correctly when scanning lines

Follow-up variants

Check if multiple moves are legal in batch
Support boards larger than 8x8 with same good line rules
Determine all legal moves for a given color on the current board

FAQ

What defines a good line in Check if Move is Legal?

A good line has endpoints of the player's color and consecutive opponent pieces in between, with at least three cells total.

Do I need to check diagonals for legality?

Yes, all eight directions including diagonals must be scanned to confirm a move is legal according to the pattern.

Can the move be legal if it only affects middle cells?

No, the move must be an endpoint of a good line; affecting only middle cells does not qualify as legal.

How does the Array plus Matrix pattern apply here?

The board is a matrix, and you enumerate in array directions from the cell to identify sequences that form good lines.

Is the solution scalable beyond 8x8 boards?

Yes, the same directional scanning approach works, but time complexity increases with board size since more cells must be checked.

terminal

Solution

Solution 1: Enumeration

We enumerate all possible directions. For each direction $(a, b)$, we start from $(\textit{rMove}, \textit{cMove})$ and use a variable $\textit{cnt}$ to record the number of cells we have passed. If, during our traversal, we encounter a cell of color $\textit{color}$ and $\textit{cnt} > 1$, then we have found a good line segment and return $\textit{true}$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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

Continue Practicing

#2018 check if word can be placed in crossword #2397 maximum rows covered by columns #1970 last day where you can still cross