1958. Check if Move is Legal Solution

The problem

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 == 8
0 <= rMove, cMove < 8
board[rMove][cMove] == '.'
color is 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.

Python

def check_direction(board, rMove, cMove, dr, dc, color):
    opposite = 'W' if color == 'B' else 'B'
    r, c = rMove + dr, cMove + dc
    found_opposite = False
    while 0 <= r < 8 and 0 <= c < 8:
        if board[r][c] == opposite:
            found_opposite = True
        elif board[r][c] == color:
            return found_opposite
        else:
            break
        r += dr
        c += dc
    return False

class Solution:
    def isLegalMove(self, board, rMove, cMove, color):
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        return any(check_direction(board, rMove, cMove, dr, dc, color) for dr, dc in directions)

Java

class Solution {
    public boolean checkDirection(char[][] board, int rMove, int cMove, int dr, int dc, char color) {
        char opposite = (color == 'B') ? 'W' : 'B';
        int r = rMove + dr;
        int c = cMove + dc;
        boolean foundOpposite = false;
        while (r >= 0 && r < 8 && c >= 0 && c < 8) {
            if (board[r][c] == opposite) {
                foundOpposite = true;
            } else if (board[r][c] == color) {
                return foundOpposite;
            } else {
                break;
            }
            r += dr;
            c += dc;
        }
        return false;
    }

    public boolean isLegalMove(char[][] board, int rMove, int cMove, char color) {
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        for (int[] dir : directions) {
            if (checkDirection(board, rMove, cMove, dir[0], dir[1], color)) {
                return true;
            }
        }
        return false;
    }
}

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool checkDirection(vector<vector<char>>& board, int rMove, int cMove, int dr, int dc, char color) {
        char opposite = (color == 'B') ? 'W' : 'B';
        int r = rMove + dr, c = cMove + dc;
        bool foundOpposite = false;
        while (r >= 0 && r < 8 && c >= 0 && c < 8) {
            if (board[r][c] == opposite) {
                foundOpposite = true;
            } else if (board[r][c] == color) {
                return foundOpposite;
            } else {
                break;
            }
            r += dr;
            c += dc;
        }
        return false;
    }

    bool isLegalMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        for (auto& dir : directions) {
            if (checkDirection(board, rMove, cMove, dir[0], dir[1], color)) {
                return true;
            }
        }
        return false;
    }
};

JavaScript

function checkDirection(board, rMove, cMove, dr, dc, color) {
    let opposite = (color === 'B') ? 'W' : 'B';
    let r = rMove + dr, c = cMove + dc;
    let foundOpposite = false;
    while (r >= 0 && r < 8 && c >= 0 && c < 8) {
        if (board[r][c] === opposite) {
            foundOpposite = true;
        } else if (board[r][c] === color) {
            return foundOpposite;
        } else {
            break;
        }
        r += dr;
        c += dc;
    }
    return false;
}

var isLegalMove = function(board, rMove, cMove, color) {
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]];
    return directions.some(([dr, dc]) => checkDirection(board, rMove, cMove, dr, dc, color));
};

#include <stdbool.h>

bool checkInDirection(char board[8][8], int rMove, int cMove, int dr, int dc, char color) {
    char opposite = (color == 'B') ? 'W' : 'B';
    int r = rMove + dr;
    int c = cMove + dc;
    bool foundOpposite = false;
    while(r >= 0 && r < 8 && c >= 0 && c < 8) {
        if(board[r][c] == opposite) {
            foundOpposite = true;
        } else if(board[r][c] == color) {
            return foundOpposite;
        } else {
            break;
        }
        r += dr;
        c += dc;
    }
    return false;
}

bool isLegalMove(char board[8][8], int rMove, int cMove, char color) {
    int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    for(int i = 0; i < 8; i++) {
        if(checkInDirection(board, rMove, cMove, directions[i][0], directions[i][1], color)) {
            return true;
        }
    }
    return false;
}

public class Solution {
    private bool CheckDirection(char[,] board, int rMove, int cMove, int dr, int dc, char color) {
        char opposite = (color == 'B') ? 'W' : 'B';
        int r = rMove + dr, c = cMove + dc;
        bool foundOpposite = false;
        while (r >= 0 && r < 8 && c >= 0 && c < 8) {
            if (board[r, c] == opposite) {
                foundOpposite = true;
            } else if (board[r, c] == color) {
                return foundOpposite;
            } else {
                break;
            }
            r += dr;
            c += dc;
        }
        return false;
    }

