Graph Breadth First Search Depth First Search Shortest Path Minimum Spanning Tree
Proficient Level

Implement the minimumEffortPathGrid method that returns the minimum effort required to travel across a height grid.

You are given a matrix of heights. You start at the top-left cell and need to reach the bottom-right cell. You may move up, down, left, or right.

The effort of a path is the maximum absolute height difference between two adjacent cells on that path. Return the minimum possible effort among all valid paths.

Example 1
Input:
heights (int[][]) = [[1,2,2],[3,8,2],[5,3,5]]
rows (int) = 3
cols (int) = 3
Return:
(int) 2
Example 2
Input:
heights (int[][]) = [[1,2,3],[3,8,4],[5,3,5]]
rows (int) = 3
cols (int) = 3
Return:
(int) 1
Example 3
Input:
heights (int[][]) = [[1]]
rows (int) = 1
cols (int) = 1
Return:
(int) 0

This is a shortest path problem where the path cost is controlled by the maximum edge difference, not the sum of edge weights.

Use Dijkstra's algorithm with effort as the distance value. When moving to a neighbor, the new effort is the maximum of the current effort and the height difference for that move. If this effort is smaller than the best known effort for the neighbor, update it.

The first time the destination is removed from the min heap, its effort is the answer.

Pseudocode:

function minimumEffortPathGrid(heights, rows, cols):
    effort = matrix filled with infinity
    effort[0][0] = 0
    heap = [(0, 0, 0)]
    while heap is not empty:
        currentEffort, r, c = heap.popMin()
        if r == rows - 1 and c == cols - 1:
            return currentEffort
        for each valid neighbor:
            diff = absolute height difference
            nextEffort = max(currentEffort, diff)
            if nextEffort < effort[neighbor]:
                effort[neighbor] = nextEffort
                push neighbor into heap
    return 0
Run your code to see the result.