#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/dijkstra-s-algorithm/minimum-effort-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/dijkstra-s-algorithm/minimum-effort-implementation

Repovive

LeetCode 1631 Path with Minimum Effort - Implementation - Dijkstra's Algorithm | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

LeetCode 1631 Path with Minimum Effort - Implementation

Code solution

Here is the solution:

function minimumEffortPath(heights):
    rows = heights.rows
    cols = heights.cols
    dist = 2D array of size rows x cols, all infinity
    dist[0][0] = 0
    pq = min-heap with (0, 0, 0)

    while pq is not empty:
        (effort, r, c) = pq.pop()
        if r == rows - 1 and c == cols - 1:
            return effort
        if effort > dist[r][c]:
            continue
        for (nr, nc) in neighbors of (r, c):
            newEffort = max(effort, abs(heights[r][c] - heights[nr][nc]))
            if newEffort < dist[nr][nc]:
                dist[nr][nc] = newEffort
                pq.push((newEffort, nr, nc))

    return dist[rows - 1][cols - 1]

This runs in $O(rows \times cols \times \log(rows \times cols))$ time and uses $O(rows \times cols)$ space.