Python O(1) solution, with O(n) extra space


  • 0
    H
    
        def __init__(self, n):
            """
            Initialize your data structure here.
            :type n: int
            """
            self.board = [[None]*n for x in range(n)]
            # number of moves in each row and column
            self.record = [[{},{}],[{},{}]]
            self.diag = [{},{}]
            
    
        def move(self, row, col, player):
            if self.board[row][col]!=None: return 0
            
            n = len(self.board)
            k = player - 1
            self.board[row][col] = 1
            
            if row not in self.record[k][0]:
                self.record[k][0][row] = 1
            else:
                self.record[k][0][row] += 1
            
            if col not in self.record[k][1]:
                self.record[k][1][col] = 1
            else:
                self.record[k][1][col] += 1
    
            if row==col:
                if 'diag1' not in self.diag[k]:
                    self.diag[k]['diag1']=1
                else:
                    self.diag[k]['diag1']+=1
            if row+col==n-1:
                if 'diag2' not in self.diag[k]:
                    self.diag[k]['diag2']=1
                else:
                    self.diag[k]['diag2']+=1
            
            if (row in self.record[k][0] and self.record[k][0][row]==n) or \
            (col in self.record[k][1] and self.record[k][1][col]==n):
                return player
                
            if (row==col and self.diag[k]['diag1']==n): return player
            
            if (row+col==n-1 and self.diag[k]['diag2']==n): return player
               
            return 0
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.