# Problem

348. Design Tic-Tac-Toe

# Naive solution

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: 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 = ndef 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.`

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

## Jimmy Shen

Data Scientist/MLE/SWE @takemobi