1958. Check if Move is Legal

MediumArrayEnumerationMatrix

Problem Description

In the given problem, you have an 8x8 game board represented by a two-dimensional array board, where each cell can be in one of three states: it can either be free (marked with '.'), hold a white piece ('W'), or hold a black piece ('B'). Your task is to determine if a move, defined as changing a free cell to a particular color (either white or black), is legal.

A move is legal if it turns the selected cell into the endpoint of a "good line". A good line must follow these conditions:

It consists of at least three cells, including endpoints.
The endpoints of the line must be of one color.
The cells between the endpoints must all be of the opposite color and there should be no free cells.

There must be a good line in any of the eight possible directions from the selected cell: horizontal, vertical, or diagonal. The task boils down to checking whether making the move creates at least one good line according to the above conditions.

Intuition

Given the rules for a legal move, the logical approach is to start from the cell at (rMove, cMove) and look in all possible line directions (8 in total) to check if there is a good line with the move being an endpoint.

The solution has the following key steps:

Define the eight possible directions to explore from any given cell (up, down, left, right, and the four diagonals).
For each direction, keep moving along that line until you either run off the board or encounter a cell that isn't occupied by the opposite color (could be free or the same color as the one you're playing).
Count the number of cells of the opposite color you pass in this process.
If you find a cell at the end of the sequence that is of the same color as the one you're playing, and there are more than one opposite color cells in between, the move is legal (i.e., a good line is formed).

The provided code creates a list of directions and iterates over them. For each direction, it increments along that path counting the cells until a stopping condition is met. If the final cell checked matches the player's color and there was more than one opposite color cell in between, the function returns true, indicating that the move is legal.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Given an array of 1,000,000 integers that is almost sorted, except for 2 pairs of integers. Which algorithm is fastest for sorting the array?

Heap sortMerge sortInsertion sortQuick sort

I don’t know

Solution Approach

The implementation of the solution involves systematic exploration in every possible direction from the cell where the move is intended. Here is a breakdown of how the algorithm translates into the solution strategy:

Direction Vectors: The solution uses a list of tuples called dirs, where each tuple represents a direction vector in the two-dimensional space of the board. For example, (1, 0) represents moving down, (0, 1) represents moving right, (-1, 0) and (0, -1) represent moving up and left respectively, and the four diagonal directions are represented with combinations of 1 and -1.
Iterating Over Directions: The solution iterates over these direction vectors using a for loop. Inside the loop, it sets up two index variables i and j to the rMove and cMove coordinates of the move being queried.
Exploring a Direction: For each of the 8 directions, the code enters a while loop which continues as long as the new indices i + a and j + b (representing the next cell in the direction (a, b)) stay within the bounds of the grid (0 to n-1, as the grid size is 8).
Counting Opposite Colors: It increments a counter t representing the number of cells traversed. The loop breaks if the next cell is either free or of the same color as the move being played (color), since this means a good line cannot be assured in this direction.
Check for Legal Move: After the loop, if the cell that caused the loop to terminate is of the same color as color, and if at least one opposite-colored piece (t > 1) was found in the traversed path, then the move is legal. A true value is immediately returned.
Result: If none of the directions leads to a legal move, meaning no good line was formed, the function returns false after exiting the for loop.

The solution effectively uses a pattern common in grid-based problems, iterating over a set of fixed directions to explore adjacent cells. By using the direction vectors with a while loop and boundary checks, it manages to traverse the two-dimensional array efficiently.

The data structures used here are basic; a list for directions and simple variables for indices and counters. The algorithm does not require additional data structures like stacks, queues, or maps.

This iterative approach examines each potential line emanating from the cell (rMove, cMove), handling the board as if it were an infinite plane, clipping off paths that go off-grid or do not meet the conditions for a legal move.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversalPost-order traversalIn-order traversalLevel-order traversal

I don’t know

Example Walkthrough

Let's illustrate the solution approach with a small example. Consider the following 8x8 board configuration where 'rMove' is at row 3, and 'cMove' is at column 3 (0-indexed), and we wish to place a black piece ('B'):

1. . . . . . . .
2. . . . . . . .
3. . W B W . . .
4. . W . W . . .
5. . W B W . . .
6. . . . . . . .
7. . . . . . . .
8. . . . . . . .

We want to determine if placing a black piece at (3,3) is a legal move.

Following the solution approach:

