Solution: Path With Minimum Effort

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

---

Leetcode Problem #1631 (Medium): Path With Minimum Effort

---

Description:

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

---

Examples:

Example 1:
Input:	heights = [[1,2,2],[3,8,2],[5,3,5]]
Output:	2
Explanation:	The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells. This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
Visual:

Example 2:
Input:	heights = [[1,2,3],[3,8,4],[5,3,5]]
Output:	1
Explanation:	The route of [1,2,3,4,5] has a maximum absolute difference of 1 in consecutive cells, which is better than route [1,3,5,3,5].
Visual:

Example 3:
Input:	heights = [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
Output:	0
Explanation:	This route does not require any effort.
Visual:

---

Constraints:

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6

---

Idea:

If we think of the cells of height as if they were nodes on a graph, and think of the effort of traveling from a cell to its neighbor as the weight of the edge connecting those two nodes, then we can use a BFS approach to this solution.

Since the edges should be considered weighted, we can use a slightly modified Dijkstra's algorithm to find the path with minimum effort. As usual with Dijkstra's algorithm, we should implement a min-heap storage in which to keep our list of moves.

Dijkstra's algorithm essentially operates like a standard graph BFS approach, except that it prioritizes the next nodes by how quickly (or in this case with how little effort) they are reached. To do so, we just need to keep track of which nodes have already been visited (vis), and then use some method of prioritizing the next node based on which possible nodes can be reached with the least amount of cumulative effort from the starting point.

To be even more efficient, we can keep track of the best effort found for each node, and prevent worse routes from even being entered into our heap.

---

Implementation:

In javascript, we can use a Uint8Array for vis since it will only contain 0s or 1s. We can likewise use a Uint32Array for effort, since it will only contain integers from 1 to 1e6.

I've also included a version of the code with MinPriorityQueue(), which does the work of the min-heap for us, but it's far less efficient than the purpose-built min-heap.

---

Javascript Code w/ Min-Heap:

var minimumEffortPath = function(H) {
    let y = H.length, x = H[0].length, last = x*y-1,
        vis = new Uint8Array(last+1),
        effort = new Uint32Array(last+1).fill(1000001), 
        heap = [,], node = 0, path = 0, i, j, cell

    const heapify = (next, k, l) => {
        let newEff = Math.max(path, Math.abs(cell - H[k][l]))
        if (effort[next] <= newEff) return
        effort[next] = newEff
        let i = heap.length, par = i >> 1
        heap.push([next,newEff])
        while (par && heap[par][1] > heap[i][1]) {
            [heap[par], heap[i]] = [heap[i], heap[par]]
            i = par, par = i >> 1
        }
    }

    const extract = () => {
        let min = heap[1], left, right,
            i = 1, child = heap[3] && heap[3][1] < heap[2][1] ? 3 : 2
        heap[1] = heap.pop()
        while (heap[child] && heap[i][1] > heap[child][1]) {
            [heap[i], heap[child]] = [heap[child], heap[i]]
            i = child, left = i << 1, right = left + 1
            child = heap[right] && heap[right][1] < heap[left][1] ? right : left
        }
        return min
    }

     while (node !== last) {
        i = ~~(node / x), j = node % x, cell = H[i][j]
        if (i > 0 && !vis[node-x]) heapify(node-x, i-1, j)
        if (i < y-1 && !vis[node+x]) heapify(node+x, i+1, j)
        if (j > 0 && !vis[node-1]) heapify(node-1, i, j-1)
        if (j < x-1 && !vis[node+1]) heapify(node+1, i, j+1)
        vis[node] = 1
        while (vis[node]) [node,path] = extract()
    }
    return path
};

---

Javascript Code w/ MinPriorityQueue():

This code is less efficient, but easier to read. It uses the priorityqueue npm package that leetcode has enabled by default in their javascript implementation.

var minimumEffortPath = function(H) {
    let y = H.length, x = H[0].length,
        vis = new Uint8Array(x*y),
        effort = new Uint32Array(x*y).fill(1000001), 
        node = 0, path = 0, i, j, cell,
        pq = new MinPriorityQueue({priority: x => x[1]})

    const insert = (next, k, l) => {
        let newEff = Math.max(path, Math.abs(cell - H[k][l]))
        if (effort[next] <= newEff) return
        effort[next] = newEff
        pq.enqueue([next, effort[next]])
    }

    while (node !== x*y-1) {
        i = ~~(node / x), j = node % x, cell = H[i][j]
        if (i > 0 && !vis[node-x]) insert(node-x, i-1, j)
        if (i < y-1 && !vis[node+x]) insert(node+x, i+1, j)
        if (j > 0 && !vis[node-1]) insert(node-1, i, j-1)
        if (j < x-1 && !vis[node+1]) insert(node+1, i, j+1)
        vis[node] = 1
        while (vis[node]) [node, path] = pq.dequeue().element
    }
    return path
};