[Medium] 348. Design Tic-Tac-Toe

Difficulty: Medium
Category: Design, Array, Matrix
Companies: Amazon, Google, Microsoft, Facebook

Design a Tic-tac-toe game that is played between two players on an n x n grid.

A move is guaranteed to be valid and is placed on an empty block. Once a winning condition is reached, no more moves are allowed. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Implement the TicTacToe class:

• TicTacToe(int n) Initializes the object the size of the board n.
• int move(int row, int col, int player) Indicates that the player with id player plays at the cell (row, col) of the board. The move is guaranteed to be a valid move, and the two players alternate in making moves. Returns:
  • 0 if there is no winner yet
  • 1 if player 1 wins
  • 2 if player 2 wins

Examples

Example 1:

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]

Explanation:
TicTacToe ticTacToe = new TicTacToe(3);
Assume that player 1 is "X" and player 2 is "O" in the board.
ticTacToe.move(0, 0, 1); // return 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

ticTacToe.move(0, 2, 2); // return 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

ticTacToe.move(2, 2, 1); // return 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

ticTacToe.move(1, 1, 2); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

ticTacToe.move(2, 0, 1); // return 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

ticTacToe.move(1, 0, 2); // return 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

ticTacToe.move(2, 1, 1); // return 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Constraints

• 2 <= n <= 100
• player is 1 or 2
• 0 <= row, col < n
• At most n^2 calls will be made to move

Solution Approaches

Approach 1: Naive Implementation

Algorithm:

1. Store the entire board as a 2D array
2. For each move, check all rows, columns, and diagonals
3. Return winner if any line is complete

Time Complexity: O(n) per move
Space Complexity: O(n²)

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

    def move(self, row: int, col: int, player: int) -> int:
        self.board[row][col] = 'X' if player == 1 else 'O'

        if self.win(player):
            return player

        return 0

    def win(self, player: int) -> bool:
        ch = 'X' if player == 1 else 'O'
        n = len(self.board)

        # rows
        for i in range(n):
            if all(self.board[i][j] == ch for j in range(n)):
                return True

        # cols
        for j in range(n):
            if all(self.board[i][j] == ch for i in range(n)):
                return True

        # main diagonal
        if all(self.board[i][i] == ch for i in range(n)):
            return True

        # anti diagonal
        if all(self.board[i][n - i - 1] == ch for i in range(n)):
            return True

        return False

Solution Explanation

Approach: Row/column traversal (this problem)

Key idea: Difficulty:** Medium

How the code works: Difficulty: Medium Category: Design, Array, Matrix

• Treat the grid as a graph with 4- or 8-directional neighbors.
• Row-major vs column-major traversal affects cache and logic.
• Boundary checks on every neighbor expansion.

Walkthrough — input ["TicTacToe", "move", "move", "move", "move", "move", "move", "move"], expected output [null, 0, 0, 0, 0, 0, 0, 1]:

TicTacToe ticTacToe = new TicTacToe(3); Assume that player 1 is “X” and player 2 is “O” in the board. ticTacToe.move(0, 0, 1); // return 0 (no one wins) |X| | | | | | | // Player 1 makes a move at (0, 0). | | | |

Time: O(1) vs O(n) per move · Space: see analysis

Implementation Details

Counter Update Logic

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

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

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

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

        if row + col == self.n - 1:
            self.antiDiagonal += curr

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

        return 0

Win Condition Check

curr = 1 if player == 1 else -1

rows[row] += curr
cols[col] += curr

if row == col:
    diagonal += curr

if row + col == n - 1:
    antiDiagonal += curr

Edge Cases

1. First Move: No winner yet
2. Diagonal Win: Both main and anti-diagonal can win simultaneously
3. Last Move: Game ends immediately when someone wins
4. Large Board: Optimized approach scales better

Follow-up Questions

• What if the board could be larger (n > 100)?
• How would you handle more than 2 players?
• What if you needed to detect draws?
• How would you implement undo functionality?

Common Mistakes

• Skipping edge cases (empty input, single element, boundaries).
• Off-by-one errors in loops and index ranges.
• Forgetting to handle the case when no valid answer exists.

Related Problems

• LC 794: Valid Tic-Tac-Toe State
• LC 1275: Find Winner on a Tic Tac Toe Game
• LC 348: Design Tic-Tac-Toe

Design Patterns

1. State Tracking: Maintain game state efficiently
2. Counter Optimization: Use mathematical properties to avoid full scans
3. Space-Time Trade-off: Trade space for time efficiency
4. Incremental Updates: Update only affected counters

Performance Considerations

• Memory Usage: Optimized approach uses O(n) vs O(n²) space
• Time Complexity: O(1) vs O(n) per move
• Scalability: Optimized approach handles large boards efficiently
• Cache Efficiency: Linear arrays have better cache performance than 2D arrays

Key Takeaways

• Pattern: Row/column traversal (this problem)
• Difficulty:** Medium
• Category:** Design, Array, Matrix

References

• LC 348: Design Tic-Tac-Toe on LeetCode
• LeetCode Discuss — LC 348: Design Tic-Tac-Toe
• LeetCode Editorial (may require premium)

Template Reference

• Data Structure Design

Thinking Process

Difficulty: Medium

Category: Design, Array, Matrix

• Treat the grid as a graph with 4- or 8-directional neighbors.
• Row-major vs column-major traversal affects cache and logic.
• Boundary checks on every neighbor expansion.

Common Approaches

Typical techniques for this pattern:

Approach	Time	Space	Notes
Row/column traversal (this problem)	O(nm)	O(1)	Simulation, spiral
BFS/DFS on grid	O(nm)	O(nm)	Islands, shortest path
Matrix as graph	O(nm)	O(nm)	4/8-directional neighbors
Transpose / rotate	O(nm)	O(1)	In-place rotation tricks