Lab 21 — Tic-Tac-Toe (Streaming Winner Detection)

Goal

Implement Tic-Tac-Toe (LC 348) where players alternate moves on an N × N board and move(row, col, player) returns 0 (no winner yet) or the player number on a winning move. The naive O(N²) per-move full-scan is unacceptable; achieve O(1) per move by maintaining row, column, and diagonal counters. After this lab you should write the implementation in <15 minutes.

Background Concepts

The non-trivial bit of Tic-Tac-Toe-as-a-data-structure-problem is the per-move winner check. Each cell affects exactly one row, one column, and (if on a diagonal) at most one or two diagonals. By incrementing player-1’s counter by +1 and player-2’s by -1 on the same axes, a counter that hits +N means player 1 won that axis, -N means player 2 won. This collapses the O(N²) scan to O(1).

Diagonals: the main diagonal is the line where row == col; the anti-diagonal is where row + col == N - 1. A cell is on the main diagonal iff row == col; on the anti-diagonal iff row + col == N - 1. The center cell of an odd-N board sits on both.

This is the cleanest real example of “exchange a redundant scan for a maintained counter” — a recurring pattern in real code (running averages, sliding maxes, materialized aggregates in databases).

Interview Context

A 20-minute warmup at Amazon, Google, and Microsoft. Often paired with the LRU lab as a phone-screen double-feature. The interviewer wants O(1) per move, clean class API, and at least one or two follow-ups about extending to N-in-a-row Connect Four-style games (where the winning condition is more complex).

Problem Statement

Implement TicTacToe(n) and move(row, col, player) -> int:

  • The board is n × n and starts empty.
  • Players alternate (caller manages turn order; you don’t validate it for this version).
  • player is 1 or 2.
  • Each move places the player’s mark at (row, col). Assume the cell is empty.
  • Return the player’s number if this move results in a win (full row, column, main diagonal, or anti-diagonal of that player); otherwise return 0.
  • Once a player has won, the game ends; further moves are not part of the spec but should be defensively handled.

Constraints

  • 1 ≤ n ≤ 100.
  • Each call to move is O(1) target.
  • Up to 10^6 moves across the lifetime of an instance.

Clarifying Questions

  1. Are row and col 0-indexed? (Yes.)
  2. Is the cell guaranteed empty? (Per LC 348: yes. In practice, validate defensively.)
  3. Do we need to detect a draw? (Not in LC 348; doable as move_count == n*n.)
  4. Once a player wins, are further moves undefined? (Yes; either short-circuit to that winner or raise.)
  5. Can the same player call move twice in a row? (Spec assumes alternating; we do not enforce.)

Examples

g = TicTacToe(3)
g.move(0, 0, 1)  # 0  player 1 at (0,0)
g.move(0, 2, 2)  # 0  player 2 at (0,2)
g.move(2, 2, 1)  # 0
g.move(1, 1, 2)  # 0
g.move(2, 0, 1)  # 0
g.move(1, 0, 2)  # 0
g.move(2, 1, 1)  # 1  player 1 wins via row 2 (0,0 main diag was already two of 1's)

Initial Brute Force

class TicTacToeNaive:
    def __init__(self, n):
        self.n = n
        self.b = [[0] * n for _ in range(n)]
    def move(self, r, c, p):
        self.b[r][c] = p
        # check row
        if all(self.b[r][j] == p for j in range(self.n)): return p
        if all(self.b[i][c] == p for i in range(self.n)): return p
        if r == c and all(self.b[i][i] == p for i in range(self.n)): return p
        if r + c == self.n - 1 and all(self.b[i][self.n - 1 - i] == p for i in range(self.n)): return p
        return 0

This is O(N) per move. For N = 100 and 10^6 moves: 10^8 — slow but passing. The point is structural: it scans the whole row/column/diagonal every time even though the move only changed one cell.

Brute Force Complexity

move: O(N) per call. Total: O(M · N).

Optimization Path

