Path With Minimum Effort

▶

Steps

setup

Initialize - dist all ∞, push (0, 0,0) to heap

Set dist[0][0]=0, all others=∞. Push (effort=0, r=0, c=0) to the min-heap. Grid heights: row0=[1,2,2], row1=[3,8,2], row2=[5,3,5].

💡 Starting cell (0,0) has effort 0 to reach itself. All others start at infinity meaning unreachable.

Line:

dist = [[float('inf')] * cols for _ in range(rows)]
dist[0][0] = 0
heap = [(0, 0, 0)]

💡 Infinity initialization ensures any real path effort will improve the distance.

expand

Pop (0, 0,0) - relax neighbors (0,1) and (1,0)

Pop cell (0,0) with effort=0. Check neighbors: (0,1) h=2, edge=|1-2|=1, next_effort=max(0,1)=1 < ∞ → update dist[0][1]=1, push (1,0,1). (1,0) h=3, edge=|1-3|=2, next_effort=max(0,2)=2 < ∞ → update dist[1][0]=2, push (2,1,0).

💡 The effort to reach a neighbor = max(effort to reach current, edge difference). We take the max because the bottleneck of a path is its hardest single step.

Line:

effort, r, c = heapq.heappop(heap)
for dr, dc in directions:
    next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
    if next_effort < dist[nr][nc]:
        dist[nr][nc] = next_effort
        heapq.heappush(heap, (next_effort, nr, nc))

💡 Both neighbors relaxed. (0,1) is cheaper to reach (effort 1) than (1,0) (effort 2).

expand

Pop (1, 0,1) - relax (0,2) and (1,1)

Pop (0,1) with effort=1. Check neighbors: (0,0) already done (effort 1 > dist[0][0]=0, skip). (0,2) h=2, edge=|2-2|=0, next_effort=max(1,0)=1 → dist[0][2]=1, push (1,0,2). (1,1) h=8, edge=|2-8|=6, next_effort=max(1,6)=6 → dist[1][1]=6, push (6,1,1).

💡 Edge from (0,1) to (0,2) has 0 difference (same height!), so effort stays 1. But edge to (1,1) jumps to 8 so effort becomes 6.

Line:

next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
if next_effort < dist[nr][nc]:
    dist[nr][nc] = next_effort

💡 The top row has low effort because heights are [1,2,2] - small differences. Going into (1,1)=8 is very expensive.

expand

Pop (1, 0,2) - relax (1,2)

Pop (0,2) with effort=1. Neighbor (1,2) h=2, edge=|2-2|=0, next_effort=max(1,0)=1 → dist[1][2]=1, push (1,1,2). (0,1) already done. (1,1): next_effort=max(1,6)=6, not < dist[1][1]=6 → no update.

💡 Another 0-diff edge! From (0,2) to (1,2) both have height 2. The top-right to middle-right path stays at effort 1.

Line:

next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
if next_effort < dist[nr][nc]: ...

💡 The path 0,0→0,1→0,2→1,2 all has heights [1,2,2,2] - max diff is 1. We're building a low-effort path down the right column.

expand

Pop (1, 1,2) - reach (2,2) with effort 3

Pop (1,2) effort=1. Neighbor (2,2) h=5, edge=|2-5|=3, next_effort=max(1,3)=3 → dist[2][2]=3. Also (1,1) h=8, edge=|2-8|=6, next_effort=max(1,6)=6=dist[1][1] → no update.

💡 We can now reach (2,2) with effort 3 via the right column path. But dist[2][2]=3 is not final - there may be a better path via (1,0) and (2,0).

Line:

next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
if next_effort < dist[nr][nc]:
    dist[nr][nc] = next_effort
    heapq.heappush(heap, (next_effort, nr, nc))

💡 The right column path gives effort 3. The left column path via (1,0) might be cheaper - we'll see when (1,0) is processed.

expand

Pop (2, 1,0) - relax (2,0); better path to (2,2) found

Pop (1,0) effort=2. Neighbor (2,0) h=5, edge=|3-5|=2, next_effort=max(2,2)=2 → dist[2][0]=2. Neighbor (1,1) h=8, edge=|3-8|=5, next_effort=max(2,5)=5 < 6 → update dist[1][1]=5.

💡 The left column is turning out competitive. dist[2][0]=2 means we can reach the bottom-left with effort 2.

Line:

next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
if next_effort < dist[nr][nc]:

💡 Effort 2 to reach (2,0) is less than effort 3 to reach (2,2) via right column. The bottom-row path 2,0→2,1→2,2 may beat effort 3.

expand

Pop (2, 2,0) - relax (2,1) with effort 2

Pop (2,0) effort=2. Neighbor (2,1) h=3, edge=|5-3|=2, next_effort=max(2,2)=2 → dist[2][1]=2, push (2,2,1). Neighbor (1,0) done. This gives us a promising bottom-row path.