    public bool IsLegalMove(char[,] board, int rMove, int cMove, char color) {
        int[,] directions = new int[,] { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
        for (int i = 0; i < directions.GetLength(0); i++) {
            if (CheckDirection(board, rMove, cMove, directions[i, 0], directions[i, 1], color)) {
                return true;
            }
        }
        return false;
    }
}

The Python solution employs a helper function, check_direction, similar to other languages. The main function isLegalMove uses Python's any function to assess existence of any good line from available directions.

Complexity

Time Complexity: O(8 * n) = O(n), with length of direction check being max 8.
Space Complexity: O(1).

Try this approach in the editor

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.

Python

def is_out_of_bounds(r, c):
    return r < 0 or r >= 8 or c < 0 or c >= 8

class Solution:
    def check_direction(self, board, rMove, cMove, dr, dc, color):
        opposite = 'W' if color == 'B' else 'B'
        r, c = rMove + dr, cMove + dc
        count_opposite = 0

        while not is_out_of_bounds(r, c) and board[r][c] == opposite:
            r += dr
            c += dc
            count_opposite += 1

        if is_out_of_bounds(r, c) or board[r][c] != color or count_opposite < 1:
            return False

        return True

    def isLegalMove(self, board, rMove: int, cMove: int, color: str) -> bool:
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (1, -1), (-1, 1), (-1, -1)]
        return any(self.check_direction(board, rMove, cMove, dr, dc, color) for dr, dc in directions)

Java

class Solution {
    private boolean isOutOfBounds(int r, int c) {
        return r < 0 || r >= 8 || c < 0 || c >= 8;
    }

    private boolean checkDirection(char[][] board, int rMove, int cMove, int dr, int dc, char color) {
        char opposite = (color == 'B') ? 'W' : 'B';
        int r = rMove + dr;
        int c = cMove + dc;
        int countOpposite = 0;

        while (!isOutOfBounds(r, c) && board[r][c] == opposite) {
            r += dr;
            c += dc;
            countOpposite++;
        }
        if (isOutOfBounds(r, c) || board[r][c] != color || countOpposite < 1) return false;
        return true;
    }

    public boolean isLegalMove(char[][] board, int rMove, int cMove, char color) {
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        for (int[] dir : directions) {
            if (checkDirection(board, rMove, cMove, dir[0], dir[1], color)) {
                return true;
            }
        }
        return false;
    }
}

C++

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool isOutOfBounds(int r, int c) {
        return r < 0 || r >= 8 || c < 0 || c >= 8;
    }

    bool checkDirection(vector<vector<char>>& board, int rMove, int cMove, int dr, int dc, char color) {
        char opposite = (color == 'B') ? 'W' : 'B';
        int r = rMove + dr, c = cMove + dc;
        int countOpposite = 0;

        while (!isOutOfBounds(r, c) && board[r][c] == opposite) {
            r += dr;
            c += dc;
            countOpposite++;
        }
        if (isOutOfBounds(r, c) || board[r][c] != color || countOpposite < 1) return false;
        return true;
    }

    bool isLegalMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
        for (auto& dir : directions) {
            if (checkDirection(board, rMove, cMove, dir[0], dir[1], color)) {
                return true;
            }
        }
        return false;
    }
};

JavaScript

function isOutOfBounds(r, c) {
    return r < 0 || r >= 8 || c < 0 || c >= 8;
}

function checkDirection(board, rMove, cMove, dr, dc, color) {
    let opposite = (color === 'B') ? 'W' : 'B';
    let r = rMove + dr, c = cMove + dc;
    let countOpposite = 0;

    while (!isOutOfBounds(r, c) && board[r][c] === opposite) {
        r += dr;
        c += dc;
        countOpposite++;
    }

    if (isOutOfBounds(r, c) || board[r][c] !== color || countOpposite < 1) return false;
    return true;
}

var isLegalMove = function(board, rMove, cMove, color) {
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]];
    return directions.some(([dr, dc]) => checkDirection(board, rMove, cMove, dr, dc, color));
};

#include <stdbool.h>

bool isOutOfBounds(int r, int c) {
    return r < 0 || r >= 8 || c < 0 || c >= 8;
}

bool checkDirection(char board[8][8], int rMove, int cMove, int dr, int dc, char color) {
    char opposite = (color == 'B') ? 'W' : 'B';
    int r = rMove + dr;
    int c = cMove + dc;
    int countOpposite = 0;

    while (!isOutOfBounds(r, c) && board[r][c] == opposite) {
        r += dr;
        c += dc;
        countOpposite++;
    }
    if (isOutOfBounds(r, c) || board[r][c] != color || countOpposite < 1) return false;
    return true;
}

