DSA sheet · Graphs · Dijkstra pattern

Path With Minimum Effort

The last Dijkstra problem, and it brings two new things. First, the graph is a grid, so there's no adjacency list: neighbours are the 4 cells around you. Second, a path's cost is not a sum but the biggest single jump along it. The teacher shows that Dijkstra still works if we just replace "+" with "max". At the end she leaves a homework: solve it with binary search on the answer, and pick between the two methods by looking at the constraints. Both are written out in full below.

Every problem below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Dijkstra on the grid (effort = max, not sum)
• Part B · Binary search on the answer + BFS (her homework)
• Part C · Revision page

Part 0 · Before starting

A grid is a graph

Every cell (r, c) is a node. Two cells are joined by an edge if they touch up, down, left or right (not diagonally). The edges are undirected (you can step both ways), and here each edge has a weight: the height difference between the two cells.

         (r-1, c)
            |
 (r, c-1) —(r, c)— (r, c+1)
            |
         (r+1, c)

We never build an adjacency list for a grid. The neighbours come from a small list of directions (dr, dc), and each one needs a bounds check so we don't step off the grid.

grid = [[1, 2, 2],
        [3, 8, 2],
        [5, 3, 5]]
m, n = len(grid), len(grid[0])
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]   # right, left, up, down

r, c = 0, 0
for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n:              # stay inside the grid
        print((nr, nc), abs(grid[r][c] - grid[nr][nc]))
# prints (0, 1) 1  then  (1, 0) 2   (left and up are outside)

Visited in grids, BFS, and why this problem uses Dijkstra

In earlier grid problems (Number of Islands, Rotting Oranges) we used BFS with a queue and marked cells visited so we'd never enter them twice. That works when every step costs the same. Here steps have different weights, so we need Dijkstra: a min-heap (always continue from the cheapest cell so far) and, instead of visited, "enter a cell again only if you arrive with a smaller value". Background and a picture of plain BFS failing: Dijkstra page.

Binary search on the answer (for Part B)

When the answer is a number, and "can I do it with at most X?" is a yes/no question whose answers look like no no no yes yes yes as X grows, we can binary search for the first "yes". Each check costs one simple BFS. That's Part B.

Part A · Dijkstra on the grid

LeetCode 1631

1The question in simple words

You get a grid heights of size rows × cols. You start at the top-left cell (0, 0) and want to reach the bottom-right cell (rows−1, cols−1), moving up, down, left or right.

The effort of a path is the largest absolute height difference between two neighbouring cells on that path. ("Absolute" means ignore the sign: going 5 → 3 and 3 → 5 both count as 2.) Return the smallest effort over all paths.

Her example (LeetCode example 1):

  1  2  2
  3  8  2
  5  3  5

  1→ 2→ 2
  3  8  2       jumps: 1, 0, 0, 3
  5  3  5       effort = 3

  1  2  2
  3  8  2       jumps: 2, 2, 2, 2
  5→ 3→ 5       effort = 2

Path X has small jumps, but one jump of 3 (2 → 5) and the effort is the worst jump, so 3. Path Y has jumps all of size 2, so its effort is 2. No path does better. Answer: 2.

2What the constraints tell us

• rows, cols ≤ 100 → at most 10⁴ cells, and each cell has at most 4 edges → about 4·10⁴ edges. Dijkstra's O(mn log mn) is tiny.
• heights from 1 to 10⁶ → an effort is at most 10⁶ − 1. She uses this number later to compare Dijkstra with binary search.
• Every jump is ≥ 0 (absolute difference), so efforts never go negative, which Dijkstra needs.
• The grid has at least one cell. A 1×1 grid means start = end and the answer is 0.

3Intuition

This is Dijkstra where the "distance" of a cell is the smallest effort with which we can reach it. From a cell with effort e, stepping to a neighbour with jump j gives that neighbour max(e, j), not e + j. The min-heap always continues from the cell with the smallest effort so far, so the first time we pop the bottom-right cell, its effort is the minimum.

4Building the logic from her example

Where do we start? BFS or DFS?

The question fixes the start: (0, 0), with effort 0 (no jumps yet). She says DFS could work too, but for "reach a target with the least cost" problems she prefers BFS, and with a heap BFS becomes Dijkstra.

