Check if Move is Legal

Check if Move is Legal

What is this problem about?

The "Check if Move is Legal interview question" is a simulation of a move in an 8x8 board game like Othello or Reversi. You are given a grid, a starting position $(r, c)$, and a color (Black or White). A move is "legal" if it completes a "good line." A good line is a sequence of at least 3 cells starting at $(r, c)$ that begins and ends with the player's color, with the opposite color in between.

Why is this asked in interviews?

Amazon ask the "Check if Move is Legal coding problem" to test a candidate's ability to handle multi-directional traversals and boundary conditions. It evaluations your proficiency with "Matrix interview pattern" logic and your ability to implement a well-defined set of rules accurately.

Algorithmic pattern used

This problem follows the Directional Enumeration and Simulation pattern.

1. Directions: Define an array of 8 directions: [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)].
2. Exploration: For each direction, move one step away from $(r, c)$.
3. Validation:
   • The first step must be the opposite color.
   • Subsequent steps must remain the opposite color until you hit a cell of the same color.
   • If you hit an empty cell or the boundary before finding your own color, that direction is invalid.
4. Conclusion: If at least one of the 8 directions forms a "good line," the move is legal.

Example explanation

Move White to (3, 3).

• Direction North: (2,3) is Black, (1,3) is White.
• Sequence: White (new), Black, White. Length = 3. Result: True.

Common mistakes candidates make

• Length Constraint: Forgetting that a "good line" must have at least 3 elements (Start, Middle, End).
• Stopping early: Returning false after one failed direction instead of checking all 8.
• Boundary checks: Crashing the program when moving off the 8x8 grid.

Interview preparation tip

When a problem involves directions (up, down, diagonals), always use a 2D array of offsets (e.g., dirs = [[0,1], [0,-1]...]). This makes your code much cleaner and less error-prone than writing 8 separate if blocks.