Path With Minimum Effort Python Solution

Tested Python solution for LeetCode 1631 with 15 pytest cases. Generate a practice environment with lcpy.

LeetCode 1631, Medium. Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union Find, Heap (Priority Queue), Matrix. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 15 parametrized pytest cases, and a playground notebook:

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

​

Problem

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

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.

​

Constraints

• rows == heights.length
• columns == heights[i].length
• 1 <= rows, columns <= 100
• 1 <= heights[i][j] <= 10^6

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

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

​

Complexity

Time	Space
O(rows * cols * log(rows * cols))	O(rows * cols)

​

Tags

NeetCode 250, NeetCode All.