What's in the heap? → (effort, row, col)

A cell is no longer a single number, so the entry holds its row and column, with effort first so the heap orders by effort.

The new rule: carry the maximum, not the sum

She walks it: from 1 we can go right to 2 (jump 1) or down to 3 (jump 2). Push (1, 0, 1) and (2, 1, 0). The heap gives the effort-1 cell first; that's why we need a min-heap: explore the gentlest path first.

From that 2 at (0,1), stepping right to the other 2 is a jump of 0. Do we save 0? No. The path so far already contains a jump of 1, and the effort is the biggest jump on the whole path. So we save max(1, 0) = 1. Stepping down to 8 instead is a jump of 6, so that path's effort becomes max(1, 6) = 6.

The dist grid: start with infinity, save only improvements

Like the dist array in Dijkstra, but 2D: dist[r][c] = smallest effort found so far to reach (r, c). All infinity, except dist[0][0] = 0. We push a neighbour only if new_effort < dist[nr][nc].

Her example of why this replaces visited: from the 2 at (0,1), going back to the start (0,0) would give effort 1, but (0,0) already has 0. Not smaller → don't go. So the condition itself stops us going back and forth, and no visited grid is needed. And when a better effort does arrive, we must be allowed back in: the 8 in the middle first gets 6 (from above, via 2→8), later 5 (from the left, via 3→8). We overwrite 6 with 5.

Stale entries

The 8 sits in the heap twice, as (6, 1, 1) and (5, 1, 1). If an entry is popped with an effort bigger than dist[r][c], a better path already handled that cell: continue.

When is the answer final? On pop, not on push

This is a point she stresses. The bottom-right cell is first pushed with effort 3 (path X). If we stopped there we'd answer 3, which is wrong. When we push, we don't yet know what's still to come. When we pop, the heap promises nothing smaller is left. Later the cell is pushed again with 2 (path Y), and (2, 2, 2) comes out of the heap before (3, 2, 2). So: check for the target right after popping.

5Approach steps

1. m, n = rows, cols. dist = m × n grid of infinity; dist[0][0] = 0.
2. Heap = [(0, 0, 0)] (effort, row, col).
3. Pop the smallest. If its effort > dist at that cell → stale, continue.
4. If it's the bottom-right cell → return its effort.
5. For each of the 4 directions: skip if outside the grid. Else new_effort = max(effort, |height difference|). If smaller than dist[nr][nc]: save it and push.

6Code (Python)

import heapq

class Solution:
    def minimumEffortPath(self, heights):
        m, n = len(heights), len(heights[0])
        dist = [[float('inf')] * n for _ in range(m)]
        dist[0][0] = 0
        pq = [(0, 0, 0)]                                    # (effort, row, col)
        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]

        while pq:
            effort, r, c = heapq.heappop(pq)
            if effort > dist[r][c]:                         # stale entry
                continue
            if r == m - 1 and c == n - 1:                   # target popped = final
                return effort
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if nr < 0 or nr >= m or nc < 0 or nc >= n:  # off the grid
                    continue
                edge = abs(heights[r][c] - heights[nr][nc]) # this one jump
                new_effort = max(effort, edge)              # worst jump on the path
                if new_effort < dist[nr][nc]:
                    dist[nr][nc] = new_effort
                    heapq.heappush(pq, (new_effort, nr, nc))
        return dist[m - 1][n - 1]

7Code line by line

8Dry run: heap and dist grid after every pop

Heights as above. dist grid written row by row, rows separated by "|". Heap entries are (effort, row, col), sorted.

Start: dist = 0 ∞ ∞ | ∞ ∞ ∞ | ∞ ∞ ∞, heap = (0,0,0).

  0  1  1
  2  6  1
  ∞  ∞  3   ← not final yet!

  0  1  1
  2  5  1
  2  ∞  3

  0  1  1
  2  5  1
  2  2  2   ← popped next → answer

The two leftover entries for the target, (3, 2, 2), and for the 8, (6, 1, 1) and (5, 1, 1), are never popped because we return first. Had they been popped, (3, 2, 2) and (6, 1, 1) would be stale.