Direction Vectors: We have a list of eight possible directions to check - up, down, left, right, and the four diagonals.
Iterating Over Directions: We start iterating over these directions. Let's consider checking upwards first (direction vector (-1, 0)).
Exploring a Direction: We move up from our desired move position (3,3) to (2,3) and keep going up as long as we're within the bounds and encountering white pieces ('W').
Counting Opposite Colors: We find that we indeed encounter white pieces and keep a counter t. Since we find white pieces at positions (2,3) and (1,3), t is now 2.
Check for Legal Move: As we move to the next cell upwards (0,3), we find a black piece ('B'). Since t > 1 and the piece found is of the same color as the piece we wish to play, this direction confirms a legal move.
Result: We return true before checking the remaining directions because we've found at least one good line (vertical line from (0,3) through (3,3)), and thus the move at (3,3) is legal.

In this example, only one direction was needed to confirm the legality of the move, but in a complete implementation, all eight directions would be checked to evaluate the move fully. This demonstrates how the algorithm systematically checks each direction to determine whether a legal "good line" is formed.

Solution Implementation

1class Solution:
2    def checkMove(
3        self, board: List[List[str]], r_move: int, c_move: int, color: str
4    ) -> bool:
5        # Define all 8 possible directions to move in a 2D grid
6        directions = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]
7      
8        # The size of the Othello board is 8x8
9        board_size = 8
10
11        # Check each direction from the move point
12        for delta_row, delta_col in directions:
13            # Initialize the current position to the initial move point
14            row, col = r_move, c_move
15            # Track the number of opponent's pieces between our pieces
16            in_between_count = 0
17          
18            # Move in the current direction until we're still on the board
19            while 0 <= row + delta_row < board_size and 0 <= col + delta_col < board_size:
20                # Move to the next cell in the direction
21                row, col = row + delta_row, col + delta_col
22              
23                # If we find a piece of the same color or an empty space, stop looking in this direction
24                if board[row][col] in ['.', color]:
25                    break
26              
27                # Otherwise, we've found an opponent's piece
28                in_between_count += 1
29
30            # If the last piece we found was of the same color and there was at least one piece in between,
31            # then the move is legal
32            if board[row][col] == color and in_between_count > 1: 
33                return True
34
35        # If no direction is valid, then the move is not legal
36        return False
37

1class Solution {
2    private static final int[][] DIRECTIONS = { // Directions to check for flips
3        {1, 0},   // South
4        {0, 1},   // East
5        {-1, 0},  // North
6        {0, -1},  // West
7        {1, 1},   // Southeast
8        {1, -1},  // Southwest
9        {-1, 1},  // Northeast
10        {-1, -1}  // Northwest
11    };
12    private static final int BOARD_SIZE = 8; // Standard Othello board size
13
14    public boolean checkMove(char[][] board, int rowMove, int columnMove, char color) {
15        // Loop through all possible directions
16        for (int[] direction : DIRECTIONS) {
17            int currentRow = rowMove;
18            int currentColumn = columnMove;
19            int moveLength = 0; // Length of the potential line of opponent's pieces between our pieces
20            int rowDelta = direction[0], columnDelta = direction[1];
21
22            // Keep moving in the direction while the next position is inside the board
23            while (0 <= currentRow + rowDelta && currentRow + rowDelta < BOARD_SIZE
24                    && 0 <= currentColumn + columnDelta && currentColumn + columnDelta < BOARD_SIZE) {
25                moveLength++; // Increase the length of the line
26                currentRow += rowDelta;
27                currentColumn += columnDelta;
28
29                // If the next position is either empty or contains a piece of the same color, break out of the loop
30                if (board[currentRow][currentColumn] == '.' || board[currentRow][currentColumn] == color) {
31                    break;
32                }
33            }
34
35            // Check if the last piece in the direction is the same color and the length of opponent's pieces is more than 1
36            if (board[currentRow][currentColumn] == color && moveLength > 1) {
37                return true; // The move is valid as it brackets at least one line of opponent pieces
38            }
39        }
40        return false; // If no direction is valid, the move is invalid
41    }
42}
43

