1958. Check if Move Is Legal - Explanation

Description

An 8 by 8 board contains empty cells (.), black pieces (B), and white pieces (W). You want to place a piece of color in the empty cell [rMove, cMove].

The move is legal if, starting at the new piece and following one of the eight horizontal, vertical, or diagonal directions, you encounter one or more consecutive pieces of the opposite color followed immediately by an existing piece of your own color. There must be no empty cell along this line.

The new piece must be an endpoint of the line, and the line must contain at least three cells in total. Return true if at least one such line exists; otherwise return false. Coordinates are zero-based.

The dashed square marks the proposed move.

Example 1:

Check if Move is Legal, example 1: illustration of the example

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

Output: true

Explanation: Placing B at [0,0] creates the horizontal line B, W, B ending at [0,2]. The new piece is an endpoint and the one middle piece has the opposite color.

Example 2:

Check if Move is Legal, example 2: illustration of the example

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

Output: true

Explanation: Placing W at [0,0] creates a diagonal line through [1,1] and [2,2] to the W at [3,3]. Both middle pieces are B, so the move is legal.

Example 3:

Check if Move is Legal, example 3: illustration of the example

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

Output: false

Explanation: The neighboring B has the same color as the new piece. No opposite-color piece lies between two B endpoints, and every other direction is empty, so the move is illegal.

Constraints:

board has exactly 8 rows and 8 columns.
Each cell is ., B, or W.
0 <= rMove, cMove < 8
board[rMove][cMove] == "."
color is B or W.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

2D Arrays/Matrices - Understanding how to navigate and manipulate grid-based data structures
Direction Vectors - Using coordinate offsets to traverse in 8 directions (horizontal, vertical, diagonal)
Boundary Checking - Validating array indices to avoid out-of-bounds errors

1. Iteration - I

Intuition

This problem simulates an Othello/Reversi move validation. A move is legal if placing a piece creates a "good line" in any of the 8 directions (horizontal, vertical, or diagonal). A good line starts with the placed piece, has one or more opponent pieces in between, and ends with another piece of the same color. The total length must be at least 3.

Algorithm

Place the piece of the given color at the specified position on the board.
Define all 8 possible directions: up, down, left, right, and the 4 diagonals.
For each direction, check if a valid line can be formed:
- Start from the placed position and move one step in the chosen direction.
- Track the length of the line.
- Continue moving while within bounds and encountering non-empty cells.
- If we hit an empty cell, this direction is invalid.
- If we reach a cell with our color and the total length is at least 3, the line is valid.
If any direction produces a valid line, return true.
If no valid line exists in any direction, return false.

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1],
                     [1, 1], [-1, -1], [1, -1], [-1, 1]]

        board[rMove][cMove] = color

        def legal(row, col, color, direc):
            dr, dc = direc
            row, col = row + dr, col + dc
            length = 1

            while 0 <= row < ROWS and 0 <= col < COLS:
                length += 1
                if board[row][col] == ".":
                    return False
                if board[row][col] == color:
                    return length >= 3
                row, col = row + dr, col + dc
            return False

        for d in direction:
            if legal(rMove, cMove, color, d):
                return True
        return False

public class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        int ROWS = board.length, COLS = board[0].length;
        int[][] direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1},
                             {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

        board[rMove][cMove] = color;

        for (int[] d : direction) {
            if (legal(board, rMove, cMove, color, d)) {
                return true;
            }
        }
        return false;
    }

    private boolean legal(char[][] board, int row, int col, char color, int[] direc) {
        int ROWS = board.length, COLS = board[0].length;
        int dr = direc[0], dc = direc[1];
        row += dr;
        col += dc;
        int length = 1;

        while (row >= 0 && row < ROWS && col >= 0 && col < COLS) {
            length++;
            if (board[row][col] == '.') {
                return false;
            }
            if (board[row][col] == color) {
                return length >= 3;
            }
            row += dr;
            col += dc;
        }
        return false;
    }
}

class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int ROWS = board.size(), COLS = board[0].size();
        vector<vector<int>> direction = {{1, 0}, {-1, 0}, {0, 1}, {0, -1},
                                         {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};

        board[rMove][cMove] = color;

        for (auto& d : direction) {
            if (legal(board, rMove, cMove, color, d)) {
                return true;
            }
        }
        return false;
    }

