LeetCode 348: Design Tic-Tac-Toe Solution in Python – A Step-by-Step Guide

What Is LeetCode 348: Design Tic-Tac-Toe?

In LeetCode 348: Design Tic-Tac-Toe, you need to implement a TicTacToe class for an n x n board with two methods: __init__(n) to set up the game, and move(row, col, player) to place a mark and return the winner (0 if none, 1 or 2 if a player wins). For example, on a 3x3 board, placing marks might lead to a win after 5 moves. This problem tests your ability to optimize win detection, connecting to concepts in LeetCode 794: Valid Tic-Tac-Toe State.

Problem Statement

• Input:
• __init__(n): Integer n for board size.
• move(row, col, player): Row, column (0-based), player (1 or 2).
• Output:
• move(): Integer—0 (no win), 1 (player 1 wins), 2 (player 2 wins).
• Rules:
• Players 1 and 2 alternate placing marks (X and O).
• Win by filling a row, column, or diagonal with n marks.
• Assume valid moves (empty cells).

Constraints

• 1 <= n <= 100
• 0 <= row, col < n
• player is 1 or 2
• At most n² calls to move()

Examples

• 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] (Player 1 wins with diagonal [0,0],[1,1],[2,2])
• Input: ["TicTacToe","move","move"], [[2],[0,0,1],[1,1,2]]
• Output: [null,0,0] (No win yet)
• Input: ["TicTacToe","move","move","move","move"], [[2],[0,0,1],[0,1,2],[1,0,1],[1,1,2]]
• Output: [null,0,0,0,0] (No win, board full)

Understanding the Problem: Designing the Game

To solve LeetCode 348: Design Tic-Tac-Toe in Python, we need a class that initializes an n x n board and handles moves, efficiently checking for wins in rows, columns, or diagonals. A naive approach—tracking the full board and scanning after each move—is O(n²) per move, too slow for frequent calls. We’ll use:

• Best Solution (Counter-Based): O(1) time per move, O(n) space—fast and optimal.
• alternative Solution (Board-Tracking): O(n) time per move, O(n²) space—clear but less efficient.

Let’s start with the counter-based solution, explained in a beginner-friendly way.

Best Solution: Counter-Based Approach

Why This Is the Best Solution

The counter-based approach is the top choice for LeetCode 348 because it’s blazing fast—O(1) time per move, O(n) space—and avoids scanning the board by tracking row, column, and diagonal sums directly. It uses arrays to increment counters for each player, detecting wins when a counter hits ±n. It’s like keeping a scoreboard that instantly shows the winner—smart and quick!

How It Works

Think of this as a scorekeeper:

• Step 1: Initialize:
• Arrays for rows, columns, diagonals (main and anti).
• Player 1 adds +1, Player 2 adds -1.
• Step 2: Make Move:
• Update row[r], col[c], diag (if r==c), anti_diag (if r+c==n-1).
• Check if any counter reaches n (Player 1) or -n (Player 2).
• Step 3: Return Result:
• 1 or 2 if win, 0 if not.
• Step 4: Why It Works:
• Counters track net effect of moves.
• O(1) updates and checks per move.

It’s like tallying wins with a single glance!

Step-by-Step Example

Example: n = 3, moves: [(0,0,1), (0,2,2), (2,2,1), (1,1,2), (2,0,1)]

• Init: rows = [0,0,0], cols = [0,0,0], diag = 0, anti_diag = 0
• (0,0,1): rows[0]=1, cols[0]=1, diag=1, no win (0)
• (0,2,2): rows[0]=0, cols[2]=-1, no win (0)
• (2,2,1): rows[2]=1, cols[2]=0, diag=2, no win (0)
• (1,1,2): rows[1]=-1, cols[1]=-1, diag=1, no win (0)
• (2,0,1): rows[2]=2, cols[0]=2, anti_diag=1, diag=2 → no win yet
• Next hypothetical move (1,1,1) would make diag=3, win for 1
• Result: [0, 0, 0, 0, 0] (example ends before win)

