We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Design Tic-Tac-Toe

Number: 348

Difficulty: Medium

Paid? Yes

Companies: Meta, Databricks, Amazon, Microsoft, Apple, Airbnb, TikTok, Atlassian, Goldman Sachs, Tesla, Chewy, Qualcomm, Google

Problem Description

Design a Tic-Tac-Toe game that is played on an n x n board. Two players take alternating moves where a move is valid only if it is placed on an empty cell and immediate winning conditions are enforced. A player wins by placing n of their marks consecutively in a row, column, or any of the two diagonals. Once a winning move is made, no further moves are allowed.

Key Insights

  • Instead of scanning the entire board after every move, count marks for each row, column, and both diagonals.
  • Use incremental updates to quickly identify a win in O(1) time.
  • By assigning +1 for player 1 and -1 for player 2, a player's win condition is verified when the absolute count equals n in any counter.
  • This approach avoids O(n^2) processing per move and leverages space-efficient counter arrays.

Space and Time Complexity

Time Complexity: O(1) per move
Space Complexity: O(n), primarily from the row and column counter arrays

Solution

The solution utilizes four counters: one for each row, one for each column, and two for the diagonals (main and anti-diagonal). Each move updates the respective counters by a delta value (+1 for player 1 and -1 for player 2). After updating, the algorithm checks if the absolute value of any counter equals n, indicating a win. This computation is performed in constant time per move, ensuring efficiency even as the board size increases.

Code Solutions

Below are the implementations in Python, JavaScript, C++, and Java with explanatory inline comments.

class TicTacToe:
    def __init__(self, n: int):
        # Initialize board size and counter arrays for rows and columns.
        self.n = n
        self.rows = [0] * n
        self.cols = [0] * n
        # Initialize main diagonal and anti-diagonal counters.
        self.diag = 0
        self.antiDiag = 0

    def move(self, row: int, col: int, player: int) -> int:
        # Define delta: +1 for player 1 and -1 for player 2.
        delta = 1 if player == 1 else -1
        
        # Update row and column counters.
        self.rows[row] += delta
        self.cols[col] += delta
        
        # Update the main diagonal if applicable.
        if row == col:
            self.diag += delta
        # Update the anti-diagonal if applicable.
        if row + col == self.n - 1:
            self.antiDiag += delta
        
        # Check if any counter reaches the absolute value of n.
        if (abs(self.rows[row]) == self.n or
            abs(self.cols[col]) == self.n or
            abs(self.diag) == self.n or
            abs(self.antiDiag) == self.n):
            return player
        return 0
← Back to All Questions