1#include <vector>
2using std::vector;
3
4class Solution {
5public:
6    // Directions of 8 possible moves from any position (vertical, horizontal, diagonal)
7    vector<vector<int>> directions = {
8        {1, 0},  // Down
9        {0, 1},  // Right
10        {-1, 0}, // Up 
11        {0, -1}, // Left
12        {1, 1},  // Down-right diagonal
13        {1, -1}, // Down-left diagonal
14        {-1, 1}, // Up-right diagonal
15        {-1, -1} // Up-left diagonal
16    };
17    int boardSize = 8; // Board is 8x8
18
19    // Check if a move is valid by the game rules
20    bool checkMove(vector<vector<char>>& board, int rowMove, int colMove, char color) {
21        // Iterate over all possible directions
22        for (auto& direction : directions) {
23            int deltaX = direction[0], deltaY = direction[1];
24            int currRow = rowMove, currCol = colMove;
25            int tilesToFlip = 0; // Counter for the number of opponent's tiles in the line
26
27            // Move in the direction while staying within the bounds of the board
28            while (0 <= currRow + deltaX && currRow + deltaX < boardSize &&
29                   0 <= currCol + deltaY && currCol + deltaY < boardSize) {
30                // Move to the next tile
31                currRow += deltaX;
32                currCol += deltaY;
33
34                // If the tile is empty or has the same color, move is not valid in this direction
35                if (board[currRow][currCol] == '.' || board[currRow][currCol] == color) break;
36
37                // Increase the count of tiles to flip
38                tilesToFlip++;
39            }
40
41            // Check if after moving in this direction, we end on our own color and there was at least one tile to flip
42            if (board[currRow][currCol] == color && tilesToFlip > 1) {
43                return true; // Move is valid in this direction
44            }
45        }
46        return false; // Move is not valid in any direction
47    }
48};
49

1// Possible directions of moves from any position (vertical, horizontal, diagonal)
2const directions: number[][] = [
3  [1, 0],   // Down
4  [0, 1],   // Right
5  [-1, 0],  // Up
6  [0, -1],  // Left
7  [1, 1],   // Down-right diagonal
8  [1, -1],  // Down-left diagonal
9  [-1, 1],  // Up-right diagonal
10  [-1, -1]  // Up-left diagonal
11];
12
13const boardSize: number = 8; // The board is an 8x8 grid
14
15/**
16 * Check if a move is valid by the game rules.
17 *
18 * @param {string[][]} board - The game board represented as a two-dimensional array.
19 * @param {number} rowMove - The row index of the move to check.
20 * @param {number} colMove - The column index of the move to check.
21 * @param {string} color - The color of the current player ('B' or 'W').
22 * @returns {boolean} True if the move is valid, otherwise false.
23 */
24function checkMove(board: string[][], rowMove: number, colMove: number, color: string): boolean {
25  // Iterate over all possible directions to find if the move is valid
26  for (let direction of directions) {
27    let deltaX = direction[0], deltaY = direction[1];
28    let currRow = rowMove, currCol = colMove;
29    let tilesToFlip = 0; // Counter for the number of opponent's tiles in line
30  
31    // Continue moving in the direction while within the bounds of the board
32    while (0 <= currRow + deltaX && currRow + deltaX < boardSize &&
33           0 <= currCol + deltaY && currCol + deltaY < boardSize) {
34      // Proceed to the next tile in the direction
35      currRow += deltaX;
36      currCol += deltaY;
37    
38      // If the tile is empty or has the same color, the move is not valid in this direction
39      if (board[currRow][currCol] === '.' || board[currRow][currCol] === color) break;
40    
41      // Otherwise, increase the count of tiles to flip
42      tilesToFlip++;
43    }
44  
45    // After the loop, if we end on our own color and there was at least one tile to flip, the move is valid
46    if (board[currRow] && board[currRow][currCol] === color && tilesToFlip > 0) {
47      return true;
48    }
49  }
50
51  // If the move wasn't found to be valid in any direction, return false
52  return false;
53}
54

Not Sure What to Study? Take the 2-min Quiz：

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1dp[i] = dp[i] + dp[i - 1]dp[i] = (dp[i] + dp[j] + 1) for j in 0 to idp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the code is determined by how many times we loop over the different directions from the starting move, as well as how far we can go in each direction. We have 8 possible directions to check, and in the worst-case scenario, we could iterate over all n cells in one direction (where n is the size of the board's dimension, which is 8 in this case). Therefore, the worst-case time complexity is O(8n) which simplifies to O(n) because 8 is a constant factor.

In this specific case, since n is fixed at 8, we can also argue that the time complexity is O(1) since the board size doesn't change and there's a maximum number of steps to be taken.

Space Complexity

The space complexity of the code is O(1) since the extra space used does not scale with the size of the input. We have a fixed-size board and the dirs array which consists of 8 directions, and a few variables i, j, and t, which all occupy constant space regardless of input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1958. Check if Move is Legal

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings