LeetCode Entry
1631. Path With Minimum Effort
Minimum absolute difference in path top-left to right-bottom
1631. Path With Minimum Effort medium blog post substack
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/341
Problem TLDR
Minimum absolute difference in path top-left to right-bottom
Intuition
To find an optimal path using some condition, we can use A* algorithm:
- add node to
PriorityQueue - choose the “optimal” one
- calculate a new heuristic for siblings and add to
PQ
Approach
- use directions sequence for more clean code
Complexity
-
Time complexity: \(O(nmlog(nm))\)
-
Space complexity: \(O(nm)\)
Code
val dirs = sequenceOf(1 to 0, 0 to 1, 0 to -1, -1 to 0)
fun minimumEffortPath(heights: Array<IntArray>): Int {
val pq = PriorityQueue<Pair<Pair<Int, Int>, Int>>(compareBy { it.second })
pq.add(0 to 0 to 0)
val visited = HashSet<Pair<Int, Int>>()
while (pq.isNotEmpty()) {
val (xy, diff) = pq.poll()
if (!visited.add(xy)) continue
val (x, y) = xy
if (x == heights[0].lastIndex && y == heights.lastIndex) return diff
dirs.map { (dx, dy) -> x + dx to y + dy }
.filter { (x1, y1) -> x1 in 0..<heights[0].size && y1 in 0..<heights.size }
.forEach { (x1, y1) -> pq.add(x1 to y1 to maxOf(diff, abs(heights[y][x] - heights[y1][x1]))) }
}
return 0
}