private:
    bool legal(vector<vector<char>>& board, int row, int col, char color, vector<int>& direc) {
        int ROWS = board.size(), COLS = board[0].size();
        int dr = direc[0], dc = direc[1];
        row += dr;
        col += dc;
        int length = 1;

        while (row >= 0 && row < ROWS && col >= 0 && col < COLS) {
            length++;
            if (board[row][col] == '.') {
                return false;
            }
            if (board[row][col] == color) {
                return length >= 3;
            }
            row += dr;
            col += dc;
        }
        return false;
    }
};

class Solution {
    /**
     * @param {character[][]} board
     * @param {number} rMove
     * @param {number} cMove
     * @param {character} color
     * @return {boolean}
     */
    checkMove(board, rMove, cMove, color) {
        const ROWS = board.length,
            COLS = board[0].length;
        const direction = [
            [1, 0],
            [-1, 0],
            [0, 1],
            [0, -1],
            [1, 1],
            [-1, -1],
            [1, -1],
            [-1, 1],
        ];

        board[rMove][cMove] = color;

        const legal = (row, col, color, [dr, dc]) => {
            row += dr;
            col += dc;
            let length = 1;

            while (row >= 0 && row < ROWS && col >= 0 && col < COLS) {
                length++;
                if (board[row][col] === '.') {
                    return false;
                }
                if (board[row][col] === color) {
                    return length >= 3;
                }
                row += dr;
                col += dc;
            }
            return false;
        };

        for (let d of direction) {
            if (legal(rMove, cMove, color, d)) {
                return true;
            }
        }
        return false;
    }
}

public class Solution {
    public bool CheckMove(char[][] board, int rMove, int cMove, char color) {
        int ROWS = board.Length, COLS = board[0].Length;
        int[][] direction = new int[][] {
            new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1},
            new int[] {1, 1}, new int[] {-1, -1}, new int[] {1, -1}, new int[] {-1, 1}
        };

        board[rMove][cMove] = color;

        foreach (int[] d in direction) {
            if (Legal(board, rMove, cMove, color, d)) {
                return true;
            }
        }
        return false;
    }

    private bool Legal(char[][] board, int row, int col, char color, int[] direc) {
        int ROWS = board.Length, COLS = board[0].Length;
        int dr = direc[0], dc = direc[1];
        row += dr;
        col += dc;
        int length = 1;

        while (row >= 0 && row < ROWS && col >= 0 && col < COLS) {
            length++;
            if (board[row][col] == '.') {
                return false;
            }
            if (board[row][col] == color) {
                return length >= 3;
            }
            row += dr;
            col += dc;
        }
        return false;
    }
}

class Solution {
    fun checkMove(board: Array<CharArray>, rMove: Int, cMove: Int, color: Char): Boolean {
        val ROWS = board.size
        val COLS = board[0].size
        val direction = arrayOf(
            intArrayOf(1, 0), intArrayOf(-1, 0), intArrayOf(0, 1), intArrayOf(0, -1),
            intArrayOf(1, 1), intArrayOf(-1, -1), intArrayOf(1, -1), intArrayOf(-1, 1)
        )

        board[rMove][cMove] = color

        fun legal(row: Int, col: Int, color: Char, direc: IntArray): Boolean {
            var r = row + direc[0]
            var c = col + direc[1]
            var length = 1

            while (r >= 0 && r < ROWS && c >= 0 && c < COLS) {
                length++
                if (board[r][c] == '.') {
                    return false
                }
                if (board[r][c] == color) {
                    return length >= 3
                }
                r += direc[0]
                c += direc[1]
            }
            return false
        }

        for (d in direction) {
            if (legal(rMove, cMove, color, d)) {
                return true
            }
        }
        return false
    }
}

class Solution {
    func checkMove(_ board: inout [[Character]], _ rMove: Int, _ cMove: Int, _ color: Character) -> Bool {
        let ROWS = board.count, COLS = board[0].count
        let direction = [[1, 0], [-1, 0], [0, 1], [0, -1],
                         [1, 1], [-1, -1], [1, -1], [-1, 1]]

        board[rMove][cMove] = color

        func legal(_ row: Int, _ col: Int, _ color: Character, _ direc: [Int]) -> Bool {
            var row = row + direc[0]
            var col = col + direc[1]
            var length = 1

            while row >= 0 && row < ROWS && col >= 0 && col < COLS {
                length += 1
                if board[row][col] == "." {
                    return false
                }
                if board[row][col] == color {
                    return length >= 3
                }
                row += direc[0]
                col += direc[1]
            }
            return false
        }

        for d in direction {
            if legal(rMove, cMove, color, d) {
                return true
            }
        }
        return false
    }
}

