LeetCode 348 - Design Tic-Tac-Toe

LeetCode Problem 348

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Design, Matrix, Simulation

Solution

Problem Understanding

The problem asks us to design a data structure that simulates an n x n Tic-Tac-Toe game between two players. We need to implement a class that supports two operations:

• Initializing a game board of size n
• Processing moves one at a time and immediately determining whether the current move causes a player to win

A move is represented by three values:

• row, the row index where the player places a mark
• col, the column index where the player places a mark
• player, either 1 or 2

After every move, we must return:

• 0 if nobody has won yet
• 1 if player 1 wins
• 2 if player 2 wins

The winning condition is standard Tic-Tac-Toe logic:

• A complete row
• A complete column
• The main diagonal
• The anti-diagonal

The important part of this problem is the follow-up question. A naive implementation would check the entire board after every move, which can be expensive. The problem explicitly asks whether we can do better than O(n^2) per move.

The constraints help guide the expected solution:

• 2 <= n <= 100
• At most n^2 moves
• Every move is valid
• No duplicate moves
• No moves after someone wins

These guarantees simplify the implementation because we do not need to validate moves or handle invalid game states.

Several edge cases are important:

• A player may win on the main diagonal
• A player may win on the anti-diagonal
• A move may belong to both diagonals simultaneously, such as the center cell of an odd-sized board
• Small boards like 2 x 2 can produce wins quickly
• Large boards require efficient move processing

The key challenge is designing move() so that each call runs in constant time instead of scanning the board repeatedly.

Approaches

Brute Force Approach

The most straightforward implementation is to store the entire board and, after every move, scan:

• The entire row
• The entire column
• The main diagonal if applicable
• The anti-diagonal if applicable

This works because a player wins only if all cells in one of these lines belong to that player.

For example, after placing a mark at (row, col):

• Check whether every cell in board[row] belongs to the same player
• Check whether every cell in column col belongs to the same player
• If row == col, check the main diagonal
• If row + col == n - 1, check the anti-diagonal

This approach is correct because it directly verifies the winning conditions after each move.

However, it is inefficient. Each move may require scanning up to O(n) cells for rows, columns, and diagonals. If implemented carelessly by scanning the entire board, it could even become O(n^2) per move.

Optimal Approach

The key insight is that we do not need to store or inspect the entire board repeatedly.

A player wins only when they completely fill:

• One row
• One column
• One diagonal

Instead of storing the board state, we can maintain running counts:

• rows[i] tracks the cumulative score for row i
• cols[j] tracks the cumulative score for column j
• diagonal tracks the main diagonal
• anti_diagonal tracks the anti-diagonal

We use this trick:

• Player 1 contributes +1
• Player 2 contributes -1

If any counter reaches:

• +n, player 1 wins
• -n, player 2 wins

This works because only one player's marks can occupy a line completely.

For example, suppose n = 3.

If row 2 becomes:

X X X

Then the row counter becomes:

+1 +1 +1 = +3

Similarly, if player 2 fills a column:

O O O

The column counter becomes:

-1 -1 -1 = -3

This allows every move to run in constant time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per move	O(n²)	Stores full board and scans rows, columns, and diagonals
Optimal	O(1) per move	O(n)	Tracks row and column counts incrementally

Algorithm Walkthrough

1. Initialize four tracking structures:

• rows, an array of size n
• cols, an array of size n
• diagonal, an integer
• anti_diagonal, an integer

These structures keep cumulative scores for each line on the board. 2. Convert the player into a numeric value.

• Player 1 becomes +1
• Player 2 becomes -1

Using opposite signs allows both players to share the same counters cleanly. 3. Update the row counter.

Add the player's value to rows[row]. 4. Update the column counter.

Add the player's value to cols[col]. 5. Check whether the move lies on the main diagonal.

A cell belongs to the main diagonal when:

$row = col$

If true, update the diagonal counter. 6. Check whether the move lies on the anti-diagonal.

A cell belongs to the anti-diagonal when:

$row + col = n - 1$

If true, update the anti-diagonal counter. 7. Check for a winning condition.

If the absolute value of any updated counter becomes n, then one player has completely filled that line.

$|counter| = n$ 8. Return the winner if found.

• Return 1 if the counter is positive
• Return 2 if the counter is negative

9. If no counter reaches n or -n, return 0.

Why it works

The algorithm maintains an invariant:

• Every row, column, and diagonal counter equals the sum of contributions from moves placed in that line.

Because player 1 contributes +1 and player 2 contributes -1, a line can reach magnitude n only if all n cells belong to the same player. Therefore, checking whether a counter equals n or -n correctly identifies a winner immediately after each move.

Python Solution

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:
        value = 1 if player == 1 else -1

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

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

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

        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

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row, col, player)

The constructor initializes the bookkeeping arrays and diagonal counters. We do not store the full board because the problem only requires winner detection.

Inside move(), the current player is converted into either +1 or -1. This allows both players to share the same counters elegantly.

The row and column counters are updated immediately. If the move lies on either diagonal, the corresponding diagonal counter is updated as well.

Finally, the method checks whether any relevant counter has magnitude n. If so, the current player has completed a winning line, so we return that player number. Otherwise, the game continues and we return 0.

Go Solution

type TicTacToe struct {
	n            int
	rows         []int
	cols         []int
	diagonal     int
	antiDiagonal int
}

func Constructor(n int) TicTacToe {
	return TicTacToe{
		n:            n,
		rows:         make([]int, n),
		cols:         make([]int, n),
		diagonal:     0,
		antiDiagonal: 0,
	}
}

func (this *TicTacToe) Move(row int, col int, player int) int {
	value := 1
	if player == 2 {
		value = -1
	}

	this.rows[row] += value
	this.cols[col] += value

	if row == col {
		this.diagonal += value
	}

	if row+col == this.n-1 {
		this.antiDiagonal += value
	}

	if abs(this.rows[row]) == this.n ||
		abs(this.cols[col]) == this.n ||
		abs(this.diagonal) == this.n ||
		abs(this.antiDiagonal) == this.n {
		return player
	}

	return 0
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * obj := Constructor(n)
 * param_1 := obj.Move(row, col, player)
 */

The Go implementation mirrors the Python logic closely. Since Go does not provide a built-in integer abs() function, we define a helper manually.

Slices are used for rows and cols, which behave similarly to dynamic arrays in Python. The struct stores all counters directly.

Because Go passes structs by value by default, the Move() method uses a pointer receiver so updates persist across method calls.

Worked Examples

Example 1

n = 3

Initial state:

Variable	Value
rows	[0, 0, 0]
cols	[0, 0, 0]
diagonal	0
anti_diagonal	0

Move 1

move(0, 0, 1)

Player 1 contributes +1.

Structure	Updated Value
rows[0]	1
cols[0]	1
diagonal	1

State:

Variable	Value
rows	[1, 0, 0]
cols	[1, 0, 0]
diagonal	1
anti_diagonal	0

No counter reaches 3.

Return 0.

Move 2

move(0, 2, 2)

Player 2 contributes -1.

Structure	Updated Value
rows[0]	0
cols[2]	-1
anti_diagonal	-1

State:

Variable	Value
rows	[0, 0, 0]
cols	[1, 0, -1]
diagonal	1
anti_diagonal	-1

Return 0.

Move 3

move(2, 2, 1)

Player 1 contributes +1.

Structure	Updated Value
rows[2]	1
cols[2]	0
diagonal	2

State:

Variable	Value
rows	[0, 0, 1]
cols	[1, 0, 0]
diagonal	2
anti_diagonal	-1

Return 0.

Move 4

move(1, 1, 2)

Player 2 contributes -1.

This move belongs to both diagonals.

Structure	Updated Value
rows[1]	-1
cols[1]	-1
diagonal	1
anti_diagonal	-2

State:

Variable	Value
rows	[0, -1, 1]
cols	[1, -1, 0]
diagonal	1
anti_diagonal	-2

Return 0.

Move 5

move(2, 0, 1)

Structure	Updated Value
rows[2]	2
cols[0]	2
anti_diagonal	-1

Return 0.

Move 6

move(1, 0, 2)

Structure	Updated Value
rows[1]	-2
cols[0]	1

Return 0.

Move 7

move(2, 1, 1)

Structure	Updated Value
rows[2]	3
cols[1]	0

Now:

abs(rows[2]) == 3

Player 1 wins.

Return 1.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1) per move	Each move updates a fixed number of counters
Space	O(n)	Two arrays of size n are maintained