bool isLegalMove(char board[8][8], int rMove, int cMove, char color) {
    int directions[8][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    for (int i = 0; i < 8; i++) {
        if (checkDirection(board, rMove, cMove, directions[i][0], directions[i][1], color)) {
            return true;
        }
    }
    return false;
}

public class Solution {
    private bool IsOutOfBounds(int r, int c) {
        return r < 0 || r >= 8 || c < 0 || c >= 8;
    }

    private bool CheckDirection(char[,] board, int rMove, int cMove, int dr, int dc, char color) {
        char opposite = (color == 'B') ? 'W' : 'B';
        int r = rMove + dr, c = cMove + dc;
        int countOpposite = 0;

        while (!IsOutOfBounds(r, c) && board[r, c] == opposite) {
            r += dr;
            c += dc;
            countOpposite++;
        }

        if (IsOutOfBounds(r, c) || board[r, c] != color || countOpposite < 1) return false;
        return true;
    }

    public bool IsLegalMove(char[,] board, int rMove, int cMove, char color) {
        int[,] directions = new int[,] { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1} };
        for (int i = 0; i < directions.GetLength(0); i++) {
            if (CheckDirection(board, rMove, cMove, directions[i, 0], directions[i, 1], color)) {
                return true;
            }
        }
        return false;
    }
}

The Python solution utilizes inline boundary checks to prevent out-of-range errors during evaluation. Leverages counting of intermediary opposite colors to ascertain line legitimacy.

Complexity

Time Complexity: O(8 * n).
Space Complexity: O(1).

Try this approach in the editor

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).

TypeScript

function checkMove(board: string[][], rMove: number, cMove: number, color: string): boolean {
    for (let a = -1; a <= 1; ++a) {
        for (let b = -1; b <= 1; ++b) {
            if (a === 0 && b === 0) {
                continue;
            }
            let [i, j] = [rMove, cMove];
            let cnt = 0;
            while (0 <= i + a && i + a < 8 && 0 <= j + b && j + b < 8) {
                i += a;
                j += b;
                if (++cnt > 1 && board[i][j] === color) {
                    return true;
                }
                if (board[i][j] === color || board[i][j] === '.') {
                    break;
                }
            }
        }
    }
    return false;
}

func checkMove(board [][]byte, rMove int, cMove int, color byte) bool {
	for a := -1; a <= 1; a++ {
		for b := -1; b <= 1; b++ {
			if a == 0 && b == 0 {
				continue
			}
			i, j := rMove, cMove
			cnt := 0
			for 0 <= i+a && i+a < 8 && 0 <= j+b && j+b < 8 {
				i += a
				j += b
				cnt++
				if cnt > 1 && board[i][j] == color {
					return true
				}
				if board[i][j] == color || board[i][j] == '.' {
					break
				}
			}
		}
	}
	return false
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Directional Check Method	Time Complexity: O(8 * n) = O(n), with length of direction check being max 8. Space Complexity: O(1).
Line Detection with Boundary Check	Time Complexity: O(8 * n). Space Complexity: O(1).
Enumeration	–

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

Frequently asked questions

Is Check if Move is Legal easy or hard?

The problem is rated Medium because it requires careful handling of grid boundaries and directional traversal. The core logic is straightforward, but missing edge cases—such as immediately encountering empty cells or stopping before finding your own piece—can lead to incorrect solutions.

Check if Move is Legal Python/Java solution

Most implementations define an array of eight direction offsets and iterate through them. For each direction, move step-by-step while validating the opponent sequence and board boundaries. The same logic translates cleanly across Python, Java, C++, C#, and JavaScript.

How to solve Check if Move is Legal in O(n)?

Treat each of the eight directions as a linear scan. Move step-by-step from the starting cell, ensuring the first cell is an opponent piece, then continue until you either reach the player's piece or hit an empty cell or boundary. If any direction ends with the player's color after at least one opponent piece, the move is valid.

What is the best approach for Check if Move is Legal?

The directional scanning approach is the standard solution. From the candidate cell, iterate through the eight possible directions and check for a sequence of opponent pieces followed by the player's piece. This directly models the Othello rule and runs in O(8 * n) time, which becomes O(1) on the fixed 8x8 board.

Is Check if Move is Legal asked at Google/Amazon/Meta?

Matrix traversal and board-game simulation problems like this frequently appear in interviews at large tech companies. While this exact problem may vary, the pattern of directional scanning in grids is common in interviews at companies such as Amazon, Google, and Meta.

What data structure is used in Check if Move is Legal?

The primary data structure is a 2D array representing the game board. The algorithm also uses a small list of direction vectors to iterate through horizontal, vertical, and diagonal movements in the matrix.

What is the time complexity of Check if Move is Legal?

The algorithm checks at most eight directions and scans up to 7 cells per direction on the board. This results in O(8 * n) time in a generalized grid or effectively O(1) for the fixed 8x8 board used in the problem. Space complexity remains O(1) because only a few directional variables are used.

Check if Move is Legal solution and explanation

The problem

Approach overview

Approach 1: Directional Check Method

Approach 2: Line Detection with Boundary Check

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Check if Move is Legal solution and explanation

The problem

Approach overview

Approach 1: Directional Check Method

Approach 2: Line Detection with Boundary Check

Approach 3: Enumeration

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems