778. Swim in Rising Water

At a Glance

Topic: graphs
Pattern: Dijkstra / “minimize max edge” (path threshold) with min-heap
Difficulty: Hard
Companies: Google, Amazon, Meta, Apple, Uber
Frequency: High
LeetCode: 778

In an n x n grid, water level in cell (row, col) is grid[row][col]. You swim from (0,0) to (n-1,n-1) in any 4-directional path. The time to traverse a path is the maximum water height along that path. Return the minimum such time over all paths.

Recognition Cues

“Minimize the maximum along a route” — minimax on a graph
Grid as graph; edge cost related to cell elevation
Classic Dijkstra where distance[cell] = min over paths of max height seen so far

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 — test threshold T, flood-fill if grid <= T — O(n^2 log(max)) — good alternative.
Dijkstra variant — priority queue by current water level so far — O(n^2 log(n^2)) — interview gold.

Optimal Solution

Go

import "container/heap"

type cellState struct {
	row         int
	col         int
	waterSoFar  int
	index       int
}

type minHeap []*cellState

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

func swimInWater(grid [][]int) int {
	size := len(grid)
	const inf = int(^uint(0) >> 1)
	best := make([][]int, size)
	for row := range best {
		best[row] = make([]int, size)
		for col := range best[row] {
			best[row][col] = inf
		}
	}
	startWater := grid[0][0]
	best[0][0] = startWater
	directions := [][2]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
	priorityQueue := &minHeap{}
	heap.Init(priorityQueue)
	heap.Push(priorityQueue, &cellState{row: 0, col: 0, waterSoFar: startWater})
	for priorityQueue.Len() > 0 {
		current := heap.Pop(priorityQueue).(*cellState)
		if current.waterSoFar > best[current.row][current.col] {
			continue
		}
		if current.row == size-1 && current.col == size-1 {
			return current.waterSoFar
		}
		for _, direction := range directions {
			nextRow := current.row + direction[0]
			nextCol := current.col + direction[1]
			if nextRow < 0 || nextRow >= size || nextCol < 0 || nextCol >= size {
				continue
			}
			maxAlongPath := current.waterSoFar
			if grid[nextRow][nextCol] > maxAlongPath {
				maxAlongPath = grid[nextRow][nextCol]
			}
			if maxAlongPath < best[nextRow][nextCol] {
				best[nextRow][nextCol] = maxAlongPath
				heap.Push(priorityQueue, &cellState{row: nextRow, col: nextCol, waterSoFar: maxAlongPath})
			}
		}
	}
	return -1
}

JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }
  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;
  }
  get length() {
    return this.data.length;
  }
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.data[index].waterSoFar >= this.data[parentIndex].waterSoFar) {
        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].waterSoFar < this.data[smallest].waterSoFar) {
        smallest = left;
      }
      if (right < size && this.data[right].waterSoFar < this.data[smallest].waterSoFar) {
        smallest = right;
      }
      if (smallest === index) {
        break;
      }
      [this.data[index], this.data[smallest]] = [this.data[smallest], this.data[index]];
      index = smallest;
    }
  }
}

function swimInWater(grid) {
  const size = grid.length;
  const inf = Number.MAX_SAFE_INTEGER;
  const best = Array.from({ length: size }, () => Array(size).fill(inf));
  best[0][0] = grid[0][0];
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0],
  ];
  const heap = new MinHeap();
  heap.push({ row: 0, col: 0, waterSoFar: grid[0][0] });
  while (heap.length > 0) {
    const current = heap.pop();
    if (current.waterSoFar > best[current.row][current.col]) {
      continue;
    }
    if (current.row === size - 1 && current.col === size - 1) {
      return current.waterSoFar;
    }
    for (const direction of directions) {
      const nextRow = current.row + direction[0];
      const nextCol = current.col + direction[1];
      if (nextRow < 0 || nextRow >= size || nextCol < 0 || nextCol >= size) {
        continue;
      }
      const maxAlongPath = Math.max(current.waterSoFar, grid[nextRow][nextCol]);
      if (maxAlongPath < best[nextRow][nextCol]) {
        best[nextRow][nextCol] = maxAlongPath;
        heap.push({ row: nextRow, col: nextCol, waterSoFar: maxAlongPath });
      }
    }
  }
  return -1;
}

Walkthrough

Grid [[0,2],[1,3]]: from (0,0) cost 0; to (0,1) cost max(0,2)=2; to (1,0) cost 1; from (1,0) to (1,1) cost max(1,3)=3. Alternative via (0,1) also yields minimax 3. Dijkstra pops states in order of increasing waterSoFar, so first arrival at destination is optimal.

Invariant: When a cell is first visited, waterSoFar is the minimum possible minimax value among all paths from start to that cell.

Edge Cases

n == 1 — answer is grid[0][0]
All cells equal — answer is that value
Monotone path along ridge — still handled by PQ order

Pitfalls

Using sum of heights instead of max along path
Eager mark visited: first pop sets minimax for that cell (Dijkstra with nonnegative edge costs in this semiring)

Variants

Binary search + BFS: check if path exists when only cells with grid[i][j] <= mid are passable.
K-th minimal threshold path: mergeable with persistent search or parametric flow.
3D or 8-neighbor grids: same Dijkstra; only neighbor enumeration changes.

Mind-Map Tags

#dijkstra #minimax-path #grid-graph #priority-queue #binary-search-on-answer