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:

The rules are:

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

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:

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:

Use +1 for player 1.

Use -1 for player 2.

Then:

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:

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

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: