How to improve the speed of my python solution


  • 0
    Z

    This solution works well, but how to speed up it. It's just O(mn), but it still lower than other solutions

        ## put all edge connected to 1, put all O to X, put 1 to O.
        moves = [(0,1),(1,0),(-1,0),(0,-1)]
        
        if len(board)<1: return
    
        nrow = len(board)
        ncol = len(board[0])
        
        if nrow <3 or ncol < 3: return  ## if less than 3, no surrounded
        
        temp = []
        
        for i in 0, nrow-1:
            for j in xrange(ncol):
                if board[i][j] == 'O': 
                    board[i][j] = '1'   ##replace O by 1 on the edge
                    temp.append((i,j)) ##bfs, queue to store searched item
                    while temp != []:
                        (i1,j1) = temp.pop(0)  ## search from where I pop
                        for move in moves:  ## 1 step deep, check 4 directions in poped point
                            i2 = i1 + move[0]
                            j2 = j1 + move[1]
                            if i2 in range(nrow) and j2 in range(ncol) and board[i2][j2] == 'O':
                                board[i2][j2] = '1' 
                                temp.append((i2,j2))
                                
        for j in 0, ncol-1:
            for i in xrange(nrow):
                if board[i][j] == 'O': 
                    board[i][j] = '1'   ##replace O by 1 on the edge
                    temp.append((i,j)) ##bfs, queue to store searched item
                    i1 = i
                    j1 = j
                    while temp != []:
                        (i1,j1) = temp.pop(0)
                        for move in moves:
                            i2 =i1 + move[0]
                            j2 =j1 + move[1]
                            if i2 in range(nrow) and j2 in range(ncol) and board[i2][j2] == 'O':
                                board[i2][j2] = '1' 
                                temp.append((i2,j2))
                                
        for i in xrange(nrow):
            for j in xrange(ncol):
                if board[i][j] == 'O': board[i][j] = 'X'
                if board[i][j] == '1': board[i][j] = 'O'

Log in to reply
 

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