impl Solution {
    pub fn check_move(board: &mut Vec<Vec<char>>, r_move: i32, c_move: i32, color: char) -> bool {
        let rows = board.len() as i32;
        let cols = board[0].len() as i32;
        let direction: Vec<[i32; 2]> = vec![
            [1, 0], [-1, 0], [0, 1], [0, -1],
            [1, 1], [-1, -1], [1, -1], [-1, 1],
        ];

        board[r_move as usize][c_move as usize] = color;

        for d in &direction {
            if Self::legal(board, r_move, c_move, color, d, rows, cols) {
                return true;
            }
        }
        false
    }

    fn legal(board: &Vec<Vec<char>>, mut row: i32, mut col: i32, color: char, direc: &[i32; 2], rows: i32, cols: i32) -> bool {
        let (dr, dc) = (direc[0], direc[1]);
        row += dr;
        col += dc;
        let mut length = 1;

        while row >= 0 && row < rows && col >= 0 && col < cols {
            length += 1;
            if board[row as usize][col as usize] == '.' {
                return false;
            }
            if board[row as usize][col as usize] == color {
                return length >= 3;
            }
            row += dr;
            col += dc;
        }
        false
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

2. Iteration - II

Intuition

This is a more compact implementation of the same logic. Instead of storing directions as pairs, we use a single array where consecutive elements form direction pairs. This reduces memory usage slightly and makes the iteration more streamlined.

Algorithm

Place the piece of the given color at the specified position.
Use a compact direction array where direction[d] and direction[d+1] represent the row and column deltas for each direction.
Loop through indices 0 to 8, treating each as a different direction.
For each direction:
- Start from the placed position.
- Move in the direction while tracking the line length.
- Stop if we go out of bounds or hit an empty cell.
- If we reach our own color and have traversed more than one cell (length > 1), return true.
If no valid line is found in any direction, return false.

class Solution:
    def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
        ROWS, COLS = len(board), len(board[0])
        direction = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1]

        board[rMove][cMove] = color

        for d in range(9):
            length = 1
            row, col = rMove, cMove
            while True:
                row += direction[d]
                col += direction[d + 1]

                if row < 0 or col < 0 or row >= ROWS or col >= COLS or board[row][col] == ".":
                    break
                if board[row][col] == color:
                    if length > 1:
                        return True
                    break
                length += 1

        return False

public class Solution {
    public boolean checkMove(char[][] board, int rMove, int cMove, char color) {
        int ROWS = board.length, COLS = board[0].length;
        int[] direction = {0, 1, 0, -1, 0, 1, 1, -1, -1, 1};

        board[rMove][cMove] = color;

        for (int d = 0; d < 9; d++) {
            int row = rMove, col = cMove;
            for (int length = 1; ; ++length) {
                row += direction[d];
                col += direction[d + 1];

                if (row < 0 || col < 0 || row >= ROWS || col >= COLS || board[row][col] == '.')
                    break;
                if (board[row][col] == color) {
                    if (length > 1)
                        return true;
                    break;
                }
            }
        }
        return false;
    }
}

class Solution {
public:
    bool checkMove(vector<vector<char>>& board, int rMove, int cMove, char color) {
        int ROWS = board.size(), COLS = board[0].size();
        int direction[10] = {0, 1, 0, -1, 0, 1, 1, -1, -1, 1};

        board[rMove][cMove] = color;

        for (int d = 0; d < 9; ++d) {
            int row = rMove, col = cMove;
            for (int length = 1; ; ++length) {
                row += direction[d];
                col += direction[d + 1];

                if (row < 0 || col < 0 || row >= ROWS || col >= COLS || board[row][col] == '.')
                    break;
                if (board[row][col] == color) {
                    if (length > 1)
                        return true;
                    break;
                }
            }
        }
        return false;
    }
};

class Solution {
    /**
     * @param {character[][]} board
     * @param {number} rMove
     * @param {number} cMove
     * @param {character} color
     * @return {boolean}
     */
    checkMove(board, rMove, cMove, color) {
        const ROWS = board.length,
            COLS = board[0].length;
        const direction = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1];

        board[rMove][cMove] = color;

