Python O(m*n log(m*n)) floodfill solution without heap


  • 0
    M

    I figure it out myself, yet in discussion I find that everyone is using heap.

    My idea is that we maintain the info on every level and update it dynamically over height. At first we are at bottom, then gradually goes up. I think outer area are filled with sea water, and we only need the fresh water count.(May air instead of sea water is better) The blockMap is used for the level info. Since each point can only transform from wall to fresh water then sea water once, the speed is actually fast.

    The major performance cost is at sort, and everything else is easy to understand. Welcome discussion and further improvement!

    class Solution(object):
        
        def floodfill(self, blockMap, position, nr_fresh_water, h, w):
            # fill sea water to fresh water
            i,j = position
            if i < 0 or i >= w or j < 0 or j >= h: return
            if not blockMap[j][i]==-1: return
            active = set()
            active.add((i,j))
            while len(active)>0:
                for (p,q) in active: break
                active.remove((p,q))
                if blockMap[q][p] == 0: #fill it with sea water 
                    nr_fresh_water[0]-=1
                    blockMap[q][p] = -1
                for (np,nq) in [(p-1,q),(p+1,q),(p,q-1),(p,q+1)]:
                    if np < 0 or np >= w or nq < 0 or nq >=h: continue
                    if blockMap[nq][np] == 0:
                        nr_fresh_water[0]-=1
                        blockMap[nq][np] = -1
                        active.add((np,nq))
        
        def trapRainWater(self, heightMap):
            """
            :type heightMap: List[List[int]]
            :rtype: int
            """
            # sort use height, O((m*n)log(m*n)) : most time consuming!
            # afterwards, run m*n times. Each point at most change twice => O(m*n) runtime.
            h = len(heightMap)
            if h==0: return 0
            w = len(heightMap[0])
            if w==0: return 0
            
            heightOrders = []
            for j in range(h):
                for i in range(w):
                    heightOrders.append((heightMap[j][i],(i,j)))
            heightOrders.sort()
            #/notation: "x"/1: wall; "o"/0: fresh water; "."/-1: sea water;
            blockMap = [[1 for _ in range(w)] for _ in range(h)]
            total_water=0
            nr_fresh_water=[0] # for mutable use
            last_height = heightOrders[0][0] # trick to assure at first we do nothing
            for height, (i,j) in heightOrders:
                # calculate waters stored since last 
                total_water +=nr_fresh_water[0] * (height - last_height)
                #update nr_fresh_water & h
                if i==0 or i==w-1 or j==0 or j==h-1:
                    blockMap[j][i]=-1
                    self.floodfill(blockMap, (i,j), nr_fresh_water, h, w)
                else:
                    blockMap[j][i]=0
                    nr_fresh_water[0]+=1
                    for (p,q) in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:
                        if blockMap[q][p] == -1: 
                            self.floodfill(blockMap,(p,q), nr_fresh_water, h, w)
                last_height = height
            return total_water
    

Log in to reply
 

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