Solution: Path With Minimum Effort
Tags: algorithms, javascript, leetcode
Published: 2021-02-03 19:57:00

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/path-with-minimum-effort/discuss/1037266/Javascript-or-Dijkstra%27s-and-Min-Heap-or-beats-100-100).*

---

####[Leetcode Problem #1631 (*Medium*): Path With Minimum Effort](https://leetcode.com/problems/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<br>absolute difference of 2 in consecutive cells.<br>This is better than the route of [1,2,2,2,5],<br>where the maximum absolute difference is 3.
*Visual:*|![Example 1 Visual](https://assets.leetcode.com/uploads/2020/10/04/ex1.png)|

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<br>absolute difference of 1 in consecutive cells,<br>which is better than route [1,3,5,3,5].
*Visual:*|![Example 2 Visual](https://assets.leetcode.com/uploads/2020/10/04/ex2.png)|

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:*|![Example 3 Visual](https://assets.leetcode.com/uploads/2020/10/04/ex3.png)|
 
---

***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 **0**s or **1**s. 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:***
```javascript
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.
```javascript
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
};
```