348. Design Tic-Tac-Toe

348

MediumData Structure DesignAggregate counters (rows/cols/diagonals)Running line counters

Design Tic-Tac-Toe

Design a TicTacToe class for an n x n board. move(row, col, player) records that the given player (1 or 2) placed a mark at that empty cell and returns the id of the player who wins after that move, or 0 if there is no winner yet. A player wins by filling any full row, full column, or either diagonal with their marks. Assume all moves are valid and target empty cells.

Open official problem prompt ↗

In plain English

Report the winner immediately after each move on an n x n Tic-Tac-Toe board without scanning the board.

Picture it like this

Like a scoreboard that tracks each row and column's net lean toward player 1 or player 2 - the moment any line leans fully one way (all n cells), the game is over.

Example

Input: n = 3; moves = [(0,0,1),(0,2,2),(2,2,1),(1,1,2),(2,0,1),(1,0,2),(2,1,1)]
Output: [0, 0, 0, 0, 0, 0, 1]
Why: After player 1's move at (2,1), row 2 holds player 1's marks at (2,0),(2,1),(2,2), completing a full row of 3.

Constraints

2 <= n <= 100player is 1 or 21 <= row, col <= nEach cell is used at most once per gameAt most n^2 calls to move

Pattern lesson

See the pattern, then code

Running line counters

↗

Data Structure Design

An API whose operations must meet strict O(1) or O(log n) contracts.. A row/column/diagonal wins only when all n cells belong to one player. Give player 1 a +1 and player 2 a -1, and keep a signed count per line; a line hits +n or -n exactly when it is entirely one player.

New words, made simpleKnow these before the algorithm

Main diagonal: Cells where row == col (top-left to bottom-right).
Anti-diagonal: Cells where row + col == n - 1 (top-right to bottom-left).
Signed counter: A tally that goes up for one player and down for the other, so its sign encodes ownership.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Rescan the board each move

Correct but re-reads up to n cells every move and stores the whole grid.

Store the full grid and, after each move, check that move's row, column, and diagonals cell by cell.

Time O(n) per moveSpace O(n^2)

Best choiceIncremental signed counters

Constant time per move and only O(n) memory - no board needed.

Maintain one counter per row, per column, and for the two diagonals; a win is a counter reaching +n or -n.

Time O(1) per moveSpace O(n)

The rule we keep true

Invariant

Each counter always equals (number of player-1 marks in that line) minus (number of player-2 marks in that line).

Why this is correct

Reasoning

A line is a win only when all n of its cells belong to one player. Since players never overwrite cells, its counter equals +n only if all n are player 1, and -n only if all n are player 2 - so the |counter| == n test is both necessary and sufficient.

The algorithm in three movesSay these aloud before coding

1Keep integer counters for each row, each column, the main diagonal, and the anti-diagonal

rows = [1, 0, 3 -> wins]

2On a move, add +1 for player 1 or -1 for player 2 to that move's row and column counters

player 1 add = +1

3Update the main diagonal counter when row == col, and the anti-diagonal when row + col == n - 1

abs(rows[2]) == 3 == n

4If any touched counter has absolute value n, return the current player; otherwise return 0

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

r00

r11

r2:+32

c03

c14

c25

diag6

anti7

1 · Readplayer 1 at (0,0)

2 · AskAny line at n?

3 · Update staterows[0]=1, cols[0]=1, diag=1

4 · Resultreturn 0

Key takeaway

Row-2 counter reaches +3 (= n) on player 1's final move, signalling a win.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-8State
Four counter groups: one array for rows, one for columns, and single ints for the two diagonals.
2
Lines 11-12Direction of the mark
Player 1 contributes +1, player 2 contributes -1, so a line's sign tells you whose it is.
3
Lines 13-18Update touched lines
Only the move's row and column always change; diagonals change only when the cell lies on them.
4
Lines 19-22Win test
If any updated counter's magnitude equals n the current player just completed a line.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

n = 2 board (a single move can complete a diagonal)
Cell on both diagonals, e.g. the center of an odd board
A game that ends with no winner (every move returns 0)

Common beginner mistakes

Forgetting the anti-diagonal condition row + col == n - 1
Checking == n instead of the absolute value, which misses player 2's wins
Storing the full board and rescanning, defeating the O(1) goal

Check your understanding

Why does a single signed counter suffice per line instead of two separate counts for the two players?

PyPython 3 · solution.py

Optimal

1class TicTacToe:2    def __init__(self, n: int):3        self.n = n4        self.rows = [0] * n5        self.cols = [0] * n6        self.diag = 07        self.anti = 089    def move(self, row: int, col: int, player: int) -> int:10        add = 1 if player == 1 else -111        self.rows[row] += add12        self.cols[col] += add13        if row == col:14            self.diag += add15        if row + col == self.n - 1:16            self.anti += add17        if (abs(self.rows[row]) == self.n or abs(self.cols[col]) == self.n18                or abs(self.diag) == self.n or abs(self.anti) == self.n):19            return player20        return 0

Time complexityO(1) per moveOptimized

Space complexityO(n)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonMicrosoftBloombergGoogle

Design Tic-Tac-Toe

Design Tic-Tac-Toe

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Data Structure Design