What is "Check Winner in O(1): The Hidden DSA in TicTacToe" about?

Optimizing winner detection from O(N³) to O(1) using precomputed count maps. The hidden algorithmic challenge in TicTacToe interviews.

What topics does "Check Winner in O(1): The Hidden DSA in TicTacToe" cover?

This article covers: tictactoe winner detection, o1 algorithm, lld dsa problem, count map strategy, optimization lld.

Check Winner in O(1): The Hidden DSA in TicTacToe

In a machine coding interview, once the design is set, the interviewer will often push on efficiency. If your winner detection scans the entire board after every move, you are looking at O(N^2) work per move. For an NxN board, that total work is O(N^3). Here is how I use a space-time tradeoff to optimize this check to O(1).

The Essentials

Brute force is too slow: Scanning rows, columns, and diagonals after every move is O(N^2) per move.
Count Maps Strategy: Maintain counts for every row, column, and diagonal.
The O(1) Condition: A player wins when their count in any map reaches the board size N.
Space Complexity: O(N * P) where P is the number of players. This is a small price for O(1) performance.
Update first, then check: Complete all map updates before returning a result to keep state consistent for undo.

The Brute Force Problem

The naive approach is to loop through all N cells in the current row, then all N in the column, then (if applicable) both diagonals.

Total complexity: O(N) per move. Since there are N^2 moves in a full game, the total complexity is O(N^3). For a 100x100 board, this is 1,000,000 operations. We can do it in 10,000.

The Optimization: Count Maps

ExpandO(1) Check Visualization

Instead of re-reading the board, we maintain separate count maps for each winning line.

Row and Column Maps

Each row has its own Map: Map<Symbol, Integer>. When a player makes a move at (row, col), we look up the map for that row and increment the count for that player's symbol.

class RowWinningStrategy implements WinningStrategy {
  private rowMaps: Map<string, number>[] = [];

  checkWinner(board: Board, move: Move): boolean {
    const row = move.getCell().getRow();
    const symbol = move.getPlayer().getSymbol().getChar();
    
    if (!this.rowMaps[row]) this.rowMaps[row] = new Map();
    
    const current = (this.rowMaps[row].get(symbol) || 0) + 1;
    this.rowMaps[row].set(symbol, current);
    
    return current === board.getSize();
  }
}

This check is O(1). We perform the same logic for columns.

Diagonal Maps

Any NxN board has exactly two diagonals.

Main Diagonal: row == col.
Anti-Diagonal: row + col == size - 1.

We maintain just two maps for the entire board to track these diagonal counts.

Handling the Center Cell

A corner cell like (0, 0) only affects one row, one column, and one diagonal. But the center cell (1, 1) on a 3x3 board affects both diagonals. Our DiagonalWinningStrategy must check both conditions independently.

Consistency for Undo

There is a subtle trap here. If a move triggers a win in the row map, you might be tempted to return true immediately. Don't.

If that move also affected a diagonal, and you return before updating the diagonal map, your internal state will be inconsistent. If the move is later undone, the diagonal count will be wrong. Always update all relevant maps first, then check if any of them reached the winning condition.

Efficiency isn't just about speed; it's about being clever with state. In the next post, we will look at how to organize this into a clean MVC architecture.