Path With Minimum Effort Python Solution

lcpy gen -n 1631   # by problem number
lcpy gen -s path_with_minimum_effort   # by problem name

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.

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].

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.

import heapq


class Solution:
    # Time: O(rows * cols * log(rows * cols))
    # Space: O(rows * cols)
    def minimum_effort_path(self, heights: list[list[int]]) -> int:
        rows = len(heights)
        cols = len(heights[0])

        efforts = [[float("inf")] * cols for _ in range(rows)]
        efforts[0][0] = 0

        heap: list[tuple[int, int, int]] = [(0, 0, 0)]

        while heap:
            effort, row, col = heapq.heappop(heap)

            if row == rows - 1 and col == cols - 1:
                return effort

            if effort > efforts[row][col]:
                continue

            for drow, dcol in ((-1, 0), (1, 0), (0, -1), (0, 1)):
                new_row, new_col = row + drow, col + dcol
                if 0 <= new_row < rows and 0 <= new_col < cols:
                    new_effort = max(effort, abs(heights[row][col] - heights[new_row][new_col]))
                    if new_effort < efforts[new_row][new_col]:
                        efforts[new_row][new_col] = new_effort
                        heapq.heappush(heap, (new_effort, new_row, new_col))

        return 0