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 icols[j]: the sum of the values in column jdiagandanti: the sums of the two diagonals
A player wins when any of these reaches n or -n.
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,BoardandGameclasses, withGameowning 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 team (an AI interview assistant).