LeetCode 778 - Swim in Rising Water

LeetCode Problem 778

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Depth-First Search, Breadth-First Search, Union-Find, Heap (Priority Queue), Matrix

Solution

Problem Understanding

In this problem, we are given an n x n grid where each cell contains a unique integer representing its elevation. Rain begins falling, and the water level rises over time. At any time t, you are allowed to stand on or move through any cell whose elevation is less than or equal to t.

You start at the top-left corner (0, 0) and want to reach the bottom-right corner (n - 1, n - 1). Movement is allowed only in the four cardinal directions: up, down, left, and right.

The important detail is that movement itself takes no time. The only thing that matters is whether the current water level is high enough to make a path possible. Therefore, the question becomes:

What is the smallest elevation threshold such that there exists a connected path from the start to the destination?

The input is a square matrix with the following guarantees:

• 1 <= n <= 50, so the grid is relatively small.
• Every elevation value is unique.
• Elevations range from 0 to n^2 - 1.

The uniqueness guarantee is useful because it means elevations form a strict ordering. No two cells become available at the same time.

Several edge cases are important:

• A 1 x 1 grid means the start is already the destination.
• The destination might require waiting for a very large elevation value.
• A path with fewer steps is not necessarily better, because the answer depends on the maximum elevation along the path, not path length.
• Greedy movement toward smaller neighboring values can fail because a locally optimal choice may lead to a large unavoidable elevation later.

The key challenge is minimizing the maximum elevation encountered along a valid path.

Approaches

Brute Force Approach

A straightforward solution is to simulate time from 0 upward and repeatedly check whether the destination is reachable.

For each time t:

1. Treat all cells with elevation <= t as traversable.
2. Run a BFS or DFS from (0, 0).
3. If the destination is reachable, return t.

This works because eventually all cells become submerged, guaranteeing reachability.

However, this approach is inefficient because we may run a full graph traversal many times. Since elevations range up to n^2 - 1, we could potentially perform O(n^2) searches, each costing O(n^2).

That leads to a total complexity of O(n^4), which is unnecessarily expensive.

Key Insight

The important observation is that the answer is determined by the maximum elevation encountered along the chosen path.

Suppose we move through a path whose highest elevation is k. Then:

• We cannot traverse the path before time k.
• At time k, the entire path becomes available.

So the problem becomes:

Find a path from start to destination that minimizes the maximum cell value along the path.

This is extremely similar to Dijkstra’s algorithm.

In standard Dijkstra, the path cost is the sum of edge weights. Here, the path cost is instead:

maximum elevation seen so far

We always want to expand the currently best reachable state, meaning the state with the smallest maximum elevation encountered so far.

A min-heap is perfect for this.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^4)	O(n^2)	Try every time value and run BFS/DFS
Optimal	O(n^2 log n)	O(n^2)	Dijkstra-style traversal using a min-heap

Algorithm Walkthrough

Optimal Algorithm, Dijkstra with Min-Heap

1. Create a min-heap and insert the starting cell (0, 0).

The heap stores:

• Current maximum elevation needed to reach this cell
• Row index
• Column index

Initially, the required time is simply grid[0][0]. 2. Maintain a visited set or matrix.

Once a cell has been processed with the smallest possible maximum elevation, we do not need to revisit it. 3. Repeatedly remove the smallest element from the heap.

This gives us the currently reachable position with the minimum required water level. 4. If the popped cell is the destination, return its associated elevation value.

Because we always process states in increasing order of required time, the first time we reach the destination is guaranteed to be optimal. 5. Explore the four neighboring cells.

For each valid neighbor:

• Compute the new required time:

max(current_time, neighbor_elevation)

This represents the highest elevation encountered along the path. 6. Push unvisited neighbors into the heap.

Even if the neighbor itself is low, the path may already require a larger elevation because of earlier cells. 7. Continue until the destination is reached.

Why it works

The algorithm maintains the invariant that when a cell is removed from the min-heap, we have already found the minimum possible maximum elevation required to reach it.

