Graph Theory37 sections · 1633 units
Open in Course

LeetCode 1631 Path with Minimum Effort - Problem Statement

Minimax path problem

You have a 2D2D grid of heights. You walk from top-left to bottom-right. Each step to an adjacent cell has an effort equal to the absolute difference in heights. The effort of a path is the maximum effort of any single step in that path.

Find the path with the minimum maximum effort. This is not a shortest path by total cost. It's a shortest path by the maximum edge weight along the path. Dijkstra can solve this, but you need to redefine what "cost" means.