Check if Move is Legal
MedPrompt
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'.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process of checking for a "good line" in all 8 possible directions (horizontal, vertical, and diagonals) from the given move coordinates. For each direction, it traverses the board cell by cell, keeping track of the line's length and the colors encountered.
Algorithm
- Define an array of 8 direction vectors
(dr, dc)representing horizontal, vertical, and diagonal moves. - Iterate through each of the 8 direction vectors.
- For each direction, create a helper function or an inner loop to check for a "good line".
- Inside the check for a single direction:
- Start a traversal from the cell adjacent to
(rMove, cMove). - Use a
lengthcounter, initialized to 1 (for the starting move cell). - In a loop, move one step at a time in the current direction:
- Increment the
length. - Check the cell's color:
- If it's an empty cell ('.') or out of bounds, this direction is invalid. Stop and try the next direction.
- If it's the same color as the move (
color), check iflength >= 3. If so, a good line is found, returntrue. Otherwise, this direction is invalid (e.g.,BB). - If it's the opposite color, it's part of the middle section. Continue traversing.
- Increment the
- Start a traversal from the cell adjacent to
- If the loop completes (reaches the board edge) without finding a same-colored endpoint, this direction is invalid.
- If all 8 directions are checked and no good line is found, return
false.
Walkthrough
The core idea is to check every one of the 8 directions radiating from (rMove, cMove). We can represent these 8 directions using an array of (dr, dc) pairs, like {{0, 1}, {0, -1}, {1, 0}, ...}. For each direction, we start a loop that begins at the cell adjacent to the move location. A counter length is used, initialized to 1 to account for the piece at (rMove, cMove). Inside the loop, we advance one step at a time. With each step, we increment length and check the color of the current cell. If the cell is empty ('.') or we go out of bounds, the line is broken. If the cell has the same color as our move, it's a potential endpoint. A "good line" must have at least 3 cells, so if our current length is 3 or more, we've found a valid line and can return true. If the cell has the opposite color, it's part of the middle section of a potential good line, so we continue traversing. If we check all 8 directions and none are valid, the move is not legal.
class Solution { public boolean checkMove(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 (isGoodLineInDirection(board, rMove, cMove, color, dir)) { return true; } } return false; } private boolean isGoodLineInDirection(char[][] board, int rStart, int cStart, char color, int[] dir) { int dr = dir[0]; int dc = dir[1]; int r = rStart + dr; int c = cStart + dc; int length = 1; while (r >= 0 && r < 8 && c >= 0 && c < 8) { length++; char currentCell = board[r][c]; if (currentCell == '.') { return false; // Line broken by empty cell } if (currentCell == color) { // Found an endpoint of the same color. // Check if the line has at least one piece in the middle. return length >= 3; } // If we are here, it's the opposite color, so continue. r += dr; c += dc; } return false; // Reached board edge without finding a valid endpoint. }}Complexity
Time
O(1). The board size is fixed at 8x8. We iterate through 8 directions, and for each direction, we traverse at most 7 cells. The total number of operations is constant.
Space
O(1). We only use a constant amount of extra space for the directions array and a few variables.
Trade-offs
Pros
Efficient and directly solves the problem.
Implementation is relatively compact.
Cons
The logic within the single loop, which handles multiple conditions (empty cell, same color, opposite color), can be slightly less intuitive to follow compared to a more structured approach.
This approach improves upon the direct simulation by adding more structure to the check for each direction. It breaks the process into two clear phases: first, ensuring the line starts correctly (with an adjacent piece of the opposite color), and second, scanning for the endpoint. This enhances code readability and maintainability.
Algorithm
- Define an array of 8 direction vectors
(dr, dc). - Determine the
oppositeColorbased on the inputcolor. - Iterate through each direction vector.
- Phase 1: Validate the Start of the Line.
- Check the immediate neighbor of
(rMove, cMove)in the current direction. - If this cell is out of bounds or is not the
oppositeColor, this direction is invalid. Continue to the next direction.
- Check the immediate neighbor of
- Phase 2: Scan for the Endpoint.
- If Phase 1 passed, we have a potential line. Start a loop from the cell after the immediate neighbor.
- Traverse in the same direction:
- If the cell is out of bounds or empty ('.'), the line is broken. Stop and check the next direction.
- If the cell is the
oppositeColor, continue traversing. - If the cell is the same
coloras the move, a valid endpoint is found. The line is guaranteed to have a length of at least 3. Returntrue.
- If all 8 directions are exhausted without finding a valid line, return
false.
Walkthrough
Similar to the previous approach, we iterate through all 8 directions from (rMove, cMove). However, the logic for checking each direction is split into two distinct steps for clarity.
Phase 1: Validate the Start of the Line.
For a given direction, we first check the immediate neighbor of (rMove, cMove). A valid "good line" must start with (move_color, opposite_color, ...). Therefore, this immediate neighbor must exist (be within board bounds) and must be of the opposite color. If this condition is not met, we can immediately discard this direction.
Phase 2: Scan for the Endpoint.
If the first neighbor is valid, we know we have a potential line of length 2. We now need to find an endpoint of our color to complete the line. We continue traversing in the same direction, cell by cell. If we encounter an empty cell ('.') or go off the board, the line is invalid. If we encounter a cell of our color, we have successfully found a "good line". Since we already passed Phase 1, the length is guaranteed to be at least 3, so we can return true.
class Solution { public boolean checkMove(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}}; char oppositeColor = (color == 'W') ? 'B' : 'W'; for (int[] dir : directions) { int dr = dir[0]; int dc = dir[1]; // Start from the cell adjacent to the move int r = rMove + dr; int c = cMove + dc; // Phase 1: Check if the line starts with an opposite-colored piece if (r >= 0 && r < 8 && c >= 0 && c < 8 && board[r][c] == oppositeColor) { // Phase 2: Scan for an endpoint of the same color while (true) { r += dr; c += dc; if (r < 0 || r >= 8 || c < 0 || c >= 8 || board[r][c] == '.') { // Reached edge or empty cell, this direction is not a good line break; } if (board[r][c] == color) { // Found a valid endpoint, making it a good line return true; } // If it's the opposite color, continue the loop } } } return false; }}Complexity
Time
O(1). The logic is fundamentally the same as the first approach. For a fixed 8x8 board, the number of operations is constant.
Space
O(1). Constant extra space is used for the directions array and a few variables.
Trade-offs
Pros
Highly readable and easy to understand due to the clear separation of logic.
Just as efficient as the single-loop approach, with O(1) complexity.
Cons
The code might be slightly more verbose than the single-loop implementation.
Solutions
Solution
class Solution {private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};private static final int N = 8;public boolean checkMove(char[][] board, int rMove, int cMove, char color) { for (int[] d : DIRS) { int i = rMove, j = cMove; int t = 0; int a = d[0], b = d[1]; while (0 <= i + a && i + a < N && 0 <= j + b && j + b < N) { ++t; i += a; j += b; if (board[i][j] == '.' || board[i][j] == color) { break; } } if (board[i][j] == color && t > 1) { return true; } } return false; }}class Solution {public: vector<vector<int>> dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}}; int n = 8; bool checkMove(vector<vector<char>> &board, int rMove, int cMove, char color) { for (auto &d : dirs) { int a = d[0], b = d[1]; int i = rMove, j = cMove; int t = 0; while (0 <= i + a && i + a < n && 0 <= j + b && j + b < n) { ++t; i += a; j += b; if (board[i][j] == '.' || board[i][j] == color) break; } if (board[i][j] == color && t > 1) return true; } return false; }};class Solution: def checkMove(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool: dirs = [(1, 0), (0, 1), (- 1, 0), (0, - 1), (1, 1), (1, - 1), (- 1, 1), (- 1, - 1)] n = 8 for a, b in dirs: i, j = rMove, cMove t = 0 while 0 <= i + a < n and 0 <= j + b < n: t += 1 i, j = i + a, j + b if board[i][j] in ['.', color]: break if board[i][j] == color and t > 1: return True return FalseVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.