1631.path-with-minimum-effort.md

1631. Path With Minimum Effort

Binary Search

Binary search is for finding a value in "sorted array", but there is no such sorted array in this problem, either the grid or paths is unsorted. The "sorted array" is hidden in the range of possible answer.

• Let's say the maximum absolute difference range from 0 to 100.
• The answer must be in that range [0..100].
• This range [0..100] is the sorted array that we can apply the binary search.

We use effort to represent the maximum absolute difference in heights between two consecutive cells of the route. (Aligned the problem description)

Let's take a look how do we apply binary search on answer in this problem:

1. Search range: Given a minimum and maximum in the grid, the possible maximum effort = abs(max - min), the possible minimum effort is 0 (same height).
2. Monotonicity: If there exists a path which effort is k, then we can definitely find a path which effort is k + 1 or larger k. (It's constraints)

We guess an effort k and check if there exists a path from source to destination that under that effort constraints. If we can reach the destination (via DFS or BFS), we try to find a smaller threshold. Otherwise, we try to find a larger threshold.

可以上下左右走，沒有無後效性，無法用動態規劃做。無腦搜索的話因為沒有什麼障礙或限制，效率非常差。可以二分猜答案;也可以貪心找 (Dijkstra's)，先找出所有的落差值，從最小的值開始串，看能不能串出從左上到右下的路徑。

fun minimumEffortPath(heights: Array<IntArray>): Int {
    val m = heights.size
    val n = heights[0].size
    var left = 0 // Minimum effort is 0, not 1, the height difference can be 0. (same height)
    var right = abs(heights.maxOf { it.max() } - heights.minOf { it.min() })
    while (left <= right) {
        val middle = left + (right - left) / 2
        val canReach = dfs(heights, 0, 0, Array(m) { BooleanArray(n) }, middle)
        if (canReach) {
            right = middle - 1
        } else {
            left = middle + 1
        }
    }
    return left
}

// We traverse the grid using DFS and check if we can reach the destination with the threshold.
private fun dfs(
    heights: Array<IntArray>,
    x: Int,
    y: Int,
    visited: Array<BooleanArray>,
    threshold: Int
): Boolean {
    val m = heights.size
    val n = heights[0].size
    if (x == m - 1 && y == n - 1) return true
    visited[x][y] = true

    var result = false
    for (d in directions) {
        val newX = x + d[0]
        val newY = y + d[1]
        if (newX !in 0 until m || newY !in 0 until n) continue
        if (visited[newX][newY] == true) continue
        val diff = abs(heights[x][y] - heights[newX][newY])
        if (diff <= threshold) {
            result = dfs(heights, newX, newY, visited, threshold) || result
        }
    }
    return result
}

• Time Complexity: O(m * n * log(R)) where R is the maximum possible value range.
• Space Complexity: O(m * n).

Dijkstra

Explore the path greedily, always choose the path with the minimum effort.

fun minimumEffortPath(heights: Array<IntArray>): Int {
    val m = heights.size
    val n = heights[0].size
    val minHeap = PriorityQueue<Node>(compareBy { it.effort })
    val efforts = Array(m) { IntArray(n) { Int.MAX_VALUE } }
    efforts[0][0] = 0
    minHeap.add(Node(0, 0, 0))
    var answer = Int.MIN_VALUE
    while (minHeap.isNotEmpty()) {
        val (x, y, effort) = minHeap.poll()
        if (effort > efforts[x][y]) continue
        answer = maxOf(answer, effort)
        if (x == m - 1 && y == n - 1) break
        for (d in directions) {
            val newX = x + d[0]
            val newY = y + d[1]
            if (newX !in 0 until m || newY !in 0 until n) continue
            val newEffort = abs(heights[x][y] - heights[newX][newY])
            if (efforts[newX][newY] > newEffort) {
                efforts[newX][newY] = newEffort
                minHeap.add(Node(newX, newY, efforts[newX][newY]))
            }
        }
    }
    return answer
}