LeetCode 1275 - Find Winner on a Tic Tac Toe Game

This problem asks us to simulate a game of Tic-Tac-Toe on a 3 x 3 grid given a sequence of moves. Each move specifies th

leetcodeeasyarrayhash-tablematrixsimulation

LeetCode Problem 1275

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Matrix, Simulation

Solution

Problem Understanding

This problem asks us to simulate a game of Tic-Tac-Toe on a 3 x 3 grid given a sequence of moves. Each move specifies the row and column where the current player places their mark. Player A always plays first and uses 'X', while player B uses 'O'. The goal is to determine the outcome of the game after all moves in the sequence: whether A wins, B wins, the game is a draw, or it is still pending.

The input is a list of moves where each element [row, col] represents the square on the grid chosen by the current player. The constraints guarantee that all moves are valid (no duplicate squares, all indices within [0, 2]) and that the first player is always A. The maximum number of moves is 9 because the grid has 9 squares.

Important edge cases include situations where the game ends before all squares are filled, such as if a player wins early, and scenarios where the last move fills the grid, resulting in a draw. The problem guarantees no invalid moves, so we do not need to check for out-of-bounds indices or already filled squares.

Approaches

The brute-force approach is to simulate the game on a 3 x 3 matrix. After each move, we update the grid and check all possible winning conditions: three rows, three columns, and two diagonals. This approach works because it directly models the game, but checking all rows, columns, and diagonals after each move is repetitive. For a 3 x 3 grid this is still acceptable, but it is not scalable if the grid size were larger.

The optimal approach leverages counters instead of maintaining the full grid. We track the number of marks each player has in each row, column, and both diagonals. Whenever a move is made, we increment the corresponding counters for that player. If any counter reaches 3, the player wins immediately. This avoids scanning the entire grid repeatedly and keeps the code clean and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * 8) = O(n) O(1) Simulate grid and check 8 winning conditions after each move
Optimal O(n) O(1) Use row, column, and diagonal counters for each player, update per move

Algorithm Walkthrough

  1. Initialize counters for both players: rows[3], cols[3], diag, and anti_diag. These represent how many marks each player has in each row, column, and diagonal.
  2. Iterate over the moves. For each move, determine which player is playing. Player A is even-indexed moves, B is odd-indexed moves.
  3. Increment the counters corresponding to the move's row, column, and diagonals if applicable.
  4. After incrementing, check if any counter reaches 3. If so, that player wins and we return "A" or "B".
  5. If no winner is found after all moves, check if all 9 moves have been played. If so, return "Draw".
  6. If there are still empty squares, return "Pending".

Why it works: By maintaining row, column, and diagonal counters, we capture all possible winning configurations without scanning the entire grid repeatedly. The counters precisely track the potential winning condition for each player, ensuring correct detection of a win.

Python Solution

from typing import List

class Solution:
    def tictactoe(self, moves: List[List[int]]) -> str:
        rows = [0] * 3
        cols = [0] * 3
        diag = 0
        anti_diag = 0

        for i, (r, c) in enumerate(moves):
            player = 1 if i % 2 == 0 else -1
            rows[r] += player
            cols[c] += player
            if r == c:
                diag += player
            if r + c == 2:
                anti_diag += player
            if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
                return "A" if player == 1 else "B"

        if len(moves) == 9:
            return "Draw"
        return "Pending"

This Python code uses integer counters where +1 represents player A and -1 represents player B. After each move, it updates row, column, and diagonal counters and immediately checks for a win. The code handles both early wins and full draws efficiently without storing the grid.

Go Solution

func tictactoe(moves [][]int) string {
    rows := [3]int{}
    cols := [3]int{}
    diag, antiDiag := 0, 0

    for i, move := range moves {
        player := 1
        if i%2 == 1 {
            player = -1
        }
        r, c := move[0], move[1]
        rows[r] += player
        cols[c] += player
        if r == c {
            diag += player
        }
        if r+c == 2 {
            antiDiag += player
        }
        if abs(rows[r]) == 3 || abs(cols[c]) == 3 || abs(diag) == 3 || abs(antiDiag) == 3 {
            if player == 1 {
                return "A"
            }
            return "B"
        }
    }

    if len(moves) == 9 {
        return "Draw"
    }
    return "Pending"
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

Go differences: Go uses fixed-size arrays for row and column counters and an explicit abs function because Go does not have a built-in abs for integers in older versions. The logic mirrors Python with type differences.

Worked Examples

Example 1: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]

Move Player Rows Cols Diag Anti-Diag Win?
[0,0] A [1,0,0] [1,0,0] 1 0 No
[2,0] B [1,0,-1] [0,0,-1] 1 -1 No
[1,1] A [1,1,-1] [0,1,-1] 2 0 No
[2,1] B [1,1,-1] [0,0,0] 2 -1 No
[2,2] A [1,1,0] [0,0,1] 3 -1 Yes, A wins

Example 2: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]

Player B wins on the last move by completing the first column.

Example 3: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]

No counters reach 3, and all moves are filled, so the result is "Draw".

Complexity Analysis

Measure Complexity Explanation
Time O(n) Iterate through all moves once, constant-time operations per move
Space O(1) Only a fixed number of counters are used (rows, cols, diag, anti_diag)

Even though the brute-force approach is acceptable for a 3x3 grid, the optimal counter method is cleaner, avoids repeated scanning, and scales better conceptually.

Test Cases

# Provided examples
assert Solution().tictactoe([[0,0],[2,0],[1,1],[2,1],[2,2]]) == "A"  # A wins
assert Solution().tictactoe([[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]) == "B"  # B wins
assert Solution().tictactoe([[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]) == "Draw"  # Draw

# Pending game
assert Solution().tictactoe([[0,0],[1,1]]) == "Pending"  # Not all moves played

# Immediate win
assert Solution().tictactoe([[0,0],[1,0],[0,1],[1,1],[0,2]]) == "A"  # A wins on first row

# Diagonal win
assert Solution().tictactoe([[0,0],[0,1],[1,1],[0,2],[2,2]]) == "A"  # A wins on diagonal
Test Why
Provided examples Validate correctness for sample cases
Pending game Tests early game