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

• 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()
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

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