Given an R × C grid heights, travel from the top-left (0,0) to the bottom-right (R-1, C-1) moving 4-directionally. A route's effort is the maximum absolute height difference between consecutive cells. Return the minimum effort. (This is the same minimax path as minimum effort, approached here with union-find.)
Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2 The two corners connect once weight-2 edges are added.
Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1 A route exists whose largest step is 1.
- 1 <= R, C <= 100 - 1 <= heights[r][c] <= 10^6
Viewing the grid as a weighted graph — each adjacency is an edge weighted by the two cells' height difference — the answer is the bottleneck on the best route: the smallest value t such that using only edges of weight ≤ t connects start to end. That's a Kruskal-style union-find:
Sort all edges by weight ascending and add them one at a time, unioning their cells. After each addition, check whether the source and destination are now connected — the weight of the edge that first connects them is the minimum effort. Intuitively, you're building the components with the cheapest edges first, and the moment the two corners join, the largest edge you were forced to use is the answer. O(RC · α · log(RC)) (dominated by the sort).
The alternative is Dijkstra with a running max (from the sibling problem): settle cells by minimum effort, relaxing with max(effort, |Δ|).
“Same as minimum effort?”
Yes — a minimax path; here solved with union-find.
“Movement?”
4-directional.
I sort all cell-to-cell edges by height difference and union them in order.
The weight of the edge that first connects the two corners is the minimum effort.
Worked example — heights = [[1,2,2],[3,8,2],[5,3,5]]
add edges by |Δ|: many of weight 0,1,2 ... the corners connect once weight-2 edges are included -> answer 2
The largest edge on the best minimax route.
Corners connect at the answer's weight.
Two lenses on one minimax path.
| Union-Find (Kruskal) | Dijkstra (max relax) | |
|---|---|---|
| Idea | add edges by weight until corners connect | settle cells by minimum effort |
| Time | O(RC · log(RC)) | O(RC · log(RC)) |
| Answer | connecting edge's weight | effort at destination |
Both return the same minimum effort. Full code is in the Approaches selector below.
Key takeaway
Sort cell-adjacency edges by height difference and union them; the weight of the edge that first connects the two corners is the minimum effort. Or Dijkstra with a running max. O(RC·log(RC)).
sort edges by |Δ|; union in order; when src and dst connect, return that weight
