Game state design

The interview question is Design Tic-Tac-Toe (LeetCode 348). Almost every first attempt looks the same: keep an n × n board of marks, and after every move walk the played row, the played column, and both diagonals to check for a winner. That's O(n) per move on an n × n grid. The right design is O(1) per move on the same grid, using O(n) memory total instead of O(n²). Both numbers, the per-move cost and the total memory, improve at once with no sacrifice anywhere.

The trick that buys both is small enough to fit on one line: instead of storing the board, store what the board would tell you when you scanned it. Maintain four counters (one per row, one per column, one per diagonal, one per anti-diagonal) and update them in place as moves arrive. The board never gets materialized. The scan that the naive design runs after every move is replaced by four integer comparisons against ±n. This chapter is what those four counters look like, why they're sufficient, and where the same idea (don't store the state, store the predicate) shows up at chess-engine scale.

What "design" means here#

A game-state design problem hands you two operations and asks for an API:

• A mutator: a player makes a move at (row, col).
• A predicate query, "did that move just win?", which fires after every mutation.

The naive design materializes the board (the natural mental model) and re-derives the predicate by scanning. Every board cell is stored; every cell on the played lines is read. For a 100×100 grid (LC 348's max constraint), that's 10,000 cells of memory and roughly 400 reads per move.^[1]

The good design materializes the predicate's inputs, not the board. For tic-tac-toe the predicate is "does some line have all n marks from one player?" The inputs to that predicate are per-line aggregate counts. Track those directly; never store the cells.

The class holds four aggregate counters, not a 2D board; a Move updates exactly the counters whose lines pass through (row, col).

The shift from "store the board, scan to query" to "store the query's answer, update on write" is the move. CLRS calls the technique aggregate analysis: maintain a small derived state alongside the primary data so each operation does O(1) work amortized.^[2] The same pattern shows up in Hash maps and hash sets for size tracking, in difference arrays for range-update queries, and at the largest scale in chess-engine bitboards. The interview question is the smallest interesting instance of all of them.

The four-counter algorithm#

The state for an n × n board is four pieces:

• rows[i]: counter for row i, range [-n, n].
• cols[j]: counter for column j, range [-n, n].
• diag: counter for the main diagonal (0,0)..(n-1, n-1).
• antiDiag: counter for the anti-diagonal (0, n-1)..(n-1, 0).

Player 1 contributes +1 to every counter that includes the played cell. Player 2 contributes -1. The sign trick collapses what would otherwise be eight counters (one per line per player) into four; each counter's value equals (player-1 marks on the line) - (player-2 marks on the line), so the value is +n exactly when player 1 owns the line and -n exactly when player 2 does.^[1:1]

# LC 348. Design Tic-Tac-Toe

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        """LC 348: place player's mark; return player if the move wins, else 0."""
        delta = 1 if player == 1 else -1
        self.rows[row] += delta
        self.cols[col] += delta
        if row == col:
            self.diag += delta
        if row + col == self.n - 1:
            self.anti_diag += delta

        target = self.n if player == 1 else -self.n
        if (self.rows[row] == target or self.cols[col] == target
                or self.diag == target or self.anti_diag == target):
            return player
        return 0

// LC 348. Design Tic-Tac-Toe

public class TicTacToe {
    private final int n;
    private final int[] rows;
    private final int[] cols;
    private int diag;
    private int antiDiag;

    public TicTacToe(int n) {
        this.n = n;
        this.rows = new int[n];
        this.cols = new int[n];
        this.diag = 0;
        this.antiDiag = 0;
    }

    public int move(int row, int col, int player) {
        int delta = (player == 1) ? 1 : -1;
        rows[row] += delta;
        cols[col] += delta;
        if (row == col) diag += delta;
        if (row + col == n - 1) antiDiag += delta;

        int target = (player == 1) ? n : -n;
        if (rows[row] == target || cols[col] == target
                || diag == target || antiDiag == target) {
            return player;
        }
        return 0;
    }
}

// LC 348. Design Tic-Tac-Toe

#include <vector>

class TicTacToe {
public:
    TicTacToe(int n) : n_(n), rows_(n, 0), cols_(n, 0), diag_(0), antiDiag_(0) {}

    int move(int row, int col, int player) {
        int delta = (player == 1) ? 1 : -1;
        rows_[row] += delta;
        cols_[col] += delta;
        if (row == col) diag_ += delta;
        if (row + col == n_ - 1) antiDiag_ += delta;

        int target = (player == 1) ? n_ : -n_;
        if (rows_[row] == target || cols_[col] == target
                || diag_ == target || antiDiag_ == target) {
            return player;
        }
        return 0;
    }

private:
    int n_;
    std::vector<int> rows_;
    std::vector<int> cols_;
    int diag_;
    int antiDiag_;
};

// LC 348. Design Tic-Tac-Toe

package main

type TicTacToe struct {
	n        int
	rows     []int
	cols     []int
	diag     int
	antiDiag int
}

func NewTicTacToe(n int) *TicTacToe {
	return &TicTacToe{
		n:    n,
		rows: make([]int, n),
		cols: make([]int, n),
	}
}

func (t *TicTacToe) Move(row, col, player int) int {
	delta := 1
	if player == 2 {
		delta = -1
	}
	t.rows[row] += delta
	t.cols[col] += delta
	if row == col {
		t.diag += delta
	}
	if row+col == t.n-1 {
		t.antiDiag += delta
	}

	target := t.n
	if player == 2 {
		target = -t.n
	}
	if t.rows[row] == target || t.cols[col] == target ||
		t.diag == target || t.antiDiag == target {
		return player
	}
	return 0
}

Two updates always fire (rows[row] and cols[col]), and zero, one, or two diagonal updates fire depending on the cell. The corners participate in three lines. Take (0, 0): it's on the main diagonal because 0 == 0, but not on the anti-diagonal unless n = 1. The center of an odd-sized board is the only cell on all four lines. Every other cell is on two or three. The predicate check is four constant-time comparisons regardless.

Two unconditional counter updates plus zero, one, or two diagonal updates; the win-check tests four counters, never any cell.

Why the move can only complete a line through (row, col)#

The win check looks at four counters and skips the rest. The reason it's allowed to is geometric: a move at (row, col) can only complete a line that passes through (row, col). Lines that don't include the played cell didn't change on this move, so their counters didn't change, so they can't have just crossed the ±n threshold.^[1:2]

On an n × n grid, exactly four lines pass through any given cell: its row, its column, the main diagonal (when row == col), and the anti-diagonal (when row + col == n - 1). The algorithm checks exactly those, and exactly those are the only lines the move could have just completed. The check is both necessary and sufficient.

This is the same O(1) per-operation reasoning that CLRS §17.1 develops as aggregate analysis: maintain just enough derived state alongside the primary data, and per-operation queries collapse to constant time.^[2:1] It's the design pattern, not just a tic-tac-toe trick.

Why +n is the right target#

A row of length n is owned by player 1 iff every cell in it is a player-1 mark. With +1 per player-1 mark and -1 per player-2 mark, the row counter equals the player-1 count minus the player-2 count. The maximum value is n (all player 1). Any value strictly less than n means at least one cell is empty or belongs to player 2, so the row isn't owned. The threshold +n is exactly the line-ownership predicate, with no slack.

The symmetric argument for -n and player 2 follows by sign. There's no edge case where the threshold misfires: counters move by exactly ±1 per move and can only land on +n or -n from the immediately prior ±(n-1) value, which is reachable in one move only if every other cell on the line was already owned.

Tracing one game#

A short trace makes the algorithm concrete. Take n = 3, the canonical tic-tac-toe board. Player 1 plays (0, 0); player 2 plays (1, 0); player 1 plays (0, 1); player 2 plays (1, 1); player 1 plays (0, 2).

On move 5, rows[0] reaches +3 = +n. Player 1 owns row 0. The function returns 1. Note that diag swung 1 → 0 on move 4 (player 2 marked (1,1), which is on the main diagonal); every line that could matter has its counter live at all times, and the algorithm doesn't have to remember which lines are "interesting" yet.

What it actually costs#

The headline is the second row. O(1) per move with O(n) total memory is the textbook win; both axes improve at once. For n = 100 (LC 348's max), the counter-based design uses 200 ints versus the naive design's 10,000, and runs zero board scans versus four per move.

The bitboard row at the bottom is the same idea on a 64-square chessboard. Crafty's bitboard architecture, formalized in Hyatt's 1999 Rotated Bitmaps paper, packs each piece type's occupancy into a single 64-bit unsigned integer.^[5:1] "Is the king attacked?" becomes one bitwise AND of the precomputed attack mask and the king's bitboard. Same shape: derive the predicate's input from incremental updates; the per-query cost collapses to O(1) regardless of board size.

Generalizations beyond tic-tac-toe#

Position keys with Zobrist hashing#

Chess engines reach the same position via different move orders. Searching the same position twice wastes work, so engines memoize evaluations in a transposition table keyed on a position hash. The hash needs to update incrementally as moves are made and unmade; recomputing it from scratch every move would defeat the cache.

Zobrist hashing solves this in 1970.^[6] Assign each (piece, square, color) triple a random 64-bit string at startup. The position's hash is the XOR of the bitstrings for every piece currently on the board, plus a side-to-move bitstring. Making a move updates the hash with two XORs (remove the piece from its old square, add it to the new square); unmaking re-applies the same two XORs because XOR is its own inverse.^[6:1]

The same pattern: don't store the position. Store the predicate's input (the hash) and update it locally.

Snake as deque-with-membership-set#

LC 353 Design Snake Game asks for a snake that moves on a grid, growing on food and dying on self-collision. The snake's body is naturally a queue: the head is the front, the tail is the back, and a move pushes a new head and pops the old tail. But the per-move predicate is "does the new head collide with any current body cell?", and walking the queue to check is O(body length) per move.

The fix is to maintain a hash set of occupied cells alongside the deque. Push the new head: add to deque, add to set. Pop the old tail: remove from deque, remove from set. The collision check is one set lookup. O(1) per move regardless of snake length.^[7]

The order-of-operations subtlety on this one: when the new head lands on the cell the old tail is about to vacate, the collision check fires falsely if the set still contains the tail. Remove the tail from the set first, test the new head, then add it. Same pattern as the LC 348 four-counter algorithm: the invariant is what's stored, not the literal grid.

Where readers go wrong#

Problem ladder#

CORE (solve all to claim chapter mastery)#

• LC 1275 — Find Winner on a Tic Tac Toe Game [Easy] • game-state-incremental (reference: Python only)
• LC 794 — Valid Tic-Tac-Toe State [Medium] • game-state-invariants ★ (reference: Python only)
• LC 750 — Number Of Corner Rectangles [Medium] • game-board-enumeration (reference: Python only)

STRETCH (optional)#

• LC 348 — Design Tic-Tac-Toe [Medium] • game-state-incremental (Premium; full four-language code at lc-348/sol.py)
• LC 1496 — Path Crossing [Easy] • board-state-hashing (reference: Python only)

Where this leads#

The closest sibling is LRU cache, which uses the same "maintain a derived view alongside the primary data" pattern (a doubly linked list ordered by recency, alongside the hash map keyed by user). Union-Find is the next pattern to reach for when the per-move predicate is "are these two cells in the same connected region?", the natural successor for board-state problems beyond tic-tac-toe (LC 305 Number of Islands II is the canonical instance). The chess-engine generalization in §"Generalizations beyond tic-tac-toe" connects to backtracking-based game-tree search; AIMA Chapter 5 is the standard reference and Knuth's Dancing Links is the canonical write-up of the data structure that makes such searches fast.

References#