Can some one help me figure out why this solution is TLE?


  • 0
    Z

    Using union_find, compressed path, balanced tree. I just can figure out which part is not efficient enough or can be upgrade>?

    class Uf(object):
        def __init__(self):
            self.num_island = 0
            self.grid = {}
            self.size = {}
        def find(self,pos):
            if pos not in self.grid:
                self.grid[pos] = pos
                self.size[pos] = 1
                
            while pos!=self.grid[pos]:
                self.grid[pos] = self.grid[self.grid[pos]]
                pos = self.grid[pos]
            return pos
        def union(self,pos1,pos2):
            p1 = self.find(pos1)
            p2 = self.find(pos2)
            if p1!=p2:
                if self.size[p1]>self.size[p2]:
                    self.grid[p2] = p1
                    self.size[p1]+=1
                else:
                    self.grid[p1] = p2
                    self.size[p2]+=1
                self.num_island -=1
            
    class Solution(object):
        def numIslands2(self, m, n, positions):
            uf = Uf()
            discovered = []
            actions = [(1,0),(-1,0),(0,1),(0,-1)]
            res = []
            for position in map(tuple,positions):
                uf.num_island+=1
                for action in actions:
                    unknown = (position[0]+action[0],position[1]+action[1])
                    if unknown in discovered:
                        uf.union(position,unknown)
                discovered.append(position)
                res.append(uf.num_island)
            return res
    

Log in to reply
 

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