How to Answer: Find the path with minimum effort.
Advice and answer examples written specifically for a JavaScript Advanced Level Binary Search job interview.
2. Find the path with minimum effort.
This question focuses on the developer's knowledge of JavaScript binary search and loops.
You are given 2-D matrix heights for size n x m. A hiker is at the top-left cell (0, 0) (cells are 0-indexed). Her target is to reach the bottom-right of the cell (n - 1, m - 1). She can move either up, down, left or right from a cell. Your task is to find minimum effort to reach the destination cell. The effort of a path to the destination is the maximum absolute difference of their heights between two consecutive cells of the path.
/*Example*/
Given matrix-
[[1, 2, 2],
[3, 8, 2],
[5, 3, 5]]
expected output = 2
explanation:- The path 1 -> 2 -> 2 -> 2 -> 5 has an effort of 3.
The path 1 -> 3 -> 5 -> 3 -> 5 has an effort of 2.Definitions:
â— maximum absolute difference for the path 3 -> 4 -> 2 is maxOf(4 - 3, 4 - 2) = maxOf(1, 2) = 2
â— maximum absolute difference for the path 1 -> 3 -> 5 -> 3 -> 5 is maxOf(2, 2, 2, 2) = 2
â— maximum absolute difference for the path 1 -> 2 -> 2 -> 2 -> 5 is maxOf(1, 0, 0, 3) = 3
Constraints:
â— 1 <= n, m <= 100
â— 1 <= heights[i][j] <= 106
Solution:
We can use binary search to solve this problem. If we carefully observe, below the minimum effort, there is no way to reach the destination. Let’s say the minimum effort required is min. If we are asked:
â— Can we reach our destination with an effort of less than min? The answer is definitely no.
â— Can we reach our destination with an effort greater than or equal to min? The answer is definitely yes.
0 1 … min - 1 min min + 1 … max-possible
F F F F T T T T
We can do a binary search from 0 to max-possible. The value of max-possible will be the maximum height of a cell in the given matrix. We have a function that can reach answers the two questions above. It will return true if the effort passed is greater than or equal to min, false otherwise.
In the 'canReach' function, we will do DFS to at least one path using which we can reach the destination with given effort. We will maintain a 2-D array visited to check which nodes we have visited. We will start from the cell (0, 0). We will explore all the neighboring cells of the current cell viz. up, down, left, and right. While exploring a neighbouring cell, we will check if it is visited earlier. If it is not visited, we will check if the absolute height difference between the current cell and the neighboring cell is permitted using an impermissible function (i.e. check if less than given effort). If it is not permitted, we will not do DFS on this cell, because any path will not be possible through this cell. If it is permitted, we will do DFS on this cell and will explore its neighboring cells. If we have reached the destination cell, we simply return true, because there was at least one path using which we could reach the destination with given effort.
/**
* @param {number[][]} heights
* @return {number}
*/
function findMinimumEffort(heights) {
let left = 0
let right = 0
for (const row of heights) {
right = Math.max(right, Math.max(...row))
}
while(left < right) {
let mid = (left + right) / 2
mid = Math.floor(mid)
if (canReach(mid, heights)) {
right = mid
} else {
left = mid + 1
}
}
return left
}
function canReach(effort, heights) {
const n = heights.length
const m = heights[0].length
let isPossible = false
// initialize visited matrix of size n x m will all false
const visited = new Array(n)
for (let i = 0; i < n; i++) {
visited[i] = new Array(m).fill(false)
}
// check if the consecutive cells effort less than
// or equal to passed effort
function isPermissible(i1, j1, i2, j2) {
const h1 = heights[i1][j1]
const h2 = heights[i2][j2]
return Math.abs(h1 - h2) <= effort
}
function dfs(i, j) {
// we have reached the destination cell
// return true
if (i === n - 1 && j === m - 1) {
return true
}
visited[i][j] = true
const up = i - 1
const down = i + 1
const left = j - 1
const right = j + 1
// check if we can visit the up cell
if (
up >= 0 &&
!visited[up][j] &&
isPermissible(i, j, up, j)
) {
isPossible = isPossible || dfs(up, j)
}
// check if we can visit the down cell
if (
down < n &&
!visited[down][j] &&
isPermissible(i, j, down, j)
) {
isPossible = isPossible || dfs(down, j)
}
// check if we can visit the left cell
if (
left >= 0 &&
!visited[i][left] &&
isPermissible(i, j, i, left)
) {
isPossible = isPossible || dfs(i, left)
}
// check if we can visit the right cell
if (
right < m &&
!visited[i][right] &&
isPermissible(i, j, i, right)
) {
isPossible = isPossible || dfs(i, right)
}
return isPossible
}
return dfs(0, 0)
}Time complexity- O(n * m * log(106))
Space complexity- O(n * m)
Written by Jennie Taylor on May 22nd, 2021