LC 348: Design Tic-Tac-Toe

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

Problem Statement

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

Clarification Questions

Before diving into the solution, here are 5 important clarifications and assumptions to discuss during an interview:

  1. Game rules: What are the Tic-Tac-Toe rules? (Assumption: n×n board, players alternate, win by filling row/column/diagonal)

  2. Move operation: What does move() do? (Assumption: Places player’s mark at (row, col), returns winner if game ends, 0 otherwise)

  3. Win condition: When does a player win? (Assumption: Player fills entire row, column, or diagonal with their marks)

  4. Return value: What should move() return? (Assumption: Integer - player number if they win, 0 if no winner yet)

  5. Valid moves: Are moves guaranteed valid? (Assumption: Per constraints, moves are within bounds, but should check for already occupied cells)

Interview Deduction Process (20 minutes)

Step 1: Brute-Force Approach (5 minutes)

After each move, check all rows, columns, and diagonals to see if any are completely filled by one player. This requires checking O(n) rows, O(n) columns, and 2 diagonals after each move, giving O(n) time per move. This works but can be optimized.

Step 2: Semi-Optimized Approach (7 minutes)

Maintain counts for each row, column, and diagonal. For each move, increment the count for the corresponding row, column, and potentially diagonals. Check if any count equals n. However, need to handle both players: use positive counts for player 1 and negative counts for player 2, or maintain separate counts for each player.

Step 3: Optimized Solution (8 minutes)

Maintain arrays for row counts, column counts, and two diagonal counts. For player 1, increment counts; for player 2, decrement counts (or use separate arrays). After each move, check if the absolute value of any count equals n. This achieves O(1) time per move with O(n) space, which is optimal. The key insight is that we only need to check the row, column, and diagonals affected by the current move, and maintaining running counts allows O(1) checking instead of scanning entire rows/columns.

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 {
public:
    TicTacToe(int n) {
        board.resize(n, vector<int>(n));
    }
    
    int move(int row, int col, int player) {
        if(player == 1)
            board[row][col] = 'X';
        else
            board[row][col] = 'O';
        if(win(player)) return player;
        return 0;
    }
    
private:
    vector<vector<int>> board;

    bool win(int player){
        char ch;
        if(player == 1) ch = 'X';
        else ch = 'O';
        int n = board.size();

        // Check rows
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                if(board[i][j] == ch) cnt++;
            }
            if(cnt == n) return true;
        }

        // Check columns
        for(int i = 0; i < n; i++) {
            int cnt = 0;
            for(int j = 0; j < n; j++) {
                if(board[j][i] == ch) cnt++;
            }
            if(cnt == n) return true;
        }

        // Check main diagonal
        int cnt = 0;
        for(int i = 0; i < n; i++) {
            if(board[i][i] == ch) cnt++;
        }
        if(cnt == n) return true;

        // Check anti-diagonal
        cnt = 0;
        for(int i = 0; i < n; i++) {
            if(board[i][n - i - 1] == ch) cnt++;
        }
        if(cnt == n) return true;
        
        return false;
    }
};

Key Insight: Instead of checking the entire board, maintain counters for each row, column, and diagonal. Use +1 for player 1 and -1 for player 2.

Algorithm:

  1. Maintain arrays for row counts, column counts, and diagonal counts
  2. For each move, update relevant counters
  3. Check if any counter reaches ±n (absolute value equals n)

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

class TicTacToe {
public:
    TicTacToe(int n): rows(n), cols(n), diagonal(0), antiDiagonal(0) {
    }
    
    int move(int row, int col, int player) {
        int curr = player == 1 ? 1 : -1;
        int n = rows.size();

        rows[row] += curr;
        cols[col] += curr;
        if(row == col) diagonal += curr;
        if(row == n - col - 1) antiDiagonal += curr;

        if(abs(rows[row]) == n || abs(cols[col]) == n ||
           abs(diagonal) == n || abs(antiDiagonal) == n)
           return player;
        return 0;
    }
    
private:
    vector<int> rows, cols;
    int diagonal, antiDiagonal;
};

Algorithm Analysis

Naive vs Optimized Approach

Aspect Naive Optimized
Time per move O(n) O(1)
Space O(n²) O(n)
Implementation Simple Slightly complex
Scalability Poor Excellent

Key Optimizations

  1. Counter-Based Tracking: Instead of scanning the board, maintain running counts
  2. Player Encoding: Use +1 and -1 to distinguish players
  3. Diagonal Detection: Check if row == col (main diagonal) and row == n - col - 1 (anti-diagonal)
  4. Absolute Value Check: abs(count) == n indicates a win

Implementation Details

Counter Update Logic

int curr = player == 1 ? 1 : -1;  // Player encoding
rows[row] += curr;                 // Update row count
cols[col] += curr;                 // Update column count
if(row == col) diagonal += curr;   // Main diagonal
if(row == n - col - 1) antiDiagonal += curr;  // Anti-diagonal

Win Condition Check

if(abs(rows[row]) == n || abs(cols[col]) == n ||
   abs(diagonal) == n || abs(antiDiagonal) == n)
   return player;

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?

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

This problem demonstrates the importance of optimizing data structures and algorithms for repeated operations, showing how mathematical insights can lead to significant performance improvements.