Find Winner on a Tic Tac Toe Game: Simulation Made Simple

Two players, A and B, take turns placing marks on a 3x3 tic-tac-toe board. A always goes first and plays X, B plays O. Given a list of moves where each move is [row, col], determine who wins. Return "A" if player A wins, "B" if player B wins, "Draw" if all nine squares are filled with no winner, or "Pending" if the game is still in progress and no one has won yet.

This is LeetCode 1275: Find Winner on a Tic Tac Toe Game, and it is a clean exercise in simulation. The board is small (3x3), so brute force works fine. But an optimized approach using row, column, and diagonal counters is more elegant and teaches a pattern that scales to larger grids.

Why this problem matters

Tic-tac-toe is the simplest win-detection problem you will encounter. The board is fixed at 3x3, so you could hard-code all eight winning lines and check them after every move. That works, but it misses the point.

The real lesson here is the counter-based approach: maintain running sums for each row, each column, and the two diagonals. When a player places a mark, increment (for A) or decrement (for B) the relevant counters. A win happens when any counter reaches +3 or -3. This same idea extends to N-Queens validation, Sudoku checking, and any grid problem where you need to track properties along rows, columns, or diagonals.

Two approaches

Brute force: check all lines after each move

After every move, scan all eight possible winning lines (3 rows, 3 columns, 2 diagonals) on the board. If any line has three matching marks, that player wins. This is O(1) per move since the board size is fixed, but it requires maintaining the full board state and checking up to eight lines each time.

Optimized: row, column, and diagonal counters

Instead of storing the board, maintain counters:

• rows[0..2]: one counter per row
• cols[0..2]: one counter per column
• diag: counter for the main diagonal (where row == col)
• anti_diag: counter for the anti-diagonal (where row + col == 2)

When player A moves, add +1 to the relevant counters. When player B moves, add -1. After each move, check if any affected counter has reached +3 (A wins) or -3 (B wins). You only need to check the counters that the current move touches, not all of them.

This approach is clean because you never build or scan the board. Each move updates at most four counters (row, column, and possibly one or two diagonals), and the win check is immediate.

The solution

def tictactoe(moves: list[list[int]]) -> str:
    rows = [0] * 3
    cols = [0] * 3
    diag = 0
    anti_diag = 0

    for i, (r, c) in enumerate(moves):
        sign = 1 if i % 2 == 0 else -1

        rows[r] += sign
        cols[c] += sign

        if r == c:
            diag += sign
        if r + c == 2:
            anti_diag += sign

        if abs(rows[r]) == 3 or abs(cols[c]) == 3 or abs(diag) == 3 or abs(anti_diag) == 3:
            return "A" if sign == 1 else "B"

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

Even-indexed moves (0, 2, 4, ...) belong to player A, and odd-indexed moves (1, 3, 5, ...) belong to player B. The sign variable assigns +1 to A and -1 to B. After updating the counters, we check whether any counter has reached 3 or -3 in absolute value. If the loop finishes without a winner, the result depends on whether all nine squares have been filled.

Visual walkthrough

Notice how the main diagonal counter climbs from 1 to 2 to 3 as player A places X at (0,0), (1,1), and (2,2). The moment diag hits 3, we know A has completed the diagonal and return "A" immediately. There is no need to scan the board.

Complexity analysis

Here m is the number of moves (at most 9).

Time: Both approaches process each move once. Brute force checks up to 8 lines per move, but since the board is 3x3, that is a constant factor. The counter-based approach checks at most 4 counters per move. Both are O(m) overall, which simplifies to O(1) since m is at most 9.

Space: The counter-based approach uses 8 integers (3 rows + 3 columns + 2 diagonals). The brute force approach uses a 3x3 board. Both are O(1) since the board size is fixed.

The building blocks

1. Row, column, and diagonal tracking

The core pattern is maintaining aggregate values along grid axes. Instead of scanning the grid to compute a property (like "are all cells in this row the same?"), you maintain running counters that update incrementally. This same pattern appears in:

• N-Queens: track which columns and diagonals are occupied
• Valid Sudoku: track which numbers appear in each row, column, and box
• Set Matrix Zeroes: track which rows and columns need zeroing

rows = [0] * n
cols = [0] * n
for r, c in positions:
    rows[r] += value
    cols[c] += value

2. Sign-based player encoding

Using +1 and -1 to distinguish two players is a common trick. It lets you use a single set of counters instead of separate tracking per player. The sign encodes ownership: positive means player A dominates, negative means player B dominates, and a sum of +n or -n means one player has filled the entire line.

sign = 1 if player == "A" else -1
counter += sign
if abs(counter) == n:
    winner = "A" if sign == 1 else "B"

Edge cases

• Draw with 9 moves: all squares are filled and no player has three in a row. The loop completes without returning, and len(moves) == 9 is true, so we return "Draw".
• Pending with fewer than 9 moves: the game has not produced a winner yet and there are still empty squares. len(moves) is less than 9, so we return "Pending".
• Win on the main diagonal vs anti-diagonal: the main diagonal has r == c (cells (0,0), (1,1), (2,2)). The anti-diagonal has r + c == 2 (cells (0,2), (1,1), (2,0)). The center cell (1,1) belongs to both diagonals, so placing a mark there updates both diag and anti_diag.
• A wins on the very last move: player A makes the 9th move (index 8, which is even). The win check fires before we reach the draw check, so A is correctly returned.

From understanding to recall

You now see how the counter-based approach works: assign +1 to A and -1 to B, update row/col/diagonal counters per move, and check for 3 or -3. The logic is compact. But can you write it from memory?

The details that slip away: remembering that r + c == 2 identifies the anti-diagonal (not r + c == n), handling the sign with i % 2, and checking abs instead of comparing against both 3 and -3 separately. Small things, but they matter when you are writing code under time pressure.

Spaced repetition turns this understanding into fluency. You write the counter loop, the diagonal checks, and the win detection from scratch at increasing intervals. After a few rounds, you do not need to think about whether the anti-diagonal condition is r + c == 2 or r + c == n - 1. You just write it.

Related posts

• Valid Tic-Tac-Toe State - A harder validation problem on the same 3x3 board, checking whether a given board state could have been reached through legal play
• Set Matrix Zeroes - Uses row and column tracking to propagate information across a grid, the same axis-based thinking pattern
• Valid Sudoku - Row, column, and box tracking for a 9x9 grid, scaling the same counter pattern to a larger board

CodeBricks breaks Find Winner on a Tic Tac Toe Game into its counter-tracking and sign-encoding building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a grid simulation problem shows up in your interview, you do not hesitate. You just write it.