💡 Effort 2 to reach (2,1) from (2,0). The bottom row heights are [5,3,5] - differences are 2.

Line:

next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
if next_effort < dist[nr][nc]:
    dist[nr][nc] = next_effort
    heapq.heappush(heap, (next_effort, nr, nc))

💡 The bottom row path 0,0→1,0→2,0→2,1 has max diff=2 at each step. Almost there.

expand

Pop (2, 2,1) - update dist[2][2]=2! Better path found

Pop (2,1) effort=2. Neighbor (2,2) h=5, edge=|3-5|=2, next_effort=max(2,2)=2 < dist[2][2]=3 → UPDATE! dist[2][2]=2, push (2,2,2). The bottom-row path is better than the right-column path.

💡 dist[2][2] was 3 from the right column path. Now we found a path with effort 2. The Dijkstra relaxation updates the distance.

Line:

next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
if next_effort < dist[nr][nc]:  # 2 < 3 → update!
    dist[nr][nc] = next_effort

💡 Path (0,0)→(1,0)→(2,0)→(2,1)→(2,2) has heights [1,3,5,3,5]. Max diff = max(2,2,2,2) = 2.

reconstruct

Pop (2, 2,2) - destination reached, return 2

Pop (2,2) with effort=2. This is the destination (rows-1, cols-1). Return effort=2 immediately. The stale entry (3,2,2) will never be processed because we return early.

💡 Dijkstra guarantees: the first time we pop the destination, we have the minimum effort. Return immediately.

Line:

if r == rows - 1 and c == cols - 1:
    return effort  # minimum effort found!

💡 The answer is 2: the path (0,0)→(1,0)→(2,0)→(2,1)→(2,2) with heights [1,3,5,3,5] has max consecutive difference = 2.

from typing import List
import heapq

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        rows, cols = len(heights), len(heights[0])
        dist = [[float('inf')] * cols for _ in range(rows)]
        dist[0][0] = 0
        heap = [(0, 0, 0)]  # effort, r, c
        directions = [(1,0), (-1,0), (0,1), (0,-1)]

        while heap:
            effort, r, c = heapq.heappop(heap)
            if r == rows - 1 and c == cols - 1:
                return effort
            if effort > dist[r][c]:
                continue
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    next_effort = max(effort, abs(heights[r][c] - heights[nr][nc]))
                    if next_effort < dist[nr][nc]:
                        dist[nr][nc] = next_effort
                        heapq.heappush(heap, (next_effort, nr, nc))
        return 0

# Example usage:
# sol = Solution()
# print(sol.minimumEffortPath([[1,2,2],[3,8,2],[5,3,5]]))  # Output: 2

📊

Path With Minimum Effort - Watch Modified Dijkstra Execute, Step by Step

The key insight: effort for a path = max of all edge efforts along it. We use Dijkstra because this max-effort metric still satisfies the greedy relaxation property - the first time we pop a cell from the min-heap, we have found the minimum effort to reach it.

Visiting: none

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

(0, 0,0)

Visiting: 0,0

0,0

0,1

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

(1,0,1)(2,1,0)

Visiting: 0,1

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

(1,0,2)(2,1,0)(6,1,1)

Visiting: 0,2

Edge: 0,2 → 1,2

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

(1,1,2)(2,1,0)(6,1,1)

Visiting: 1,2

Edge: 1,2 → 2,2

0,0

0,1

0,2

1,0

1,1

1,2

2,0

2,1

2,2

Queue / Stack

(2,1,0)(3,2,2)(6,1,1)

Visiting: 1,0

0,0

1,0

2,0

1,1

2,2

Queue / Stack

(2,2,0)(3,2,2)(5,1,1)

Visiting: 2,0

Edge: 2,0 → 2,1

2,0

2,1

2,2

Queue / Stack

(2,2,1)(3,2,2)(5,1,1)

Visiting: 2,1

Edge: 2,1 → 2,2

2,1

2,2

Queue / Stack

(2,2,2)(3,2,2-stale)(5,1,1)

Visiting: 2,2

0,0

0,1

0,2

1,0

1,2

2,0

2,1

2,2

Key Takeaways

✓ effort(path) = max of all edge efforts along it. Dijkstra works because this max-metric satisfies the greedy relaxation property.

If you've seen Dijkstra for sum-of-weights, this is the same algorithm with max instead of sum.

✓ Relaxation: update dist[neighbor] only when max(current_effort, edge) < current dist[neighbor]. This is the key condition.

The relaxation can improve dist multiple times (see dist[2][2] going from 3→2) until the optimal value is locked in.

✓ Return immediately when the destination is first popped - Dijkstra guarantees the first pop gives the minimum.

This early return is what makes Dijkstra efficient - we don't process cells after finding the answer.

Practice

1. Given the following Python code implementing the two-pass DP solution for the 01 Matrix problem, what is the final distance matrix returned for input [[0,1,1],[1,1,0],[1,1,1]]?

easy

A. [[0,1,1],[1,1,0],[2,1,1]]

