Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumshortest-path-weighted

Path With Minimum Effort

Problem (restated)

A height grid. Moving to a 4-neighbor costs the absolute height difference. A path’s effort is the max of those differences. Return the minimum effort of any path from the top-left to the bottom-right.

Intuition

Effort is a bottleneck, not a sum: a path is feasible for threshold x iff every consecutive pair differs by at most x. That is Dijkstra with newDist = max(old, edge), or binary search on x plus an unweighted walk.

Approaches

Dijkstra on max-edge

Unverified

Time O(mn log mn)Space O(mn)

Idea. dist[r][c] = min effort to that cell. Relax with max(d, |h[nr][nc] - h[r][c]|). First time the sink is popped, that effort is optimal.

Walkthrough. [[1,2,2],[3,8,2],[5,3,5]]. Path 1-2-2-2-5 has max step 3; 1-3-5-3-5 has max 2. Answer 2.

Trade-offs. Same Dijkstra loop as LC 743; only the relax operator changes. Non-negative “weights” (absolute diffs) keep the greedy invariant.

Solution

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Dist is the max edge so far, not a sum.
 */
export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dist = Array.from({ length: m }, () => new Array<number>(n).fill(Infinity));
  dist[0]![0] = 0;
  const pq: [number, number, number][] = [[0, 0, 0]];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, r, c] = pq.shift()!;
    if (d > dist[r]![c]!) continue;
    if (r === m - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      const nd = Math.max(d, Math.abs(heights[nr]![nc]! - heights[r]![c]!));
      if (nd < dist[nr]![nc]!) {
        dist[nr]![nc] = nd;
        pq.push([nd, nr, nc]);
      }
    }
  }
  return 0;
}

/**
 * Toy PQ: sort + shift. Interview/production: binary heap.
 * Dist is the max edge so far, not a sum.
 */
export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dist = Array.from({ length: m }, () => new Array<number>(n).fill(Infinity));
  dist[0]![0] = 0;
  const pq: [number, number, number][] = [[0, 0, 0]];
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  while (pq.length) {
    pq.sort((a, b) => a[0]! - b[0]!);
    const [d, r, c] = pq.shift()!;
    if (d > dist[r]![c]!) continue;
    if (r === m - 1 && c === n - 1) return d;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nc < 0 || nr >= m || nc >= n) continue;
      const nd = Math.max(d, Math.abs(heights[nr]![nc]! - heights[r]![c]!));
      if (nd < dist[nr]![nc]!) {
        dist[nr]![nc] = nd;
        pq.push([nd, nr, nc]);
      }
    }
  }
  return 0;
}

Binary search + BFS

Unverified

Time O(mn log H)Space O(mn)

Idea. Search effort in [0, 10^6]. A mid is feasible if a DFS/BFS from (0,0) using only edges with |Δh| ≤ mid reaches the sink. Shrink to the smallest feasible mid.

Walkthrough. Same grid: mid=1 cannot reach; mid=2 can. Answer 2.

Trade-offs. Matches binary-search-on-answer. More code than Dijkstra, but the feasibility check is plain flood fill. H is the height range.

Solution

export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  const can = (mid: number): boolean => {
    const seen = Array.from({ length: m }, () => new Array<boolean>(n).fill(false));
    const stack: [number, number][] = [[0, 0]];
    seen[0]![0] = true;
    while (stack.length) {
      const [r, c] = stack.pop()!;
      if (r === m - 1 && c === n - 1) return true;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr]![nc]) continue;
        if (Math.abs(heights[nr]![nc]! - heights[r]![c]!) > mid) continue;
        seen[nr]![nc] = true;
        stack.push([nr, nc]);
      }
    }
    return false;
  };
  let lo = 0, hi = 1_000_000;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (can(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

export function minimumEffortPath(heights: number[][]): number {
  const m = heights.length, n = heights[0]!.length;
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]] as const;
  const can = (mid: number): boolean => {
    const seen = Array.from({ length: m }, () => new Array<boolean>(n).fill(false));
    const stack: [number, number][] = [[0, 0]];
    seen[0]![0] = true;
    while (stack.length) {
      const [r, c] = stack.pop()!;
      if (r === m - 1 && c === n - 1) return true;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= m || nc >= n || seen[nr]![nc]) continue;
        if (Math.abs(heights[nr]![nc]! - heights[r]![c]!) > mid) continue;
        seen[nr]![nc] = true;
        stack.push([nr, nc]);
      }
    }
    return false;
  };
  let lo = 0, hi = 1_000_000;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (can(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

Template connection

Dijkstra with a max-edge cost, or binary search on the answer plus BFS. Both are listed on the pattern page; Dijkstra is the “this is a shortest path” reading.

Reflection

Effort is the largest height gap on the path. Dijkstra minimizes that effort. Binary search picks a threshold and BFS asks whether that effort can reach the end.
One cell is 0. A flat grid is 0. Four directions. The gap is an absolute difference.
Effort is never negative, so Dijkstra’s first pop of the sink is optimal. A large enough threshold lets BFS reach every cell.