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-=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-=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) 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= # for mutable use last_height = heightOrders # trick to assure at first we do nothing for height, (i,j) in heightOrders: # calculate waters stored since last total_water +=nr_fresh_water * (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+=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