Path With Minimum Effort

public class Solution {
    public Integer minimumEffortPath(int[][] heights) {
        // Your code goes here
    }
}

Explanation

Understanding the Problem

The key twist here is what we're optimizing for. We're not finding the shortest path (fewest steps) or the path with the smallest total elevation change. Instead, we want to minimize the single hardest step along the entire path.

Think of it like planning a hike: you might choose a longer, winding trail if it means avoiding one extremely steep section. The steepest part determines how difficult the hike feels, not the total distance or cumulative elevation gain.

Notice something interesting, both paths visit the same number of cells, but Path B has much lower effort. This is because we're optimizing for the maximum step, not the sum of steps. A single "cliff" can ruin an otherwise reasonable path.

Brute Force: Try Every Path

The most straightforward approach: use DFS to explore every possible path from (0,0) to (m-1, n-1), track the maximum step along each path, and return the minimum across all paths.

public int minimumEffortPath(int[][] heights) {
    int rows = heights.length;
    int cols = heights[0].length;
    int[] result = {Integer.MAX_VALUE};
    boolean[][] visited = new boolean[rows][cols];
    visited[0][0] = true;
    dfs(heights, 0, 0, 0, visited, result);
    return result[0];
}
private void dfs(int[][] heights, int r, int c, int maxEffort,
                 boolean[][] visited, int[] result) {
    int rows = heights.length, cols = heights[0].length;
    if (r == rows - 1 && c == cols - 1) {
        result[0] = Math.min(result[0], maxEffort);
        return;
    }
    int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    for (int[] d : dirs) {
        int nr = r + d[0], nc = c + d[1];
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && !visited[nr][nc]) {
            int diff = Math.abs(heights[nr][nc] - heights[r][c]);
            visited[nr][nc] = true;
            dfs(heights, nr, nc, Math.max(maxEffort, diff), visited, result);
            visited[nr][nc] = false;
        }
    }
}

This works, but the number of possible paths through a grid grows exponentially. For a 3x3 grid it's fine, but for 100x100? We'd be waiting until the heat death of the universe. The time complexity is O(4^(m×n)) in the worst case, since at each cell we can branch in up to 4 directions.

We need something smarter.

A Clever Shortcut: Binary Search + BFS

Here's an interesting observation: if we could walk a path where no single step exceeds some threshold t, then we could definitely walk any path where the threshold is t+1 or higher. This monotonic property means we can binary search on the answer.

For a given threshold t, we just need to check: "Is there any path from start to end where every step has height difference ≤ t?" That's a simple BFS/DFS reachability check where we only traverse edges with weight ≤ t.

This is way better than brute force! But we're running a full BFS for each binary search step, and the search range depends on the maximum height value (up to 10^6). Can we do even better?

Recognizing the Graph Pattern

Step back and think about what we actually have here:

• Each cell is a node
• Moving between adjacent cells is an edge with weight = height difference
• We want to find the path from start to end that minimizes the maximum edge weight

This is a shortest path problem on a graph, but with a twist. In our previous shortest path problems like Network Delay Time and Cheapest Flights, we minimized the sum of edge weights. Here, we're minimizing the maximum edge weight along the path.

This is called a minimax path problem: find the path that minimizes the maximum edge weight.

Why Modified Dijkstra Works

Can we adapt Dijkstra's algorithm for this? In standard Dijkstra, we compute distances as the sum of edge weights. Here, we'd compute them as the max of edge weights. Does the greedy property still hold?

Think about it: if we've reached cell X with effort E (the max step along the path so far), any path that goes through X will have effort ≥ E, because max can only stay the same or increase as we add more edges. So when we pop a cell from the priority queue, we know no future path to that cell can do better.

That's the same greedy guarantee that makes standard Dijkstra work. The only thing that changes is the relaxation rule:

The algorithm is almost identical to standard Dijkstra:

1. State: (effort, row, col) where effort is the max step along the path so far
2. Priority Queue: Pop the cell with minimum effort first
3. Relaxation: For each neighbor with edge weight w, compute new_effort = max(current_effort, w). If it improves the best known effort to that neighbor, update and push
4. Early exit: The first time we pop the destination cell, that's our answer

Walkthrough

Let's trace through a 3×3 grid: [[1,10,2], [2,3,3], [3,2,1]]

Step 1: Initialize

Start at (0,0) with effort 0. Distance matrix initialized to ∞ except dist[0][0] = 0.

Step 2: Process (0,0), update neighbors

Pop (effort=0, row=0, col=0) from the queue. We look at neighbors (0,1) and (1,0):

• To (0,1): The height difference is |10-1| = 9. Since max(0, 9) = 9 < ∞, we update dist[0][1] = 9
• To (1,0): The height difference is |2-1| = 1. Since max(0, 1) = 1 < ∞, we update dist[1][0] = 1

Notice the queue is sorted by effort: (1, 1, 0) comes before (9, 0, 1). The greedy approach will explore the low-effort path first.

Step 3: Process (1,0), continue exploring

Pop (effort=1, row=1, col=0). Check neighbors:

• To (0,0): Already processed, skip
• To (1,1): Height diff |3-2| = 1. new_effort = max(1, 1) = 1 < ∞, update dist[1][1] = 1
• To (2,0): Height diff |3-2| = 1. new_effort = max(1, 1) = 1 < ∞, update dist[2][0] = 1

Step 4-6: Reach destination

The algorithm continues, always picking the lowest-effort cell. It reaches (2,2) via the path that goes down and right, avoiding the "cliff" at cell (0,1).

The final answer is 1, we found a path where no single step requires more than 1 unit of effort. The cliff at (0,1) with height 10 was completely avoided by going around.

Solution

public int minimumEffortPath(int[][] heights) {
    int rows = heights.length;
    int cols = heights[0].length;
    
    // Initialize distance array
    int[][] dist = new int[rows][cols];
    for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
    dist[0][0] = 0;
    
    // Min-heap: {effort, row, col}
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
    heap.offer(new int[]{0, 0, 0});
    
    // Directions: up, down, left, right
    int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    while (!heap.isEmpty()) {
        int[] curr = heap.poll();
        int effort = curr[0], row = curr[1], col = curr[2];
        
        // Check if reached destination
        if (row == rows - 1 && col == cols - 1) {
            return effort;
        }
        
        // Skip if already found better path
        if (effort > dist[row][col]) continue;
        
        // Explore neighbors
        for (int[] dir : dirs) {
            int nr = row + dir[0];
            int nc = col + dir[1];
            
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                int diff = Math.abs(heights[nr][nc] - heights[row][col]);
                int newEffort = Math.max(effort, diff);
                
                if (newEffort < dist[nr][nc]) {
                    dist[nr][nc] = newEffort;
                    heap.offer(new int[]{newEffort, nr, nc});
                }
            }
        }
    }
    
    return dist[rows - 1][cols - 1];
}