Check if Move is Legal - Solution & Explanation
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'.
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] == '.'coloris either'B'or'W'.
Approach Overview
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 1: Directional Check Method
This approach involves checking each of the 8 possible directions (vertical, horizontal, and diagonal) from the given move position to determine if forming a good line is possible. For each direction, traverse until you find a move that completes a good line according to the rules.
The C solution defines a helper function checkInDirection that checks if a good line is formed in the specified direction (denoted by dr and dc). The main function, isLegalMove, iterates over all 8 directions and calls checkInDirection for each, returning true if any direction confirms a good line.
Complexity
Time Complexity: O(8 * n) = O(n), where n is the max possible travel in each direction (here less than or equal to 8).
Space Complexity: O(1).
Approach 2: Line Detection with Boundary Check
This approach enhances the directional check by incorporating specific boundary validations. It involves examining the line in both forward and reverse directions from the intended position, ensuring a valid line formation before reverting colors.
This solution refines line checking by validating boundary conditions. The isOutOfBounds function ensures no illegal access occurs, while checkDirection confirms the opposite color count is sufficient prior to accepting the line as valid.
Complexity
Time Complexity: O(8 * n).
Space Complexity: O(1).
Approach 3: Enumeration
We enumerate all possible directions. For each direction (a, b), we start from (rMove, cMove) and use a variable cnt to record the number of cells we have passed. If, during our traversal, we encounter a cell of color color and cnt > 1, then we have found a good line segment and return true.
If no good line segments are found after the enumeration, we return false.
The time complexity is O(m + n), where m is the number of rows and n is the number of columns in board, with m = n = 8 in this problem. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Directional Check Method | Time Complexity: O(8 * n) = O(n), where n is the max possible travel in each direction (here less than or equal to 8). |
| Line Detection with Boundary Check | Time Complexity: O(8 * n). |
| Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Check if Move is Legal - Biweekly Leetcode Contest - 1958 - Python • NeetCode • 9,891 views views
Watch 4 more video solutions →Frequently Asked Questions
Is Check if Move is Legal easy or hard?
Check if Move is Legal Python/Java solution
How to solve Check if Move is Legal in O(n)?
What is the best approach for Check if Move is Legal?
Is Check if Move is Legal asked at Google/Amazon/Meta?
What data structure is used in Check if Move is Legal?
What is the time complexity of Check if Move is Legal?
Ready to solve this problem?
Practice Check if Move is Legal with our built-in code editor and test cases.
Practice on FleetCode