Connect Four Move Validator

Overview

The goal is to determine if a specific move in a Connect Four-style game results in a win for the current player. A win occurs if the newly placed piece completes a line of four consecutive pieces of the same type in any of the four standard directions: horizontal, vertical, and the two diagonals.

Since we are guaranteed that no winner existed before this move, we only need to check lines that pass through the specific coordinate [x, y] of the new move.

Brute Force

The simplest way to check for a win is to look at all possible lines of length 4 that could contain the current move. For each direction, there are exactly four possible "windows" of 4 cells that include our target cell. For example, in the horizontal direction, the move (x, y) could be the 1st, 2nd, 3rd, or 4th piece in a winning sequence.

We can iterate through all 16 possible segments (4 directions × 4 positions) and check if every cell in that segment belongs to the current player and stays within the board boundaries.

def checkWinCondition(board: list[list[str]], move: list[int], player: str) -> str:
    r, c = move
    rows, cols = len(board), len(board[0])
    
    # Directions: (dr, dc)
    directions = [
        (0, 1),  # Horizontal
        (1, 0),  # Vertical
        (1, 1),  # Diagonal (TL to BR)
        (1, -1)  # Anti-diagonal (TR to BL)
    ]
    
    for dr, dc in directions:
        # A move at (r, c) could be at index 'i' of a 4-length sequence
        # where i ranges from 0 to 3.
        for i in range(4):
            # Calculate the starting point of the 4-length sequence
            start_r = r - i * dr
            start_c = c - i * dc
            
            count = 0
            for k in range(4):
                curr_r = start_r + k * dr
                curr_c = start_c + k * dc
                
                # Boundary check
                if 0 <= curr_r < rows and 0 <= curr_c < cols:
                    # Check if cell matches player (considering the move itself is now 'player')
                    cell_val = player if (curr_r == r and curr_c == c) else board[curr_r][curr_c]
                    if cell_val == player:
                        count += 1
                    else:
                        break
                else:
                    break
            
            if count == 4:
                return player
                
    return ""

Time complexity: O(1) — While the board size is $N \times M$, we only check a fixed number of segments (16) of fixed length (4) around the move coordinate. Space complexity: O(1) — We use a constant amount of extra space for direction vectors and loop counters.

Optimal Approach

The optimal approach is a variation of the "sliding window" or "expansion" technique. Instead of checking all possible segments, we start at the move coordinate (r, c) and count how many identical pieces extend consecutively in both directions along an axis.

For example, for the horizontal axis, we count pieces to the left and pieces to the right. If 1 (the move) + count_left + count_right >= 4, the player wins. This is more efficient in practice because it stops searching an axis as soon as a mismatch or boundary is hit.

def checkWinCondition(board: list[list[str]], move: list[int], player: str) -> str:
    r, c = move
    rows, cols = len(board), len(board[0])
    
    # Define the 4 axes to check: (dr, dc)
    # We only need one direction per axis; we will check both positive and negative steps.
    axes = [
        (0, 1),  # Horizontal
        (1, 0),  # Vertical
        (1, 1),  # Diagonal
        (1, -1)  # Anti-diagonal
    ]
    
    for dr, dc in axes:
        consecutive = 1  # Start with the piece just placed
        
        # Check in the positive direction
        nr, nc = r + dr, c + dc
        while 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == player:
            consecutive += 1
            nr += dr
            nc += dc
            
        # Check in the negative direction
        nr, nc = r - dr, c - dc
        while 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == player:
            consecutive += 1
            nr -= dr
            nc -= dc
            
        if consecutive >= 4:
            return player
            
    return ""

Time complexity: O(K) — Where $K$ is the number of pieces required to win (in this case, 4). We visit at most 7 cells per axis (3 in each direction + the center). Space complexity: O(1) — No additional data structures are used.

Edge Cases

• Board Boundaries: The move might be at the edge or corner of the board. The 0 <= nr < rows checks handle this.
• Small Boards: If the board is smaller than $4 \times 4$ in a certain dimension, the logic still holds (it will simply hit the boundary before reaching a count of 4).
• Move at Start/End of Line: The bidirectional expansion correctly handles cases where the new move is the first, last, or middle piece of a winning line.

Fast