Check if Move is Legal: Directional Grid Search

LeetCode 1958: Check if Move is Legal gives you an 8x8 Othello (Reversi) board where each cell is 'B' (black), 'W' (white), or '.' (empty). You are given a move (rMove, cMove, color) and need to determine whether placing that color at that position is legal. A move is legal if it creates at least one "good line" in any of the 8 directions (horizontal, vertical, or diagonal). A good line starts at the placed cell, passes through one or more cells of the opposite color, and ends at a cell of the same color.

Why this problem matters

This problem tests your ability to systematically search in multiple directions from a single cell. The 8-direction traversal pattern shows up constantly in grid problems: Game of Life, word search, minesweeper, flood fill. The twist here is that you are not just counting neighbors. You are walking along a line and validating a sequence of colors. That combination of directional movement with conditional logic is exactly the kind of detail that trips people up in interviews.

The brute force approach

You could check each direction by writing eight separate loops, one for right, one for down-right, one for down, and so on. Each loop would walk outward from the placed cell, counting opposite-color cells and looking for a same-color terminator. This works, but it produces a lot of duplicated code. The core logic (walk, count opposites, check for same color) is identical in every direction. The only thing that changes is the direction vector.

The key insight: encode all 8 directions as (dr, dc) pairs

Instead of writing eight loops, define each direction as a pair (dr, dc) where dr is the row delta and dc is the column delta. The eight directions are all combinations of -1, 0, and 1, excluding (0, 0). Then write a single loop that walks in any direction using r += dr, c += dc. This collapses eight cases into one.

For each direction, you walk outward counting cells of the opposite color. If you hit an empty cell or go out of bounds, this direction fails. If you hit a cell of the same color after counting at least one opposite cell, you have found a good line.

Walking through it step by step

Suppose the board has a row like [B, W, W, B] and you just placed the B at the left end. Let's trace the direction check going right, with (dr, dc) = (0, 1).

The solution

def check_move(board, r_move, c_move, color):
    directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    for dr, dc in directions:
        r, c = r_move + dr, c_move + dc
        count = 0
        while 0 <= r < 8 and 0 <= c < 8:
            if board[r][c] == '.':
                break
            if board[r][c] == color:
                if count >= 1:
                    return True
                break
            count += 1
            r += dr
            c += dc
    return False

The function iterates over all 8 direction vectors. For each direction, it starts one step away from the placed cell and walks outward. At each step, three things can happen:

1. Empty cell or out of bounds: this direction cannot form a good line. Break and try the next direction.
2. Same color as placed piece: if we have already passed at least one opposite-color cell (count >= 1), this is a good line. Return True. Otherwise, the line has no opposite cells in between, so break.
3. Opposite color: increment count and keep walking.

If no direction produces a good line, return False.

Complexity analysis

Time: The board is always 8x8. For each of the 8 directions, you walk at most 7 steps (the longest diagonal or straight line on the board). That is at most 56 steps total. Since the board size is fixed, this is O(1).

Space: You only use a few variables for the direction, position, and count. No extra data structures. O(1).

Building blocks

1. 8-direction grid traversal

The pattern of defining directions as (dr, dc) pairs and looping over them is one of the most reusable building blocks in grid problems. It replaces eight separate branches with a single parameterized loop:

directions = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < rows and 0 <= nc < cols:
        pass

You will see this exact structure in Game of Life, Number of Islands (if using 8-connected), word search, and minesweeper. The only variation is whether you use 4 directions (up, down, left, right) or all 8.

2. Line validation pattern

Walking along a direction and validating a sequence is a distinct pattern from simply checking neighbors. In neighbor problems, you look one step away. In line validation, you walk until you hit a termination condition. This same idea appears in problems like N-Queens (checking diagonals for conflicts) and Connect Four (checking for four in a row).

The key structure is a while loop with bounds checking, combined with break conditions that distinguish between "this direction failed" and "this direction succeeded."

Edge cases

• No opposite cells in any direction: every adjacent cell in every direction is either empty, out of bounds, or the same color. No direction can form a good line. Return False.
• Opposite cells but no same-color terminator: you walk through opposite-color cells but hit the board edge or an empty cell before finding a same-color cell. That direction fails.
• Line of length 1: exactly one opposite-color cell followed by a same-color cell. This is the minimum good line. count = 1, which satisfies count >= 1.
• Placed cell is on the edge or corner: fewer directions have room to form a line. The bounds check 0 <= r < 8 and 0 <= c < 8 handles this naturally. Directions that immediately go out of bounds simply produce zero steps.

Common mistakes

1. Forgetting to start one step away. The walk should begin at (r_move + dr, c_move + dc), not at (r_move, c_move). If you start at the placed cell itself, you will immediately match your own color and incorrectly report a good line with zero opposite cells.

2. Not requiring at least one opposite cell. A good line needs one or more opposite-color cells between the placed piece and the terminating same-color piece. If you skip the count >= 1 check, you will accept lines where two same-color pieces are adjacent with nothing in between.

3. Treating empty cells as opposite color. An empty cell ('.') breaks the line. It is not the opposite color. If you only check for == color vs. everything else, empty cells will be counted as opposites and the walk will continue past gaps.

4. Confusing direction vectors. Mixing up the sign of dr or dc can send you in the wrong direction. Double-check that (-1, 0) is up and (1, 0) is down if rows increase downward.

From understanding to recall

You understand the 8-direction walk now, but the details are easy to fumble during an interview. Do you start counting at the placed cell or one step away? Do you break on empty cells or treat them as opposite? Is the condition count >= 1 or count > 0? (They are the same, but you need to remember to check at all.)

Spaced repetition locks these details in. Write the direction list, the walk loop, and the three-way branch (empty, same, opposite) from scratch. Do it today, again tomorrow, again in four days. After a few reps, the structure becomes automatic. You see "check directions on a grid" and the (dr, dc) loop with bounds checking writes itself.

The 8-direction traversal and line validation patterns are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Valid Sudoku - Another grid validation problem where you check structured constraints across rows, columns, and sub-regions
• Game of Life - Uses the same 8-direction neighbor pattern to count live cells around each position

CodeBricks breaks Check if Move is Legal into its 8-direction traversal and line validation building blocks, then drills them independently with spaced repetition. You type the direction vectors, the walk loop, and the count check from scratch until the pattern is automatic. When a directional grid search shows up in your interview, you do not think about it. You just write it.