NUHMAN.com

🧩 Problem Statement

Design a TicTacToe class that allows two players to play a game of Tic-Tac-Toe on an n x n board.

Each move should be evaluated to determine if it causes a player to win.

📥 Function Signatures

python

TicTacToe(n): Initializes the board of size n.
move(row, col, player): Places a move and checks if it wins the game.

Returns:

• 0 → No one wins
• 1 → Player 1 wins
• 2 → Player 2 wins

🔢 Example

python

t = TicTacToe(3)
t.move(0, 0, 1) -> 0
t.move(0, 2, 2) -> 0
t.move(2, 2, 1) -> 0
t.move(1, 1, 2) -> 0
t.move(2, 0, 1) -> 0
t.move(1, 0, 2) -> 0
t.move(2, 1, 1) -> 1  # Player 1 wins

🚫 Brute Force Approach (Not Ideal)

You could use a 2D grid and scan the board for every move to check rows, columns, and diagonals.

But this results in O(n) time per move — too slow for large boards.

⚡ Optimized Strategy – O(1) Time per Move

Instead of storing the entire board:

• Use row sums and column sums.
• Maintain two diagonals: main and anti-diagonal.
• Add +1 for Player 1, -1 for Player 2.
• If abs(row/col/diag sum) == n, then that player wins.

✅ Python Code (Optimized)

python

class TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        self.diag = 0
        self.anti_diag = 0

    def move(self, row: int, col: int, player: int) -> int:
        mark = 1 if player == 1 else -1
        
        self.rows[row] += mark
        self.cols[col] += mark
        
        if row == col:
            self.diag += mark
        if row + col == self.n - 1:
            self.anti_diag += mark
        
        if (abs(self.rows[row]) == self.n or
            abs(self.cols[col]) == self.n or
            abs(self.diag) == self.n or
            abs(self.anti_diag) == self.n):
            return player
        
        return 0

🔍 Step-by-Step Example (n = 3)

Let’s say Player 1 marks:

• (0, 0) → rows[0] = 1, cols[0] = 1, diag = 1
• (2, 2) → rows[2] = 1, cols[2] = 1, diag = 2
• (2, 1) → rows[2] = 2, cols[1] = 1

Eventually, if any sum reaches n = 3, Player 1 wins.

⏱️ Time and Space Complexity

MetricValueTime ComplexityO(1) per moveSpace ComplexityO(n)

🧠 Real-World Use Cases

• Game development engines
• Multiplayer games
• AI simulations for board games

✅ Conclusion

LeetCode 348: Design Tic-Tac-Toe is a neat object-oriented design problem with a smart use of counters and math to achieve O(1) time moves. It’s a great example of how to avoid brute force checks with a clever data structure design.

This problem often comes up in system design rounds for real-time games or collaborative apps.