Design a TicTacToe

Problem

348. Design Tic-Tac-Toe

Naive solution

code

Time complexity for move: O(n²)

Space complexity: O(n²)

class TicTacToe:
def __init__(self, n: int):
        """
        Initialize your data structure here.
        """
        self.rows = [[None]*n for _ in range(n)]
        self.cols = [[None]*n for _ in range(n)]
        self.diag = [None]*n
        self.anti_diag = [None]*n
        self._moves = 0
        self.n = n
        
    def win(self, player):
        for row in self.rows:
            if set(row)=={player}:return True
        for col in self.cols:
            if set(col)=={player}:return True
        if set(self.diag)=={player} or set(self.anti_diag)=={player}:return True
        return False
    def move(self, row: int, col: int, player: int) -> int:
        """
        Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins.
        """
        self._moves +=player
        self.rows[row][col] = player
        self.cols[col][row] = player
        if row==col:self.diag[row]=player
        if row+col==self.n-1:self.anti_diag[row]=player
        if self._moves<self.n:return 0
        return player if self.win(player) else 0
        if self._moves>self.n**2:
            return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

runtime

Runtime: 2884 ms, faster than 5.12% of Python3 online submissions for Design Tic-Tac-Toe.
Memory Usage: 16.5 MB, less than 16.67% of Python3 online submissions for Design Tic-Tac-Toe.

Can we do better?

Yes

Code is from here

class TicTacToe(object):

    def __init__(self, n):
        self.row, self.col, self.diag, self.anti_diag, self.n = [0] * n, [0] * n, 0, 0, n
        
    def move(self, row, col, player):
        offset = player * 2 - 3
        self.row[row] += offset
        self.col[col] += offset
        if row == col:
            self.diag += offset
        if row + col == self.n - 1:
            self.anti_diag += offset
        if self.n in [self.row[row], self.col[col], self.diag, self.anti_diag]:
            return 2
        if -self.n in [self.row[row], self.col[col], self.diag, self.anti_diag]:
            return 1
        return 0

runtime

Runtime: 92 ms, faster than 55.68% of Python3 online submissions for Design Tic-Tac-Toe.
Memory Usage: 16.3 MB, less than 16.67% of Python3 online submissions for Design Tic-Tac-Toe.

Rewrite the code

class TicTacToe:
def __init__(self, n: int):
        """
        Initialize your data structure here.
        """
        self.rows = [0]*n
        self.cols = [0]*n
        self.diag, self.anti_diag = 0, 0
        self.n = n
def move(self, row: int, col: int, player: int) -> int:
        """
        Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins.
        """
        offset = 1 if player==1 else -1
        self.rows[row] += offset
        self.cols[col] += offset
        if row==col:self.diag += offset
        if row+col == self.n-1:self.anti_diag += offset
        possible_win_locations = [self.rows[row], self.cols[col], self.diag, self.anti_diag]
        if offset*self.n in possible_win_locations:
            return player
        return 0
# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)

It has a similar runtime

Runtime: 80 ms, faster than 96.82% of Python3 online submissions for Design Tic-Tac-Toe.
Memory Usage: 16.2 MB, less than 16.67% of Python3 online submissions for Design Tic-Tac-Toe.