1631. Path With Minimum Effort

At a Glance

Topic: advanced-graphs
Pattern: Dijkstra minimax on grid + heap; alternative binary search + BFS
Difficulty: Hard
Companies: Google, Amazon, Meta, Microsoft, Coupang
Frequency: High
LeetCode: 1631

rows x cols integer heights. Moving between adjacent cells costs abs(heights[row][col] - heights[nextRow][nextCol]). Return the minimum possible maximum edge cost along a path from top-left to bottom-right.

Recognition Cues

Same structure as Swim in Rising Water — minimax path cost
Edge weight is absolute difference — nonnegative
Grid graph — node count moderate

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Binary search on answer + BFS reachability — O(rows * cols * log(maxHeight)).
Dijkstra on “effort so far = max edge along path” — O(rows * cols * log(rows*cols)) — clean single pass.

Optimal Solution

Go

import "container/heap"

type effortCell struct {
	row           int
	col           int
	maxEdgeSoFar  int
	heapIndex     int
}

type effortHeap []*effortCell

func (heapData effortHeap) Len() int { return len(heapData) }
func (heapData effortHeap) Less(indexA, indexB int) bool {
	return heapData[indexA].maxEdgeSoFar < heapData[indexB].maxEdgeSoFar
}
func (heapData effortHeap) Swap(indexA, indexB int) {
	heapData[indexA], heapData[indexB] = heapData[indexB], heapData[indexA]
	heapData[indexA].heapIndex = indexA
	heapData[indexB].heapIndex = indexB
}
func (heapData *effortHeap) Push(value interface{}) {
	item := value.(*effortCell)
	item.heapIndex = len(*heapData)
	*heapData = append(*heapData, item)
}
func (heapData *effortHeap) Pop() interface{} {
	old := *heapData
	n := len(old)
	item := old[n-1]
	*heapData = old[0 : n-1]
	return item
}

func minimumEffortPath(heights [][]int) int {
	rows := len(heights)
	cols := len(heights[0])
	const inf = int(^uint(0) >> 1)
	best := make([][]int, rows)
	for row := range best {
		best[row] = make([]int, cols)
		for col := range best[row] {
			best[row][col] = inf
		}
	}
	best[0][0] = 0
	directions := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	priorityQueue := &effortHeap{}
	heap.Init(priorityQueue)
	heap.Push(priorityQueue, &effortCell{row: 0, col: 0, maxEdgeSoFar: 0})
	for priorityQueue.Len() > 0 {
		current := heap.Pop(priorityQueue).(*effortCell)
		if current.maxEdgeSoFar > best[current.row][current.col] {
			continue
		}
		if current.row == rows-1 && current.col == cols-1 {
			return current.maxEdgeSoFar
		}
		for _, direction := range directions {
			nextRow := current.row + direction[0]
			nextCol := current.col + direction[1]
			if nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols {
				continue
			}
			stepEffort := heights[current.row][current.col] - heights[nextRow][nextCol]
			if stepEffort < 0 {
				stepEffort = -stepEffort
			}
			nextEffort := current.maxEdgeSoFar
			if stepEffort > nextEffort {
				nextEffort = stepEffort
			}
			if nextEffort < best[nextRow][nextCol] {
				best[nextRow][nextCol] = nextEffort
				heap.Push(priorityQueue, &effortCell{row: nextRow, col: nextCol, maxEdgeSoFar: nextEffort})
			}
		}
	}
	return 0
}

JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }
  get length() {
    return this.data.length;
  }
  push(item) {
    this.data.push(item);
    this.bubbleUp(this.data.length - 1);
  }
  pop() {
    if (this.data.length === 0) {
      return undefined;
    }
    const top = this.data[0];
    const last = this.data.pop();
    if (this.data.length > 0) {
      this.data[0] = last;
      this.bubbleDown(0);
    }
    return top;
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index].maxEdgeSoFar >= this.data[parentIndex].maxEdgeSoFar) {
        break;
      }
      [this.data[index], this.data[parentIndex]] = [this.data[parentIndex], this.data[index]];
      index = parentIndex;
    }
  }
  bubbleDown(index) {
    const size = this.data.length;
    while (true) {
      let smallest = index;
      const left = index * 2 + 1;
      const right = index * 2 + 2;
      if (left < size && this.data[left].maxEdgeSoFar < this.data[smallest].maxEdgeSoFar) {
        smallest = left;
      }
      if (right < size && this.data[right].maxEdgeSoFar < this.data[smallest].maxEdgeSoFar) {
        smallest = right;
      }
      if (smallest === index) {
        break;
      }
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}

function minimumEffortPath(heights) {
  const rows = heights.length;
  const cols = heights[0].length;
  const inf = Number.MAX_SAFE_INTEGER;
  const best = Array.from({ length: rows }, () => Array(cols).fill(inf));
  best[0][0] = 0;
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const heap = new MinHeap();
  heap.push({ row: 0, col: 0, maxEdgeSoFar: 0 });
  while (heap.length > 0) {
    const current = heap.pop();
    if (current.maxEdgeSoFar > best[current.row][current.col]) {
      continue;
    }
    if (current.row === rows - 1 && current.col === cols - 1) {
      return current.maxEdgeSoFar;
    }
    for (const direction of directions) {
      const nextRow = current.row + direction[0];
      const nextCol = current.col + direction[1];
      if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols) {
        continue;
      }
      const stepEffort = Math.abs(heights[current.row][current.col] - heights[nextRow][nextCol]);
      const nextEffort = Math.max(current.maxEdgeSoFar, stepEffort);
      if (nextEffort < best[nextRow][nextCol]) {
        best[nextRow][nextCol] = nextEffort;
        heap.push({ row: nextRow, col: nextCol, maxEdgeSoFar: nextEffort });
      }
    }
  }
  return 0;
}

Walkthrough

Push (0,0) with effort 0. Pop smallest maxEdgeSoFar; relax neighbors with new effort max(prev, |Δh|). First pop of destination yields minimax cost.

Invariant: When a cell is first visited, its popped maxEdgeSoFar is minimal achievable minimax value (Dijkstra on expanded edge weights).

Edge Cases

1x1 grid — 0
Flat grid — 0
Monotone ridge along diagonal — effort equals largest step on chosen path

Pitfalls

Using sum of absolute differences instead of max along path
Marking visited on pop vs push — either works with consistent Dijkstra; LeetCode solutions often mark on push for grids

Variants

K-th smallest minimax value — persistent search or binary search on answer with counting.
8-directional moves — neighbor loop grows; same PQ logic.
Query multiple pairs — preprocess with APSP on small grid or reuse binary search + BFS.

Mind-Map Tags

#dijkstra #minimax #grid #binary-search-on-answer #absolute-difference-edge