BS on Answer — Path With Minimum Effort

↗ LeetCode: Path With Minimum Effort · Medium · pattern chapter →

Asked atAmazonGoogle

In a 2D grid of heights, an "effort" of a path is the max abs-diff between consecutive cells. Return the min effort from top-left to bottom-right (4-connected).

Example — heights=[[1,2,2],[3,8,2],[5,3,5]] → 2

Constraints — 1 ≤ m, n ≤ 100; 0 ≤ height[i][j] ≤ 10⁶.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Dijkstra with edge weight = max-so-far

O(mn log mn).

Approach 2 — Binary search on the effort + BFS reachability

Insight. feasible(e) = can we walk from start to end using only edges with |diff| ≤ e? Monotonic. Binary search minimum e.

int minimumEffortPath(int[][] h) {
    int m = h.length, n = h[0].length;
    int lo = 0, hi = 1_000_000;
    int[][] DIR = {{1,0},{-1,0},{0,1},{0,-1}};
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        boolean[][] seen = new boolean[m][n];
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[]{0, 0}); seen[0][0] = true;
        while (!q.isEmpty()) {
            int[] c = q.poll();
            if (c[0] == m - 1 && c[1] == n - 1) break;
            for (int[] d : DIR) {
                int r = c[0] + d[0], col = c[1] + d[1];
                if (r < 0 || r >= m || col < 0 || col >= n || seen[r][col]) continue;
                if (Math.abs(h[r][col] - h[c[0]][c[1]]) <= mid) { seen[r][col] = true; q.offer(new int[]{r, col}); }
            }
        }
        if (seen[m - 1][n - 1]) hi = mid;
        else                    lo = mid + 1;
    }
    return lo;
}

Execution Trace

Dijkstra with edge weight = max-so-far

Step 1 / 3Initialize scan.

Complexity — Time O(mn · log(max)); Space O(mn).

Try it yourself

Complexity summary

Approach	Time	Space
Dijkstra	O(mn log mn)	O(mn)
BS + BFS	O(mn log(max))	O(mn)

When to use which

• "Min max edge on path" → BS on answer OR Dijkstra with max-of-path metric OR MST.
• Dijkstra variant — replace sum with max in relaxation.
• Streaming edge addition → Union-Find with sorted edges.

✨AI Study CompanionBeta

Related problems

• Swim in Rising Water — same idea, sea level = effort
• Path With Maximum Minimum Value — dual (maximize min)

Was this page helpful?