Minimum Effort Path — Dijkstra / Binary Search + BFS

Problem

Find a path from (0,0) to (R-1,C-1) minimizing the maximum absolute difference between adjacent cells on the path.

Approach 1 — Dijkstra (optimal)

State = (max_effort_so_far, r, c). Process in order of current effort, relax neighbors.

Time: O(mnlog(mn)) | Space: O(mn)

Approach 2 — Binary Search + BFS

Binary search on effort; check if a valid path exists with BFS.

Solutions

Python — Dijkstra

import heapq
class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        R,C=len(heights),len(heights[0])
        dist=[[float('inf')]*C for _ in range(R)]
        dist[0][0]=0; heap=[(0,0,0)]
        while heap:
            d,r,c=heapq.heappop(heap)
            if d>dist[r][c]: continue
            if r==R-1 and c==C-1: return d
            for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                nr,nc=r+dr,c+dc
                if 0<=nr<R and 0<=nc<C:
                    nd=max(d,abs(heights[nr][nc]-heights[r][c]))
                    if nd<dist[nr][nc]:
                        dist[nr][nc]=nd; heapq.heappush(heap,(nd,nr,nc))
        return 0

Python — Binary Search + BFS

from collections import deque
class Solution:
    def minimumEffortPath(self, heights: list[list[int]]) -> int:
        R,C=len(heights),len(heights[0])
        def canReach(effort):
            visited=[[False]*C for _ in range(R)]
            q=deque([(0,0)]); visited[0][0]=True
            while q:
                r,c=q.popleft()
                if r==R-1 and c==C-1: return True
                for dr,dc in[(1,0),(-1,0),(0,1),(0,-1)]:
                    nr,nc=r+dr,c+dc
                    if 0<=nr<R and 0<=nc<C and not visited[nr][nc]:
                        if abs(heights[nr][nc]-heights[r][c])<=effort:
                            visited[nr][nc]=True; q.append((nr,nc))
            return False
        lo,hi=0,10**6
        while lo<hi:
            mid=(lo+hi)//2
            if canReach(mid): hi=mid
            else: lo=mid+1
        return lo

Complexity

Dijkstra: O(mnlog(mn)) | Space: O(mn)
Binary Search + BFS: O(mnlog(max_diff))