# What's the complexity of the winner's solution?

• I'm really glad I didn't participate in this context because I never stood a chance. I blazed through the first 3 problems like I never did, and then I spent almost a day trying to figure out the last one. Had the right idea, but couldn't implement it right. So I gave up and went to the scoreboard to study the winner's solution.

Here is my implementation of the same idea, although I modified a few things in the algorithm:

``````if len(heightMap) < 3 or len(heightMap[0]) < 3:
return 0
m, n = len(heightMap), len(heightMap[0])
queue, level = set(), [[float('+inf')] * n for __ in xrange(m)]
for i in xrange(m):
queue |= {(i, 0), (i, n - 1)}
level[i][0] = heightMap[i][0]
level[i][n - 1] = heightMap[i][n - 1]
for j in xrange(1, n - 1):
queue |= {(0, j), (m - 1, j)}
level[0][j] = heightMap[0][j]
level[m - 1][j] = heightMap[m - 1][j]

def within(i, j):
return 0 <= i < m and 0 <= j < n

nearby = ((0, -1), (0, +1), (-1, 0), (+1, 0))
next_queue = set()
while queue:
for i, j in queue:
for di, dj in nearby:
if within(i + di, j + dj):
new_level = max(level[i][j], heightMap[i + di][j + dj])
if new_level < level[i + di][j + dj]:
level[i + di][j + dj] = new_level
next_queue.add((i + di, j + dj))
queue = next_queue
next_queue = set()
return sum(level[i][j] - heightMap[i][j]
for i, j in product(xrange(m), xrange(n)))
``````

Never mind the first boring part where we just set up the boundary (is there a more concise way to do it?). The fun begins afterwards. Unlike most solutions posted here, this one doesn't use a queue. The winner used a regular list here, I replaced it with a set in order to avoid adding duplicate coordinates to the queue, so I switch sets instead. The other thing I modified was that the winner calculated the next level as `max(min(level[i][j], level[i + di][j + dj]), heightMap[i + di][j + dj])`. I skipped the `min` part because I check that `new_level` is less than the current level at `(i + di, j + dj)` anyway (the winner checked for `!=` there).

Note that unlike most solution posted, there is no heap. Not only that, there is no `visited` matrix or set! So it is quite possible that the same spot is reached via multiple paths. But only a better path leads to actual re-exploration of it. It runs pretty fast: 645 ms. But I can't figure out what its complexity is. It feels like discovering a new path could lead to a whole cascade of re-evaluation of nearby elements. Why is it so fast then?

• You can refer to SPFA algorithm, which is another algorithm for single source shortest path. https://en.wikipedia.org/wiki/Shortest_Path_Faster_Algorithm

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