Path with Minimum Effort

Difficulty: Medium Source: NeetCode

Problem

You are given an m x n integer matrix heights where heights[i][j] represents the height of cell (i, j). You are situated at the top-left cell (0, 0) and want to reach the bottom-right cell (m-1, n-1).

The effort of a route is the maximum absolute difference in heights between two consecutive cells of the route. Return the minimum effort required to travel from (0, 0) to (m-1, n-1).

Example 1: Input: heights = [[1,2,2],[3,8,2],[5,3,5]] Output: 2

Example 2: Input: heights = [[1,2,3],[3,8,4],[5,3,5]] Output: 1

Constraints:

• m == heights.length
• n == heights[i].length
• 1 <= m, n <= 100
• 1 <= heights[i][j] <= 10^6

Prerequisites

Before attempting this problem, you should be comfortable with:

• Dijkstra’s Algorithm — shortest path in a weighted graph using a min-heap
• Graph on a Grid — treating cells as nodes and edges as the transitions between them
• Heapq — Python’s priority queue module

1. Brute Force

Intuition

Try every possible path from the top-left to the bottom-right using DFS. For each path, track the maximum absolute difference seen so far. After exploring all paths, return the minimum of all those maximum differences. This is correct but exponentially slow because the number of paths in a grid is huge.

Algorithm

1. Use DFS from (0, 0), passing the current maximum effort seen on this path.
2. At the destination, record the effort if it’s the best seen.
3. Use a visited set to avoid revisiting cells on the same path.
4. Return the global minimum.

Solution

def minimumEffortPath_brute(heights):
    m, n = len(heights), len(heights[0])
    min_effort = float('inf')

    def dfs(r, c, current_max, visited):
        nonlocal min_effort
        if r == m - 1 and c == n - 1:
            min_effort = min(min_effort, current_max)
            return
        visited.add((r, c))
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited:
                effort = abs(heights[nr][nc] - heights[r][c])
                dfs(nr, nc, max(current_max, effort), visited)
        visited.remove((r, c))

    dfs(0, 0, 0, set())
    return min_effort


print(minimumEffortPath_brute([[1, 2, 2], [3, 8, 2], [5, 3, 5]]))  # 2
print(minimumEffortPath_brute([[1, 2, 3], [3, 8, 4], [5, 3, 5]]))  # 1
print(minimumEffortPath_brute([[1, 2, 1, 1, 1]]))                   # 0

Complexity

• Time: O(m * n * 2^(m*n)) — exponential due to all paths
• Space: O(m * n) — recursion stack and visited set

2. Dijkstra’s Algorithm

Intuition

Think of the grid as a weighted graph. Each cell is a node, and moving from one cell to an adjacent cell has an edge weight equal to the absolute height difference. We want the path where the maximum edge weight is minimized — this is called the “minimax path” problem. Dijkstra works perfectly here: instead of minimizing the total cost, we minimize the maximum edge cost seen so far on any path to each cell.

The key insight is that dist[r][c] stores the minimum possible “max effort” to reach (r, c). When we pop a cell from the heap, the value we pop is the best effort to reach that cell, so we can use it exactly like standard Dijkstra.

Algorithm

1. Initialize dist grid with infinity; set dist[0][0] = 0.
2. Push (0, 0, 0) — (effort, row, col) — into a min-heap.
3. While the heap is not empty:
   • Pop the cell with the smallest current effort.
   • If this is the destination, return the effort.
   • If the popped effort is greater than dist[r][c], skip (stale entry).
   • For each neighbor, compute new_effort = max(current_effort, abs_diff).
   • If new_effort < dist[nr][nc], update and push to heap.
4. Return dist[m-1][n-1].

Solution

import heapq

def minimumEffortPath(heights):
    m, n = len(heights), len(heights[0])
    dist = [[float('inf')] * n for _ in range(m)]
    dist[0][0] = 0
    heap = [(0, 0, 0)]  # (effort, row, col)

    while heap:
        effort, r, c = heapq.heappop(heap)

        if r == m - 1 and c == n - 1:
            return effort

        if effort > dist[r][c]:
            continue

        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n:
                new_effort = max(effort, abs(heights[nr][nc] - heights[r][c]))
                if new_effort < dist[nr][nc]:
                    dist[nr][nc] = new_effort
                    heapq.heappush(heap, (new_effort, nr, nc))

    return dist[m - 1][n - 1]


print(minimumEffortPath([[1, 2, 2], [3, 8, 2], [5, 3, 5]]))  # 2
print(minimumEffortPath([[1, 2, 3], [3, 8, 4], [5, 3, 5]]))  # 1
print(minimumEffortPath([[1, 2, 1, 1, 1]]))                   # 0
print(minimumEffortPath([[3]]))                                # 0

Complexity

• Time: O(m * n * log(m * n)) — each cell is pushed/popped from the heap at most once (in practice)
• Space: O(m * n) — dist grid and heap

Common Pitfalls

Using total sum instead of max difference. The effort of a route is the maximum absolute difference along the path, not the sum. Make sure you use max(current_effort, abs_diff) when updating, not current_effort + abs_diff.

Forgetting the stale entry check. In Dijkstra with lazy deletion, a cell can be pushed multiple times. Always check if effort > dist[r][c]: continue to skip outdated entries.

Off-by-one on grid bounds. Double-check 0 <= nr < m and 0 <= nc < n — a common source of index errors on grid problems.