        for (let d = 0; d < 9; d++) {
            let row = rMove,
                col = cMove;
            for (let length = 1; ; ++length) {
                row += direction[d];
                col += direction[d + 1];

                if (
                    row < 0 ||
                    col < 0 ||
                    row >= ROWS ||
                    col >= COLS ||
                    board[row][col] === '.'
                )
                    break;
                if (board[row][col] === color) {
                    if (length > 1) return true;
                    break;
                }
            }
        }
        return false;
    }
}

public class Solution {
    public bool CheckMove(char[][] board, int rMove, int cMove, char color) {
        int ROWS = board.Length, COLS = board[0].Length;
        int[] direction = {0, 1, 0, -1, 0, 1, 1, -1, -1, 1};

        board[rMove][cMove] = color;

        for (int d = 0; d < 9; d++) {
            int row = rMove, col = cMove;
            for (int length = 1; ; ++length) {
                row += direction[d];
                col += direction[d + 1];

                if (row < 0 || col < 0 || row >= ROWS || col >= COLS || board[row][col] == '.')
                    break;
                if (board[row][col] == color) {
                    if (length > 1)
                        return true;
                    break;
                }
            }
        }
        return false;
    }
}

class Solution {
    fun checkMove(board: Array<CharArray>, rMove: Int, cMove: Int, color: Char): Boolean {
        val ROWS = board.size
        val COLS = board[0].size
        val direction = intArrayOf(0, 1, 0, -1, 0, 1, 1, -1, -1, 1)

        board[rMove][cMove] = color

        for (d in 0 until 9) {
            var row = rMove
            var col = cMove
            var length = 1
            while (true) {
                row += direction[d]
                col += direction[d + 1]

                if (row < 0 || col < 0 || row >= ROWS || col >= COLS || board[row][col] == '.')
                    break
                if (board[row][col] == color) {
                    if (length > 1)
                        return true
                    break
                }
                length++
            }
        }
        return false
    }
}

class Solution {
    func checkMove(_ board: inout [[Character]], _ rMove: Int, _ cMove: Int, _ color: Character) -> Bool {
        let ROWS = board.count, COLS = board[0].count
        let direction = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1]

        board[rMove][cMove] = color

        for d in 0..<9 {
            var row = rMove, col = cMove
            var length = 1
            while true {
                row += direction[d]
                col += direction[d + 1]

                if row < 0 || col < 0 || row >= ROWS || col >= COLS || board[row][col] == "." {
                    break
                }
                if board[row][col] == color {
                    if length > 1 {
                        return true
                    }
                    break
                }
                length += 1
            }
        }
        return false
    }
}

impl Solution {
    pub fn check_move(board: &mut Vec<Vec<char>>, r_move: i32, c_move: i32, color: char) -> bool {
        let rows = board.len() as i32;
        let cols = board[0].len() as i32;
        let direction = [0, 1, 0, -1, 0, 1, 1, -1, -1, 1];

        board[r_move as usize][c_move as usize] = color;

        for d in 0..9 {
            let mut row = r_move;
            let mut col = c_move;
            let mut length = 1;
            loop {
                row += direction[d];
                col += direction[d + 1];

                if row < 0 || col < 0 || row >= rows || col >= cols
                    || board[row as usize][col as usize] == '.'
                {
                    break;
                }
                if board[row as usize][col as usize] == color {
                    if length > 1 {
                        return true;
                    }
                    break;
                }
                length += 1;
            }
        }
        false
    }
}

Time & Space Complexity

Time complexity: $O(1)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Place the Piece Before Checking

The move validation must include the piece being placed at (rMove, cMove). If you forget to set board[rMove][cMove] = color before checking directions, you may incorrectly validate lines that don't actually start with your piece.

# Must place the piece first:
board[rMove][cMove] = color

Not Requiring At Least One Opponent Piece Between

A valid line must have at least one opponent piece between your placed piece and another piece of your color. Checking only that the endpoint matches your color without verifying length >= 3 allows invalid moves where two of your pieces are adjacent.

# Wrong: just checking board[row][col] == color
# Correct:
if board[row][col] == color:
    return length >= 3  # Ensures at least one opponent piece in between

Missing a Direction or Checking Only 4 Directions

There are 8 possible directions (horizontal, vertical, and 4 diagonals). A common mistake is checking only 4 directions (e.g., only cardinal or only diagonal), which misses valid lines in the unchecked directions.