This visualization was AI-generated and may contain inaccuracies. Please verify against the original LeetCode problem (#778) before relying on it.

Swim in Rising Water

An interactive visualization of Dijkstra's algorithm applied to finding the minimum time to swim from the top-left to the bottom-right corner of an elevation grid as water rises over time.

Shortest Path LeetCode 778 ↗ Hard

The Problem

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at position (i, j).

It starts raining at time t = 0. At time t, the depth of water everywhere is t. You can swim from a cell to any adjacent cell (up, down, left, right) if and only if the elevation of both cells is at most t. You can swim infinite distances in zero time — you just need the water level to be high enough.

Starting at (0, 0), find the minimum time t such that you can reach (n-1, n-1).

Interactive Visualization

Grid Values (rows on separate lines, comma-separated)

Preset

Speed:

Grid Visualization

Current Time / Water Level

processing

visited

in queue

flooded

optimal path

Priority Queue: empty

Code

fun swimInWater(grid: Array<IntArray>): Int {    val n = grid.size    val visited = mutableSetOf<Pair<Int,Int>>()    val pq = PriorityQueue(compareBy<Triple<Int,Int,Int>> { it.first })    pq.add(Triple(grid[0][0], 0, 0))    while (pq.isNotEmpty()) {        val (t, r, c) = pq.poll()        if (Pair(r, c) in visited)            continue        visited.add(Pair(r, c))        if (r == n - 1 && c == n - 1)            return t        for ((dr, dc) in listOf(-1 to 0, 1 to 0, 0 to -1, 0 to 1)) {            val nr = r + dr; val nc = c + dc            if (nr in 0 until n && nc in 0 until n) {                if (Pair(nr, nc) !in visited) {                    val newT = maxOf(t, grid[nr][nc])                    pq.add(Triple(newT, nr, nc))    } } } } return -1 }

def swimInWater(grid):    n = len(grid)    visited = set()    pq = [(grid[0][0], 0, 0)]    while pq:        t, r, c = heapq.heappop(pq)        if (r, c) in visited:            continue        visited.add((r, c))        if r == n - 1 and c == n - 1:            return t        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:            nr, nc = r + dr, c + dc            if 0 <= nr < n and 0 <= nc < n:                if (nr, nc) not in visited:                    new_t = max(t, grid[nr][nc])                    heapq.heappush(pq, (new_t, nr, nc))

Status

Press Step or Play to begin.

How It Works

Key Insight

This problem is equivalent to finding a path from (0, 0) to (n-1, n-1) that minimizes the maximum elevation along the path. We can model it as a shortest-path problem where the "cost" of reaching a cell is the maximum elevation encountered so far. Dijkstra's algorithm with a min-heap naturally explores cells in order of increasing cost, guaranteeing we find the optimal path first.

The Algorithm

Initialize: push (grid[0][0], 0, 0) onto the priority queue — we start at the top-left, and must wait at least until time equals the elevation there.
Pop minimum: extract the cell (t, r, c) with the smallest time t from the heap.
Skip visited: if (r, c) has already been visited, skip it.
Mark visited: add (r, c) to the visited set.
Check destination: if (r, c) is the bottom-right corner, return t — this is the minimum time.
Explore neighbors: for each unvisited neighbor (nr, nc), compute new_t = max(t, grid[nr][nc]) and push it onto the heap.
Why max? To reach (nr, nc) through (r, c), the water level must be at least t (to reach (r, c)) and at least grid[nr][nc] (to enter (nr, nc)). So the effective time is the maximum of the two.

Complexity

Time O(n² log n)

Space O(n²)

Each of the n² cells is pushed onto the heap at most 4 times (once per neighbor direction). Each heap operation takes O(log(n²)) = O(log n). The visited set and the heap together use O(n²) space.