# Design Tic-Tac-Toe in O(1) per Move (LeetCode 348) "Design Tic-Tac-Toe" looks trivial, but the follow-up, *"can you check for a winner faster than O(n²) per move?"*, is what the interviewer is really after. ## Naive approach After each move, scan the move's row, its column and both diagonals: O(n) per move. Fine for 3x3, but the interviewer will push for better on an n x n board. ## O(1) idea: running sums Give player 1 the value 1 and player 2 the value -1. Keep: - `rows[i]`: the sum of the values in row i - `cols[j]`: the sum of the values in column j - `diag` and `anti`: the sums of the two diagonals A player wins when any of these reaches ` n` or `-n`. ```python class TicTacToe: def __init__(self, n): self.n = n self.rows = [0] * n self.cols = [0] * n self.diag = self.anti = 0 def move(self, r, c, player): v = 1 if player == 1 else -1 self.rows[r] = v self.cols[c] = v if r == c: self.diag = v if r c == self.n - 1: self.anti = v n = self.n if n in (abs(self.rows[r]), abs(self.cols[c]), abs(self.diag), abs(self.anti)): return player return 0 ``` O(1) time per move and O(n) space, because we never store the board itself. ## Assumptions to state The problem guarantees valid moves (no overwriting a cell, no moves after a win). In a real game class you'd keep the board too, to validate moves and to render it. ## Extending the design (OOD follow-ups) - `Player`, `Board` and `Game` classes, with `Game` owning turn order and win state. - Connect-K on a bigger board: the running-sum trick no longer works directly, so count consecutive pieces from the last move in each of four directions (still O(k)). - Undo: store the move history and subtract values when undoing. --- *Disclosure: I'm part of the [Linkjob AI](https://www.linkjob.ai/) team (an AI interview assistant).*