This is the same correctness principle used in Dijkstra’s algorithm. Since heap order guarantees that lower-cost paths are processed first, the first time we reach the destination must correspond to the globally minimal maximum elevation.

Python Solution

from typing import List
import heapq

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        n = len(grid)

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        min_heap = [(grid[0][0], 0, 0)]

        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True

        while min_heap:
            current_time, row, col = heapq.heappop(min_heap)

            if row == n - 1 and col == n - 1:
                return current_time

            for dr, dc in directions:
                new_row = row + dr
                new_col = col + dc

                if (
                    0 <= new_row < n
                    and 0 <= new_col < n
                    and not visited[new_row][new_col]
                ):
                    visited[new_row][new_col] = True

                    next_time = max(
                        current_time,
                        grid[new_row][new_col]
                    )

                    heapq.heappush(
                        min_heap,
                        (next_time, new_row, new_col)
                    )

        return -1

The implementation begins by initializing a min-heap with the starting cell. The heap always prioritizes the position requiring the smallest water level.

The visited matrix prevents revisiting cells unnecessarily. Since Dijkstra guarantees optimality when a node is first processed, revisiting is not needed.

Inside the main loop, we repeatedly extract the best candidate from the heap. If the destination is reached, we immediately return the associated time because it is guaranteed to be minimal.

For each neighboring cell, we calculate the new path cost using:

max(current_time, grid[new_row][new_col])

This captures the highest elevation encountered along the path so far.

The algorithm continues expanding states in increasing order of required elevation until the destination is found.

Go Solution

package main

import (
	"container/heap"
)

type State struct {
	time int
	row  int
	col  int
}

type MinHeap []State

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].time < h[j].time
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(State))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)

	item := old[n-1]

	*h = old[:n-1]

	return item
}

func swimInWater(grid [][]int) int {
	n := len(grid)

	directions := [][]int{
		{1, 0},
		{-1, 0},
		{0, 1},
		{0, -1},
	}

	visited := make([][]bool, n)

	for i := 0; i < n; i++ {
		visited[i] = make([]bool, n)
	}

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	heap.Push(minHeap, State{
		time: grid[0][0],
		row:  0,
		col:  0,
	})

	visited[0][0] = true

	for minHeap.Len() > 0 {
		current := heap.Pop(minHeap).(State)

		if current.row == n-1 && current.col == n-1 {
			return current.time
		}

		for _, dir := range directions {
			newRow := current.row + dir[0]
			newCol := current.col + dir[1]

			if newRow >= 0 &&
				newRow < n &&
				newCol >= 0 &&
				newCol < n &&
				!visited[newRow][newCol] {

				visited[newRow][newCol] = true

				nextTime := current.time

				if grid[newRow][newCol] > nextTime {
					nextTime = grid[newRow][newCol]
				}

				heap.Push(minHeap, State{
					time: nextTime,
					row:  newRow,
					col:  newCol,
				})
			}
		}
	}

	return -1
}

The Go implementation mirrors the Python solution closely. Since Go does not provide a built-in priority queue, we implement one using the container/heap package.

The State struct stores the current required time and coordinates. The custom MinHeap type defines heap behavior through the required interface methods.

Go slices are used for the visited matrix and direction vectors. Integer overflow is not a concern because all elevation values are bounded by n^2, which is at most 2500.

Worked Examples

Example 1

grid = [
  [0, 2],
  [1, 3]
]

Initial heap:

Heap Contents
(0,0,0)

Format:

(time, row, col)

Step 1

Pop:

(0,0,0)

Neighbors:

• (1,0) → max(0,1) = 1
• (0,1) → max(0,2) = 2

Heap becomes:

Heap
(1,1,0)
(2,0,1)

Step 2

Pop:

(1,1,0)

Neighbor:

• (1,1) → max(1,3) = 3

Heap:

Heap
(2,0,1)
(3,1,1)

Step 3

Pop:

(2,0,1)

Neighbor (1,1) already visited.

Heap:

Heap
(3,1,1)

Step 4

Pop destination:

(3,1,1)

Answer:

3

Example 2