B. [[0,1,2],[1,1,0],[2,1,1]]

C. [[0,1,1],[1,2,0],[2,1,1]]

D. [[0,1,1],[1,1,0],[1,1,1]]

Solution

1. Step 1: Initialize distances

   Set dist to 0 where mat is 0, else infinity: [[0,inf,inf],[inf,inf,0],[inf,inf,inf]]

2. Step 2: Forward pass updates

   Update dist using top and left neighbors: [[0,1,2],[1,2,0],[2,3,1]]

3. Step 3: Backward pass updates

   Update dist using bottom and right neighbors: [[0,1,2],[1,1,0],[2,1,1]]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Distances match shortest paths to nearest zero [OK]

Hint: Two-pass DP updates distances from neighbors correctly [OK]

Common Mistakes:

• Off-by-one in indices
• Forgetting backward pass
• Incorrect initialization

2. Given the following DFS-based code for rotting oranges, what is the value of max_time after processing the grid [[2,1,1],[1,1,0],[0,1,1]]?

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    time_grid = [[-1]*cols for _ in range(rows)]
    max_time = 0

    def dfs(r, c, time):
        nonlocal max_time
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == 0:
            return
        if time_grid[r][c] != -1 and time_grid[r][c] <= time:
            return
        time_grid[r][c] = time
        max_time = max(max_time, time)
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 1 or (grid[nr][nc] == 2 and time_grid[nr][nc] > time + 1):
                    dfs(nr, nc, time + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                dfs(r, c, 0)
    return max_time

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace DFS from rotten orange at (0,0) with time=0

   It rots adjacent fresh oranges incrementally, updating time_grid and max_time as rot spreads.

2. Step 2: Follow rot spread minute by minute

   Rot spreads to (0,1) and (1,0) at time=1, then to (0,2), (1,1), and (2,1) at time=2, and finally to (2,2) at time=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Maximum rot time matches the longest path from initial rotten orange [OK]

Hint: Max time equals longest rot spread path [OK]

Common Mistakes:

• Off-by-one counting minutes
• Ignoring multiple rotten sources
• Confusing grid indices

3. You are given an n x n grid where each cell is either 0 (walkable) or 1 (blocked). You need to find the shortest path from the top-left corner to the bottom-right corner, moving in 8 possible directions (including diagonals). Which algorithmic approach guarantees finding the shortest path efficiently in this scenario?

easy

A. Breadth-First Search (BFS) using a queue to explore neighbors level by level

B. Depth-First Search with backtracking to explore all paths

C. Greedy Best-First Search prioritizing cells closest to the target

D. Dynamic Programming to store shortest paths to each cell

Solution

1. Step 1: Understand the problem constraints

   The grid allows movement in 8 directions and requires the shortest path from start to end.

2. Step 2: Identify the algorithm that guarantees shortest path in unweighted graphs

   BFS explores neighbors level by level, ensuring the first time we reach the target is via the shortest path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS is the classic shortest path algorithm for unweighted grids [OK]

Hint: Shortest path in unweighted grid -> BFS [OK]

Common Mistakes:

• Thinking DFS finds shortest path
• Using greedy heuristics without guarantees

4. What is the time complexity of the optimal two-pass dynamic programming solution for the 01 Matrix problem on an m x n grid?

medium

A. O(m * n) because each cell is processed a constant number of times in two passes

B. O(m + n) since only rows and columns are scanned separately

C. O(m * n * log(m * n)) due to sorting or priority queue operations

D. O(m^2 * n^2) because each cell is compared with all others

Solution

1. Step 1: Identify loops in the code

   Two nested loops over m rows and n columns run twice (forward and backward passes).

2. Step 2: Calculate total operations

   Each cell is updated a constant number of times, so total operations are proportional to m*n.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two passes over all cells -> O(m*n) [OK]

Hint: Two passes over grid -> linear in number of cells [OK]

Common Mistakes:

• Confusing with brute force O(m^2*n^2)
• Assuming sorting is involved
• Ignoring nested loops

5. What is the time complexity of the bidirectional BFS algorithm for finding the shortest path in an n x n binary matrix, assuming all cells are walkable (0)?

medium

A. O(n^4) because each BFS can explore all cells and edges

B. O(8^(n^2)) due to 8 possible moves from each cell

C. O(n^2) because BFS explores each cell at most once from both ends

D. O(n^3) because of nested loops over rows, columns, and directions

Solution

1. Step 1: Identify number of vertices and edges

   Grid has n^2 vertices; each vertex has up to 8 edges.

2. Step 2: Analyze BFS complexity

   BFS visits each vertex once; total edges processed is O(8*n^2) = O(n^2).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bidirectional BFS halves search space but still O(n^2) [OK]

Hint: BFS in grid -> O(n²) due to vertices and edges [OK]

Common Mistakes:

• Confusing exponential moves with complexity
• Assuming nested loops multiply to n^3 or n^4