Code with Detailed Line-by-Line Explanation

Copy codeclass 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:
        # Player value: 1 for Player 1, -1 for Player 2
        val = 1 if player == 1 else -1

        # Update counters
        self.rows[row] += val
        self.cols[col] += val
        if row == col:
            self.diag += val
        if row + col == self.n - 1:
            self.anti_diag += val

        # Check for win
        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

• Lines 3-7: Init n, row/col arrays, diagonal counters.
• Lines 10-23: move():
• Set val (+1 or -1) based on player.
• Update row, col, and diagonals if applicable.
• Check if any counter hits ±n for a win.
• Time Complexity: O(1) per move—constant updates/checks.
• Space Complexity: O(n)—arrays of size n.

This is like a game-score genius—fast and sleek!

Alternative Solution: Board-Tracking Approach

Why an Alternative Approach?

The board-tracking approach—O(n) time per move, O(n²) space—uses a full n x n board to store moves and checks rows, columns, and diagonals after each move. It’s the simplest way to visualize the game but slower due to win-checking scans. It’s like playing on a real board—clear but less efficient!

How It Works

Track and scan:

• Step 1: Init n x n board.
• Step 2: Place move, update board.
• Step 3: Check rows, cols, diagonals for n matches.

Step-by-Step Example

Example: n = 2, moves: [(0,0,1), (1,1,2)]

• Init: board = [[0,0], [0,0]]
• (0,0,1): board = [[1,0], [0,0]], no win
• (1,1,2): board = [[1,0], [0,2]], no win
• Result: [0, 0]

Code for Board-Tracking Approach

Copy codeclass TicTacToe:
    def __init__(self, n: int):
        self.n = n
        self.board = [[0] * n for _ in range(n)]

    def move(self, row: int, col: int, player: int) -> int:
        self.board[row][col] = player

        # Check row
        if all(self.board[row][j] == player for j in range(self.n)):
            return player

        # Check column
        if all(self.board[i][col] == player for i in range(self.n)):
            return player

        # Check main diagonal
        if row == col and all(self.board[i][i] == player for i in range(self.n)):
            return player

        # Check anti-diagonal
        if row + col == self.n - 1 and all(self.board[i][self.n-1-i] == player for i in range(self.n)):
            return player

        return 0

• Time Complexity: O(n) per move—scan row/col/diags.
• Space Complexity: O(n²)—board storage.

It’s a board-watching checker—vivid but heavy!

Comparing the Two Solutions

• Counter-Based (Best):
• Pros: O(1) time per move, O(n) space, fast and scalable.
• Cons: Counter logic less visual.
• Board-Tracking (Alternative):
• Pros: O(n) time per move, O(n²) space, intuitive board.
• Cons: Slower and space-heavy.

Counter-based wins for efficiency.

Additional Examples and Edge Cases

• n=1, [(0,0,1)]: [1].
• n=2, [(0,0,1), (0,1,2)]: [0, 0].
• n=3, all empty: No win initially.

Both handle these, but counter-based is faster.

Complexity Breakdown

• Counter-Based: Time O(1) per move, Space O(n).
• Board-Tracking: Time O(n) per move, Space O(n²).

Counter-based is the clear choice.

Key Takeaways

• Counter-Based: Tally wins—efficient!
• Board-Tracking: Watch the board—clear!
• Python: Arrays and logic shine—see [Python Basics](/python/basics).
• Games: Counters beat scans.

Final Thoughts: Win the Game

LeetCode 348: Design Tic-Tac-Toe in Python is a game-design delight. The counter-based solution offers speed and elegance, while board-tracking provides a tangible baseline. Want more game challenges? Try LeetCode 794: Valid Tic-Tac-Toe State or LeetCode 1275: Find Winner on a Tic Tac Toe Game. Ready to play? Head to Solve LeetCode 348 on LeetCode (premium) and design that Tic-Tac-Toe today!