Watch 6 video solutions for Check if Move is Legal, a medium level problem involving Array, Matrix, Enumeration. This walkthrough by NeetCode has 9,740 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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'.
Each move in this game consists of choosing a free cell and changing it to the color you are playing as (either white or black). However, a move is only legal if, after changing it, the cell becomes the endpoint of a good line (horizontal, vertical, or diagonal).
A good line is a line of three or more cells (including the endpoints) where the endpoints of the line are one color, and the remaining cells in the middle are the opposite color (no cells in the line are free). You can find examples for good lines in the figure below:
Given two integers rMove and cMove and a character color representing the color you are playing as (white or black), return true if changing cell (rMove, cMove) to color color is a legal move, or false if it is not legal.
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 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.
Example 2:
Input: board = [[".",".",".",".",".",".",".","."],[".","B",".",".","W",".",".","."],[".",".","W",".",".",".",".","."],[".",".",".","W","B",".",".","."],[".",".",".",".",".",".",".","."],[".",".",".",".","B","W",".","."],[".",".",".",".",".",".","W","."],[".",".",".",".",".",".",".","B"]], rMove = 4, cMove = 4, color = "W" Output: false Explanation: 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 == 80 <= rMove, cMove < 8board[rMove][cMove] == '.'color is either 'B' or 'W'.Problem Overview: You’re given an 8×8 Othello (Reversi) board and a position where a player wants to place a piece. The move is legal only if at least one direction forms the pattern: one or more opponent pieces followed by a piece of the same color. The task is to check every direction from the placed cell and confirm whether such a capture line exists.
The board traversal relies heavily on arrays, directional movement in a matrix, and systematic enumeration of all possible directions.
Approach 1: Directional Check Method (O(8 * n) time, O(1) space)
Start from the candidate cell and explore the eight possible directions: horizontal, vertical, and diagonal. For each direction, move one step at a time. The first adjacent cell must contain the opponent’s piece; otherwise that direction cannot form a valid capture. Continue walking in the same direction while pieces belong to the opponent. If the sequence eventually ends with the player’s own color, the move is legal. If the path hits an empty cell or goes out of bounds first, the direction fails. Since the board size is fixed (8×8), the scan touches at most 7 cells per direction, giving constant practical runtime. The algorithm uses simple iteration and boundary checks without extra memory.
Approach 2: Line Detection with Boundary Check (O(8 * n) time, O(1) space)
This variation treats each direction as a potential "line" and validates it in two phases. First, step one cell in the chosen direction and ensure the piece belongs to the opponent. Second, keep advancing while the pieces remain opponent colored. The scan stops when the sequence breaks or reaches the board boundary. If the traversal ends on a cell containing the current player's piece and the line length is at least two (opponent pieces in between), the direction forms a valid capture. Structuring the logic this way makes the rule easier to reason about and reduces mistakes around edge cases such as immediately hitting empty cells or borders.
Recommended for interviews: The Directional Check Method is what most interviewers expect. It shows you understand grid traversal and directional enumeration. The Line Detection variant expresses the same idea with slightly clearer validation steps. Demonstrating either approach correctly—especially handling boundaries and opponent sequences—signals strong control over matrix iteration problems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Directional Check Method | O(8 * n) (O(1) on 8x8 board) | O(1) | General solution for Othello-style move validation by scanning all directions |
| Line Detection with Boundary Check | O(8 * n) (O(1) on fixed grid) | O(1) | When you want clearer step-by-step validation of capture lines |