How do you solve Check if Move is Legal on LeetCode?

Check if Move is Legal (LeetCode #1958) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Understanding the definition of a good line is crucial for solving the problem.

What is the brute force solution for Check if Move is Legal?

The brute force approach for Check if Move is Legal is Brute Force, with O(n²) time complexity and O(1) space complexity. We will check each of the four possible directions (horizontal, vertical, and two diagonals) from the cell where the move is made. For each direction, we will count the number of consecutive cells of the same color and the opposite color to see if we can form a good line. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check if Move is Legal?

Check if Move is Legal uses the following concepts: Array, Matrix, Enumeration. The recommended patterns to study are: Array, Enumeration.

What are the interview tips for Check if Move is Legal?

Clarify the problem statement and constraints before jumping into coding. Think aloud while coding to demonstrate your thought process. Test your solution with edge cases to ensure robustness.

What are common mistakes when solving Check if Move is Legal?

Not accounting for edge cases where the line might go out of bounds. Failing to correctly identify the opposite color.

#1958

Check if Move is Legal

Medium

ArrayMatrixEnumerationArrayEnumeration

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Instead of checking all directions separately, we can streamline the process by iterating through each direction in a single loop and counting the cells more efficiently. This reduces redundant checks and improves performance.

⚙️

Algorithm

4 steps

1Step 1: Define the four possible directions to check for good lines.
2Step 2: For each direction, count the same color cells and opposite color cells in both positive and negative directions.
3Step 3: If any direction yields a count of 3 or more for a good line, return true.
4Step 4: If no good line is found after checking all directions, return false.

solution.py25 lines

1def checkMove(board, rMove, cMove, color):
2    directions = [(1, 0), (0, 1), (1, 1), (1, -1)]
3    for dr, dc in directions:
4        count = 1
5        count += countLine(board, rMove, cMove, dr, dc, color)
6        count += countLine(board, rMove, cMove, -dr, -dc, color)
7        if count >= 3:
8            return True
9    return False
10
11
12def countLine(board, r, c, dr, dc, color):
13    count = 0
14    opposite = 'B' if color == 'W' else 'W'
15    while 0 <= r < 8 and 0 <= c < 8:
16        if board[r][c] == opposite:
17            count += 1
18        elif board[r][c] == color:
19            return count
20        else:
21            break
22        r += dr
23        c += dc
24    return count
25

ℹ

Complexity note: The complexity is O(n) because we are only iterating through the cells in a single pass for each direction, making it more efficient than the brute force method.

1Understanding the definition of a good line is crucial for solving the problem.
2Recognizing that checking in multiple directions can be optimized is key.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.