loading

Swim in Rising Water — Step-by-Step Visualization

hardLeetCode #778ArrayBinary SearchUnion FindHeap (Priority Queue)Matrix

You are given an `n x n` integer matrix `grid` where each value `grid[i][j]` represents the elevation at that point `(i, j)`. The rain starts to fall. At time `t`, the depth of the water everywhere is `t`. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most `t`. You start at the top left square `(0, 0)`. What is the least time until you can reach the bottom right square `(n - 1, n - 1)`?

Algorithm Pattern

Dijkstra's Algorithm (Min-Max Path)

Key Idea

This is a shortest path problem where the 'cost' of a path is defined as the maximum elevation encountered along it. We want to find a path from `(0, 0)` to `(n-1, n-1)` that minimizes this maximum elevation. Using Dijkstra with a min-priority queue allows us to always explore the lowest possible 'time' to reach any cell.

Step-by-Step Approach

  1. Initialize a min-heap with `[(grid[0][0], 0, 0)]` and a `visited` set.
  2. While the heap is not empty:
  3. Pop `(t, r, c)` - the lowest available time to explore a cell.
  4. If `(r, c)` is the bottom-right corner, return `t`.
  5. For each neighbor `(nr, nc)`:
  6. If not visited:
  7. Add `max(t, grid[nr][nc])` to the heap and mark as visited.

Common Gotchas

  • The time `t` at any neighbor is the maximum of the current time and that neighbor's elevation.
  • Ensure you use a priority queue to always get the minimum time available.

Related Problems

← All problems