The algorithm achieves constant-time move processing because every operation involves only direct index updates and constant-time checks. No board scanning is required.

The space complexity is linear because we store row and column counters, each of size n. The diagonal counters require only constant extra space.

Test Cases

# Provided example
game = TicTacToe(3)

assert game.move(0, 0, 1) == 0  # first move
assert game.move(0, 2, 2) == 0  # opponent move
assert game.move(2, 2, 1) == 0  # diagonal progress
assert game.move(1, 1, 2) == 0  # center move
assert game.move(2, 0, 1) == 0  # row buildup
assert game.move(1, 0, 2) == 0  # column buildup
assert game.move(2, 1, 1) == 1  # player 1 wins row

# Row victory
game = TicTacToe(2)

assert game.move(0, 0, 1) == 0
assert game.move(1, 0, 2) == 0
assert game.move(0, 1, 1) == 1  # row completed

# Column victory
game = TicTacToe(2)

assert game.move(0, 0, 1) == 0
assert game.move(0, 1, 2) == 0
assert game.move(1, 0, 1) == 1  # column completed

# Main diagonal victory
game = TicTacToe(3)

assert game.move(0, 0, 1) == 0
assert game.move(0, 1, 2) == 0
assert game.move(1, 1, 1) == 0
assert game.move(0, 2, 2) == 0
assert game.move(2, 2, 1) == 1  # main diagonal win

# Anti-diagonal victory
game = TicTacToe(3)

assert game.move(0, 2, 2) == 0
assert game.move(0, 0, 1) == 0
assert game.move(1, 1, 2) == 0
assert game.move(1, 0, 1) == 0
assert game.move(2, 0, 2) == 2  # anti-diagonal win

# Larger board without winner
game = TicTacToe(5)

assert game.move(0, 0, 1) == 0
assert game.move(1, 1, 2) == 0
assert game.move(2, 2, 1) == 0
assert game.move(3, 3, 2) == 0
assert game.move(4, 4, 1) == 0  # no full diagonal yet

# Center cell contributes to both diagonals
game = TicTacToe(3)

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

Test	Why
Provided example	Validates standard gameplay
Row victory	Ensures row tracking works
Column victory	Ensures column tracking works
Main diagonal victory	Validates main diagonal logic
Anti-diagonal victory	Validates anti-diagonal logic
Larger board without winner	Confirms no false positives
Center cell test	Ensures both diagonals update correctly

Edge Cases

One important edge case occurs when a move lies on both diagonals simultaneously. This happens only at the center cell of an odd-sized board. A buggy implementation may update only one diagonal counter. Our implementation explicitly checks both conditions independently, so both counters are updated correctly.

Another edge case is very small boards, especially 2 x 2. Wins can occur after only two moves from the same player. Some implementations accidentally assume more moves are required. Since our algorithm checks counters immediately after every move, wins are detected correctly regardless of board size.

A third important edge case is alternating contributions from different players in the same row or column. For example, if player 1 and player 2 both place marks in a row, the counter values cancel out partially. This is why the +1 and -1 technique works so effectively. A row can reach magnitude n only if every cell belongs to the same player.

Another subtle edge case is avoiding unnecessary board storage. A naive implementation might allocate an entire n x n matrix even though winner detection does not require it. Our solution stores only aggregate counters, reducing memory usage from O(n²) to O(n).