Understanding the Problem

At first, this looks like a standard shortest-path problem on a grid. But there's a twist: the "cost" of a path isn't the sum of edge weights, it's the maximum edge weight along the entire path. That changes things significantly.

Think of it this way. You're hiking across a terrain grid, and each cell has a height. Moving between adjacent cells costs you effort equal to the absolute height difference. The total effort of a route is the single worst step you had to take, not the cumulative effort. So you want to find a path from the top-left to the bottom-right that minimizes this worst-case step.

This "minimize the maximum" framing is a strong signal. It tells us we're not looking for the shortest weighted path (Dijkstra with sum), but rather an optimization over a bottleneck metric. Two classic approaches work here: modified Dijkstra's algorithm (where we track max edge weight instead of cumulative cost) and binary search on the answer combined with BFS/DFS to validate.

Key Constraints:

1 <= rows, columns <= 100 → The grid has at most 10,000 cells. This means O(V * E) or even O(V^2) approaches are feasible. Dijkstra with a heap runs in O(V log V) here, which is very comfortable.
1 <= heights[i][j] <= 10^6 → Heights range up to a million, so the maximum possible effort is 999,999. This gives us a clear binary search range of [0, 999999].

Approach 1: Binary Search + BFS

Intuition

Here's a clean way to think about this problem: if someone told you "your maximum allowed effort is k," could you check whether you can reach the bottom-right corner? Absolutely. Just run BFS (or DFS) from the top-left, but only move to adjacent cells where the height difference is at most k. If BFS reaches the destination, the effort k is achievable.

So the question becomes: what's the smallest k that works? That's a classic binary search on the answer. The search space is [0, 999999] (since heights go up to 10^6). For each mid value, we check reachability. If reachable, we try a smaller effort. If not, we need a larger effort.

This approach is elegant because it decomposes the problem into two simpler subproblems: binary search for the threshold and BFS for reachability.

Algorithm

Set low = 0 and high = 10^6 (the maximum possible height difference).
While low < high:

Compute mid = (low + high) / 2.
Run BFS from (0, 0). Only move to adjacent cells where |heights[curr] - heights[neighbor]| <= mid.
If BFS reaches (rows-1, columns-1), set high = mid (this effort is achievable, try smaller).
Otherwise, set low = mid + 1 (need more effort).

Return low.

Example Walkthrough

1Binary search: low=0, high=1000000. Try mid=2

1/6

Code

Complexity Analysis

Time Complexity: O(m n log(maxHeight)). The binary search runs for ~20 iterations. Each iteration runs a BFS that visits all m * n cells.
Space Complexity: O(m n). The visited array and BFS queue each use O(m n) space.

This approach works but runs a full BFS for each binary search iteration. What if we used the actual height differences directly to find the optimal path without the binary search wrapper?

Approach 2: Modified Dijkstra's Algorithm (Optimal)

Intuition

In standard Dijkstra's, we track the cumulative distance to each node and always process the node with the smallest total distance. Here, we adapt the idea: instead of summing edge weights, we track the maximum edge weight along the path to each cell.

For each cell, effort[r][c] stores the minimum possible effort (i.e., the smallest "maximum height difference") to reach that cell from (0, 0). When we explore a neighbor, the new effort is max(effort[r][c], |heights[r][c] - heights[nr][nc]|). If this new effort is smaller than the currently recorded effort for the neighbor, we update it and add the neighbor to the priority queue.

Why does this work?

The min-heap guarantees we always process the cell reachable with the smallest maximum effort first. Once a cell is popped from the heap, its effort value is optimal, just like distances in standard Dijkstra's. The max operation preserves the greedy property: extending a path through a low-effort cell can only maintain or increase the effort, never decrease it. So once we've found the best effort to a cell, no later discovery can beat it.

Algorithm

Create a 2D array effort initialized to infinity, with effort[0][0] = 0.
Push (0, 0, 0) into a min-heap (effort, row, col).
While the heap is not empty:

Pop the cell (e, r, c) with the smallest effort.
If (r, c) is the destination, return e.
If e > effort[r][c], skip (we've already found a better path).
For each neighbor (nr, nc):

Compute newEffort = max(e, |heights[r][c] - heights[nr][nc]|).
If newEffort < effort[nr][nc], update effort[nr][nc] = newEffort and push to the heap.

Return effort[rows-1][cols-1].

Example Walkthrough

1Initialize: effort[0][0]=0, all others INF. Heap: [(0,0,0)]

INF

1/8

Code

Complexity Analysis

Time Complexity: O(m n log(m n)). Each cell can be pushed to the heap at most 4 times. With m n cells, each heap operation takes O(log(m * n)).
Space Complexity: O(m n). The effort array and heap both use O(m n) space.

Path With Minimum Effort

Understanding the Problem

Key Constraints:

Approach 1: Binary Search + BFS

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Modified Dijkstra's Algorithm (Optimal)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium