Path with Minimum Effort

Problem

Given a rows by cols grid of heights, find the minimum effort to travel from the top-left to the bottom-right cell moving up, down, left, or right.

The effort of a path is the maximum absolute height difference between consecutive cells. Return the minimum possible effort; each cell can be visited as needed.

Hint

Dijkstra where the path cost is the maximum edge weight seen so far.

Test cases

case 1

in: [[[1,2,2],[3,8,2],[5,3,5]]]

expected: 2

case 2

in: [[[1,2,3],[3,8,4],[5,3,5]]]

expected: 1

case 3

in: [[[1,1,1],[1,1,1]]]

expected: 0

case 4

in: [[[1,2],[3,4]]]

expected: 2

Starter codePython

import heapq
def minimum_effort(heights):
    # Your code here
    pass

4 test cases · run your code against them in the editor