Replace each row/col/diagonal full-scan with a maintained counter. Use +1 for player 1, -1 for player 2; a counter at ±N is a win. The diagonals are special-cased by the row == col and row + col == N - 1 predicates — we only update them when the cell is on the diagonal. Now every check is a single integer comparison.

Final Expected Approach

State: rows[N], cols[N], diag (scalar), anti (scalar). Each is an integer counter. On move(r, c, player): compute delta = +1 if player == 1 else -1. Increment rows[r], cols[c], and conditionally diag and anti. If any of the four updated counters has absolute value N → that player wins.

Data Structures Used

  • list[int] of size N for rows.
  • list[int] of size N for columns.
  • int for the main diagonal counter.
  • int for the anti-diagonal counter.
  • (Optional) list[list[int]] board for defensive duplicate-move detection.

Correctness Argument

A row of N copies of player 1 produces a counter of +N exactly when all N cells are player 1, because every player-1 move on that row contributes +1 and no player-2 move contributes there (since the cell is occupied by player 1). Symmetric for player 2 → -N. Same argument for columns and the two diagonals. The diagonal counter is only updated for cells on the diagonal, so it correctly counts only diagonal cells.

Complexity

OperationTimeSpace
moveO(1)O(N) for row/col counters

Implementation Requirements

class TicTacToe:
    def __init__(self, n: int):
        if n < 1:
            raise ValueError("n must be >= 1")
        self._n = n
        self._rows = [0] * n
        self._cols = [0] * n
        self._diag = 0
        self._anti = 0
        self._winner = 0  # 0 = no winner yet

    def move(self, row: int, col: int, player: int) -> int:
        if self._winner:
            return self._winner
        if not (0 <= row < self._n and 0 <= col < self._n):
            raise IndexError(f"({row}, {col}) out of bounds for n={self._n}")
        if player not in (1, 2):
            raise ValueError(f"player must be 1 or 2, got {player}")

        delta = 1 if player == 1 else -1
        target = self._n if player == 1 else -self._n

        self._rows[row] += delta
        self._cols[col] += delta
        if row == col:
            self._diag += delta
        if row + col == self._n - 1:
            self._anti += delta

        if (self._rows[row] == target
                or self._cols[col] == target
                or self._diag == target
                or self._anti == target):
            self._winner = player
            return player
        return 0

Tests

def test_row_win_player1():
    g = TicTacToe(3)
    assert g.move(0, 0, 1) == 0
    assert g.move(1, 0, 2) == 0
    assert g.move(0, 1, 1) == 0
    assert g.move(1, 1, 2) == 0
    assert g.move(0, 2, 1) == 1

def test_col_win_player2():
    g = TicTacToe(3)
    g.move(0, 0, 1); g.move(0, 1, 2)
    g.move(1, 0, 1); g.move(1, 1, 2)
    g.move(2, 2, 1); 
    assert g.move(2, 1, 2) == 2

def test_diagonal_win():
    g = TicTacToe(3)
    g.move(0, 0, 1); g.move(0, 1, 2)
    g.move(1, 1, 1); g.move(0, 2, 2)
    assert g.move(2, 2, 1) == 1

def test_anti_diagonal_win():
    g = TicTacToe(3)
    g.move(0, 2, 1); g.move(0, 0, 2)
    g.move(1, 1, 1); g.move(0, 1, 2)
    assert g.move(2, 0, 1) == 1

def test_no_winner_on_partial():
    g = TicTacToe(3)
    assert g.move(0, 0, 1) == 0
    assert g.move(1, 1, 2) == 0

def test_n_equals_one():
    g = TicTacToe(1)
    assert g.move(0, 0, 1) == 1

def test_invalid_player():
    g = TicTacToe(3)
    try: g.move(0, 0, 3)
    except ValueError: pass
    else: assert False

def test_move_after_winner():
    g = TicTacToe(3)
    for c in range(3): g.move(0, c, 1)
    # subsequent moves still report the winner
    assert g.move(1, 1, 2) == 1