9Complexity & remember

• There are m·n cells, each with 4 directions, so up to about 4·m·n pushes in the worst case. She describes that worst case as every new effort beating the old one, so cells keep getting pushed again.
• Time O(mn · log(mn)): each push or pop costs log of the heap size.
• Space O(mn): the dist grid plus up to about 4mn heap entries.

Part B · Binary search on the answer + BFS

She leaves this as homework, explains the idea and compares the costs. Here it is written out fully.

1The question, asked differently

Instead of "what's the smallest effort?", ask a yes/no question: "can I get from start to end if I'm never allowed a jump bigger than X?" Find the smallest X for which the answer is yes.

2What the constraints tell us

• The answer lies between 0 and max height − min height (no jump can be bigger than that). With heights up to 10⁶, that's about 10⁶ values to search, which takes about log₂(10⁶) ≈ 20 checks.
• Each check is a plain BFS over m·n ≤ 10⁴ cells.

3Intuition: why binary search is allowed

If you can make the trip with jump limit X, you can certainly make it with any bigger limit (the same path still works). So as X grows, the answers go no, no, …, no, yes, yes, …, yes. They switch only once. Binary search finds that switch point.

Her walk-through on the example: the largest value is 8, so try the middle, 4: possible? Yes, so the answer is at most 4 → look lower. Try 2: yes → look lower. Try 1: no. So the answer is 2. Only a few BFS runs.

4Building the check

can_reach(limit): a normal BFS from (0, 0), stepping only to neighbours whose height difference is ≤ limit. Return True if we reach the bottom-right cell.

5Approach steps

1. lo = 0, hi = max(heights) − min(heights). The answer is in [lo, hi], and hi surely works.
2. While lo < hi: mid = (lo + hi) // 2.
3. If can_reach(mid): the answer is mid or smaller → hi = mid.
4. Else: mid is too strict → lo = mid + 1.
5. Return lo (= hi, the smallest limit that works).

6Code (Python)

from collections import deque

class Solution:
    def minimumEffortPath(self, heights):
        m, n = len(heights), len(heights[0])
        directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]

        def can_reach(limit):                       # BFS using only jumps <= limit
            visited = [[False] * n for _ in range(m)]
            visited[0][0] = True
            queue = deque([(0, 0)])
            while queue:
                r, c = queue.popleft()
                if r == m - 1 and c == n - 1:
                    return True
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and not visited[nr][nc] \
                            and abs(heights[r][c] - heights[nr][nc]) <= limit:
                        visited[nr][nc] = True
                        queue.append((nr, nc))
            return False

        lo = 0
        hi = max(map(max, heights)) - min(map(min, heights))
        while lo < hi:
            mid = (lo + hi) // 2
            if can_reach(mid):
                hi = mid                            # works: try smaller
            else:
                lo = mid + 1                        # too strict: go bigger
        return lo

7Code line by line

8Dry run

Same grid: max 8, min 1 → lo = 0, hi = 7.

lo = hi = 2 ✓. Three BFS runs.

  1* 2* 2*
  3  8  2*
  5  3  5    ← (2,2) needs a jump of 3 ✗

  1* 2* 2*
  3* 8  2*
  5* 3* 5*   ← reached ✓

9Complexity, and which method to pick

• Binary search: about log₂(max − min) checks, each a BFS of O(mn) → O(mn · log(maxHeight)) time, O(mn) space.
• Dijkstra: O(mn · log(mn)) time.

Her comparison with this problem's constraints:

So neither is always faster: it depends on the constraints. Her interview tip: ask the interviewer how large the values can get. Small heights with a big grid → binary search. Huge heights → Dijkstra. Both pass on LeetCode.

Part C · Revision page

s = Solution()
print(s.minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]]))      # 2
print(s.minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]]))      # 1
print(s.minimumEffortPath([[1, 2, 1, 1, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 2, 1, 2, 1], [1, 1, 1, 2, 1]]))   # 0
print(s.minimumEffortPath([[7]]))                                  # 0
print(s.minimumEffortPath([[1, 10, 1]]))                           # 9

Based on this video: Path With Minimum Effort