grid = [
  [0,1,2,3,4],
  [24,23,22,21,5],
  [12,13,14,15,16],
  [11,17,18,19,20],
  [10,9,8,7,6]
]

The algorithm gradually expands cells in increasing elevation order.

Important progression:

Current Cell	Required Time
(0,0)	0
(0,1)	1
(0,2)	2
(0,3)	3
(0,4)	4
(1,4)	5
(4,4) eventually	16

Even though some nearby cells have very high values like 24, the heap naturally avoids them because lower-cost paths exist.

The first time the destination is removed from the heap, the required elevation is 16, which is optimal.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2 log n)	Each cell enters the heap once, heap operations cost log(n^2)
Space	O(n^2)	Heap and visited matrix store up to all cells

The grid contains n^2 cells. Each cell is inserted into the heap at most once because we mark cells visited immediately when pushing them.

Heap operations take O(log(n^2)), which simplifies to O(log n).

Therefore, total complexity becomes:

O(n^2 log n)

The space complexity is dominated by the heap and visited matrix.

Test Cases

from typing import List

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        import heapq

        n = len(grid)

        heap = [(grid[0][0], 0, 0)]

        visited = [[False] * n for _ in range(n)]
        visited[0][0] = True

        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while heap:
            time, row, col = heapq.heappop(heap)

            if row == n - 1 and col == n - 1:
                return time

            for dr, dc in directions:
                nr = row + dr
                nc = col + dc

                if (
                    0 <= nr < n
                    and 0 <= nc < n
                    and not visited[nr][nc]
                ):
                    visited[nr][nc] = True

                    heapq.heappush(
                        heap,
                        (
                            max(time, grid[nr][nc]),
                            nr,
                            nc
                        )
                    )

        return -1

solution = Solution()

assert solution.swimInWater([[0, 2], [1, 3]]) == 3
# Basic example from prompt

assert solution.swimInWater([
    [0, 1, 2, 3, 4],
    [24, 23, 22, 21, 5],
    [12, 13, 14, 15, 16],
    [11, 17, 18, 19, 20],
    [10, 9, 8, 7, 6]
]) == 16
# Spiral path example

assert solution.swimInWater([[0]]) == 0
# Single cell grid

assert solution.swimInWater([
    [3, 2],
    [0, 1]
]) == 3
# Start cell determines answer

assert solution.swimInWater([
    [0, 100],
    [1, 2]
]) == 2
# Optimal path avoids high elevation

assert solution.swimInWater([
    [7, 34, 16],
    [12, 15, 0],
    [2, 3, 1]
]) == 15
# Path requires large middle elevation

assert solution.swimInWater([
    [0, 99, 100],
    [1, 2, 101],
    [3, 4, 5]
]) == 5
# Longer but lower elevation path

Test Summary

Test	Why
[[0,2],[1,3]]	Basic example validation
Spiral 5x5 grid	Confirms optimal path selection
[[0]]	Smallest possible input
High start elevation	Ensures answer includes start cell
Avoid large value	Verifies heap chooses safer route
Large middle barrier	Tests maximum elevation tracking
Longer low-cost route	Ensures shortest path is not assumed

Edge Cases

One important edge case is a 1 x 1 grid. In this scenario, the starting position is already the destination. A buggy implementation might still attempt traversal logic unnecessarily or fail due to missing neighbors. The provided implementation handles this naturally because the first heap pop immediately satisfies the destination condition.

Another important case occurs when the starting cell itself has a very large elevation. Since you begin standing on that cell, the water level must already be at least that elevation before any movement is possible. Some incorrect solutions forget to include the start cell in the maximum elevation calculation. Our implementation initializes the heap with grid[0][0], guaranteeing correctness.

A third tricky case happens when the shortest geometric path is not the optimal path. Since the objective is minimizing the maximum elevation encountered, a longer route may still be better if it avoids a large elevation spike. Breadth-first search alone would fail here because BFS minimizes step count, not path cost. Using a min-heap ordered by required elevation ensures the algorithm always prioritizes safer paths rather than shorter ones.