def test_large_n_no_win():
    g = TicTacToe(100)
    # Fill 99 of player 1's row 0 — should not win.
    for c in range(99):
        assert g.move(0, c, 1) == 0

Follow-up Questions

  1. How would you test it? Unit tests for each axis (row, col, both diagonals, by both players). Property test: random move sequences; oracle is the naive O(N) scan; assert outputs match. Edge: n=1 (any move wins). Edge: anti-diagonal at the corners only.
  2. What is the consistency model? Single-threaded, linearizable trivially. If multiple threads race on move, the counters can interleave and a player can falsely fail to win. Wrap with a Lock if concurrent.
  3. What configuration knobs would you expose? Just n. Resist adding “win condition = K-in-a-row instead of N” — that’s a different problem (Connect Four / Gomoku). If asked, see Connect Four extension below.
  4. How would you handle a poison-pill input? Out-of-bounds coords (IndexError), invalid player (ValueError), repeated cell (defensive: track board and reject). The current implementation rejects bounds and player; cell-overwrite detection is an explicit follow-up.
  5. How would you extend to K-in-a-row on an N×N board (Gomoku, Connect Four)? Counters no longer suffice — you need to find any window of K consecutive same-player cells. Two options: (a) on each move, scan the row, column, and both diagonals through the cell looking for K-in-a-row centered on the move (O(K) per move), or (b) maintain run-length encodings per axis (more memory, O(1) per move). For interview-time, (a) is the right answer — clean and O(K), not O(N).
  6. What metrics would you emit? moves_total, wins_total{player=1|2}, time_to_win histogram. Game-balance metrics for product analytics; otherwise sparse.

Product Extension

The “maintained counter instead of full scan” pattern shows up everywhere: real-time sports scores (a goal updates a single team total instead of recomputing from a play log), database materialized views (incrementally maintained, not recomputed), Prometheus counters (the rate() function avoids re-scanning the whole series). Tic-Tac-Toe is the simplest possible illustration.

Language/Runtime Follow-ups

  • Python: as above. Lists are 8 bytes per int reference; for very large N, array.array("i", [0]*n) is denser.
  • Java: int[] rows, int[] cols, int diag, int anti. No autoboxing in the hot path.
  • Go: same — value types throughout, no allocations after construction.
  • C++: std::vector<int>. Make move non-virtual; this is hot-path code.
  • JS/TS: Int32Array(n) for rows and cols — denser than a regular Array.

Common Bugs

  1. Off-by-one in the anti-diagonal predicate: row + col == n - 1, not n or n + 1.
  2. Using +1 for both players (and checking count == N and count == -N) — mistake. Use opposite-sign deltas.
  3. Forgetting to update the diagonal counter when the move is on the diagonal — counter stays stuck.
  4. Scaling the win threshold incorrectly (target = n if player == 1 else -n). A cleaner version uses abs(counter) == n and sign(counter) == sign(delta).
  5. Not guarding against repeated cells — same (r, c) updated twice can spuriously win for one player or unjustly cancel out.
  6. Concurrent calls without a lock: counters become inconsistent and the win condition fires on the wrong player.

Debugging Strategy

When wins are missed: print (rows, cols, diag, anti) after each move; trace which counter should have hit ±N. When wins fire spuriously: same trace — usually the diagonal predicate is wrong. When tests pass for player 1 but not player 2: confirm delta = -1 and target = -N for player 2; sign errors are common.

Mastery Criteria

  • Stated the O(1)-per-move counter approach in <30 seconds.
  • Wrote the diagonal predicates (r == c, r + c == n - 1) without prompting.
  • Implemented from a blank screen in <15 minutes with all tests passing.
  • Listed the K-in-a-row extension and named the right scan strategy.
  • Articulated why this is a “maintained counter” pattern in <30 seconds.
  • Wrote tests covering both diagonals and n=1.