LeetCode 348: Design Tic-Tac-Toe

Problem Restatement

We need to design a Tic-Tac-Toe game played by two players on an n x n board.

The class supports two operations:

Method	Meaning
TicTacToe(n)	Initializes an n x n board
move(row, col, player)	Places player at position (row, col) and returns the winner

The rules are:

Rule	Meaning
Valid move	Every move is guaranteed to be placed on an empty cell
Game state	No moves are made after a winner exists
Winner	A player wins by filling one row, column, main diagonal, or anti-diagonal
Return value	0 for no winner, 1 if player 1 wins, 2 if player 2 wins

The problem asks us to avoid scanning the whole board after each move. A counter-based design gives O(1) time per move.

Input and Output

Item	Meaning
Input	Board size n, then moves (row, col, player)
Output	Winner after each move
Player IDs	1 and 2
Winning line	Any full row, full column, main diagonal, or anti-diagonal

Class shape:

class TicTacToe:

    def __init__(self, n: int):
        ...

    def move(self, row: int, col: int, player: int) -> int:
        ...

Examples

Example:

Input:
["TicTacToe", "move", "move", "move", "move", "move", "move", "move"]
[[3], [0,0,1], [0,2,2], [2,2,1], [1,1,2], [2,0,1], [1,0,2], [2,1,1]]

Output:
[null, 0, 0, 0, 0, 0, 0, 1]

Board size is 3.

Moves:

Move	Player	Result
(0, 0)	1	0
(0, 2)	2	0
(2, 2)	1	0
(1, 1)	2	0
(2, 0)	1	0
(1, 0)	2	0
(2, 1)	1	1

At the last move, player 1 fills row 2:

X X X

So move(2, 1, 1) returns 1.

First Thought: Store the Board and Scan

A direct method is to store the full board.

After every move:

1. Check the whole row.
2. Check the whole column.
3. Check the main diagonal if needed.
4. Check the anti-diagonal if needed.

This works, but each move can cost:

O(n)

The board itself also costs:

O(n^2)

We can do better because we only need to know whether a line has been completed.

Key Insight

A player wins when one of their counters reaches n.

We can store:

Counter	Meaning
rows[i]	Net marks in row i
cols[j]	Net marks in column j
diagonal	Net marks on main diagonal
anti_diagonal	Net marks on anti-diagonal

Use +1 for player 1.

Use -1 for player 2.

Then:

Counter value	Meaning
n	Player 1 filled that line
-n	Player 2 filled that line

This avoids storing the whole board.

Because moves are guaranteed valid, we do not need to check whether a cell is already occupied.

Algorithm

Initialize:

rows = [0] * n
cols = [0] * n
diagonal = 0
anti_diagonal = 0

For each move:

1. Convert player to score:
   1. +1 for player 1
   2. -1 for player 2
2. Add score to rows[row].
3. Add score to cols[col].
4. If row == col, add score to diagonal.
5. If row + col == n - 1, add score to anti_diagonal.
6. If any affected counter has absolute value n, return player.
7. Otherwise return 0.

Walkthrough

Use n = 3.

Initial state:

rows = [0, 0, 0]
cols = [0, 0, 0]
diagonal = 0
anti_diagonal = 0

Move:

move(0, 0, 1)

Player 1 has score +1.

Update:

rows[0] = 1
cols[0] = 1
diagonal = 1

No counter reaches 3, so return 0.

Move:

move(2, 2, 1)

Update:

rows[2] = 1
cols[2] = 1
diagonal = 2

Still no winner.

Move:

move(2, 0, 1)

Update:

rows[2] = 2
cols[0] = 2
anti_diagonal = 1

Move:

move(2, 1, 1)

Update:

rows[2] = 3
cols[1] = 1

Now:

abs(rows[2]) == 3

So player 1 wins.

Return 1.

Correctness

A player wins exactly when they have placed marks in all n cells of one row, one column, or one diagonal.

The algorithm updates exactly the counters affected by the current move:

Move position	Updated counters
Any cell (row, col)	rows[row], cols[col]
row == col	diagonal
row + col == n - 1	anti_diagonal

For player 1, every mark contributes +1.

So a line filled entirely by player 1 has counter value n.

For player 2, every mark contributes -1.

So a line filled entirely by player 2 has counter value -n.

A mixed line cannot have absolute value n, because marks from the two players cancel each other.

After each move, only the row, column, and possible diagonals containing that move can become newly winning lines. Checking those counters is therefore sufficient.

Thus, the algorithm returns the correct winner after every move.

Complexity

Operation	Time	Why
Constructor	O(n)	Creates row and column counter arrays
move()	O(1)	Updates and checks a constant number of counters

Space	Value	Why
Extra space	O(n)	Stores n row counters and n column counters

Implementation

class TicTacToe:

    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diagonal = 0
        self.anti_diagonal = 0

    def move(self, row: int, col: int, player: int) -> int:
        score = 1 if player == 1 else -1

        self.rows[row] += score
        self.cols[col] += score

        if row == col:
            self.diagonal += score

        if row + col == self.n - 1:
            self.anti_diagonal += score

        if (
            abs(self.rows[row]) == self.n
            or abs(self.cols[col]) == self.n
            or abs(self.diagonal) == self.n
            or abs(self.anti_diagonal) == self.n
        ):
            return player

        return 0

Code Explanation

Store the board size:

self.n = n

Create counters for rows and columns:

self.rows = [0] * n
self.cols = [0] * n

Create counters for the two diagonals:

self.diagonal = 0
self.anti_diagonal = 0

Convert the player into a signed score:

score = 1 if player == 1 else -1

Update the affected row and column:

self.rows[row] += score
self.cols[col] += score

If the move is on the main diagonal:

if row == col:
    self.diagonal += score

If the move is on the anti-diagonal:

if row + col == self.n - 1:
    self.anti_diagonal += score

Check whether any affected counter reaches n in absolute value:

if abs(self.rows[row]) == self.n:
    return player

The implementation combines all four checks into one condition.

Testing

def run_tests():
    game = TicTacToe(3)

    assert game.move(0, 0, 1) == 0
    assert game.move(0, 2, 2) == 0
    assert game.move(2, 2, 1) == 0
    assert game.move(1, 1, 2) == 0
    assert game.move(2, 0, 1) == 0
    assert game.move(1, 0, 2) == 0
    assert game.move(2, 1, 1) == 1

    game = TicTacToe(3)

    assert game.move(0, 0, 1) == 0
    assert game.move(1, 0, 1) == 0
    assert game.move(2, 0, 1) == 1

    game = TicTacToe(3)

    assert game.move(0, 2, 2) == 0
    assert game.move(1, 1, 2) == 0
    assert game.move(2, 0, 2) == 2

    game = TicTacToe(1)

    assert game.move(0, 0, 1) == 1

    print("all tests passed")

run_tests()

Test meaning:

Test	Why
Official-style sequence	Checks row win after several moves
Column win	Checks vertical counter
Anti-diagonal win	Checks row + col == n - 1
n = 1	First move immediately wins