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


  • 0

    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?


  • 0
    B

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


Log in to reply
 

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