1631 Path With Minimum Effort

1631 Path With Minimum Effort#

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#

Example 1:

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.

Example 2:

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

Example 3:

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.

Constraint#

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 106

Analysis#

Single pair shortest weighted path problem can be solved using Dijkstra’s algorithm and DFS

Solution#

def minEffort(heights):

    neighbors = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    m, n = len(heights), len(heights[0])
    
    distances = [[float('inf')] * n for _ in range(m)]
    distances[0][0] = 0

    queue = [(0, (0,0))]

    while queue:
        distance, (i, j) = queue.pop()
        for di, dj in neighbors:
            ni, nj = i + di, j + dj
            if 0 <= ni < m and 0 <= nj < n:
                distance_ni_nj = max(distances[i][j], heights[ni][nj] - heights[i][j])
                if distance_ni_nj < distances[ni][nj]:
                    distances[ni][nj] = distance_ni_nj
                    queue.append((distance_ni_nj, (ni, nj)))
    return distances[-1][-1]

# test 
heights = [[1,2,2],[3,8,2],[5,3,5]]
print(minEffort(heights))

heights = [[1,2,3],[3,8,4],[5,3,5]]
print(minEffort(heights))

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]]
print(minEffort(heights))

# 6
heights = [[10,8],[10,8],[1,2],[10,3],[1,3],[6,3],[5,2]]
print(minEffort(heights))

2
1
0
1
Contents