AlgoMaster Logo

Swim in Rising Water

hardFrequency7 min readUpdated June 23, 2026

Understanding the Problem

This problem reduces to finding a path from the top-left corner to the bottom-right corner where the maximum elevation along the path is as small as possible. The "time" framing is a distraction. You can traverse a cell at time t only if its elevation is at most t, so the least time to reach the destination equals the maximum elevation on the best path from (0,0) to (n-1, n-1). Among all paths, the best one is the path whose tallest cell is the shortest.

This is a minimax path problem. The cost of a path is not the sum of its cells (as in shortest path) but the single highest cell on it, and we want to minimize that value over all paths.

Key Constraints:

  • 1 <= n <= 50 → The grid has at most 2,500 cells, small enough for an O(n^2 log n) solution.
  • 0 <= grid[i][j] < n^2 with all values unique → The elevations are a permutation of 0 to n^2-1. Since they are distinct and dense, we can map each elevation directly to its cell and process cells in elevation order without sorting. This drives the Union-Find approach.

Approach 1: Binary Search + BFS

Intuition

Checking a fixed answer is easy. Given a candidate value T, a path is reachable at time T if and only if there is a route from (0,0) to (n-1,n-1) using only cells with grid[i][j] <= T. That is a plain BFS reachability check.

Reachability is monotonic in T. If a path exists at time T, the same path exists at every T+1 and beyond, since raising the water level never removes a usable cell. So there is a single threshold below which no path exists and above which one always does, and that threshold is the answer. A monotonic yes/no predicate is the setup for binary search on the answer.

The search range runs from max(grid[0][0], grid[n-1][n-1]) (the start and end cells must be usable) up to n*n - 1 (the largest elevation). For each candidate T, run BFS to test feasibility.

Algorithm

  1. Set low = max(grid[0][0], grid[n-1][n-1]) and high = n * n - 1.
  2. While low < high:
    • Compute mid = (low + high) / 2.
    • Run BFS/DFS from (0,0), only visiting cells where grid[i][j] <= mid.
    • If (n-1, n-1) is reachable, set high = mid.
    • Otherwise, set low = mid + 1.
  3. Return low.

Example Walkthrough

1Grid: [[0,2],[1,3]]. low = max(0, 3) = 3, high = 3
0
1
0
0
2
1
1
3
1/3

Code

Binary search reruns a full BFS for every candidate threshold. The next approach finds the answer in a single traversal by always expanding the cell reachable with the smallest maximum elevation.

Approach 2: Modified Dijkstra's (Min-Heap)

Intuition

A priority queue solves this in one pass. The structure mirrors Dijkstra's algorithm, except the cost of a path is the maximum elevation along it rather than the sum of edge weights, so the heap key is that running maximum instead of a running sum.

Start at (0,0). The "distance" to any cell is the smallest possible maximum elevation on a path that reaches it. Each heap entry stores that running maximum together with the cell. When a neighbor (nr, nc) is reached from a cell whose path maximum is maxElev, the path maximum at the neighbor becomes max(maxElev, grid[nr][nc]). Always pop the entry with the smallest running maximum.

Algorithm

  1. Push (grid[0][0], 0, 0) onto a min-heap. Mark (0,0) as visited.
  2. While the heap is not empty:
    • Pop the cell (maxElevation, r, c) with the smallest max elevation.
    • If (r, c) is the destination (n-1, n-1), return maxElevation.
    • For each unvisited 4-directional neighbor (nr, nc):
      • Compute newMax = max(maxElevation, grid[nr][nc]).
      • Push (newMax, nr, nc) onto the heap and mark it visited.
  3. Return -1 (should never reach here for valid input).

Example Walkthrough

1Start: push (0, 0,0) to heap. Visited: {(0,0)}
0
1
0
0
2
1
1
3
1/5

Code

The heap adds a log factor to each cell. The next approach drops it by processing cells in elevation order and connecting each new cell to its processed neighbors until the start and end join the same component.

Approach 3: Union-Find (Optimal)

Intuition

Raise the water level from 0 to n^2-1. At each level exactly one new cell becomes available, because the elevations are distinct. The first level at which (0,0) and (n-1, n-1) belong to the same connected region of available cells is the answer.

Union-Find tracks those regions incrementally. Process cells in increasing elevation order. As each cell becomes available, union it with any of its four neighbors that are already available. After processing a cell, check whether the start and end share a root. The first elevation at which they do is the result. Because elevations form a dense permutation, the cell of a given elevation can be located in O(1) from a precomputed position array, so no separate sort is needed.

Algorithm

  1. Build a position array mapping each elevation t to its (row, col). Since elevations are a permutation of 0 to n^2-1, this replaces sorting.
  2. Initialize a Union-Find structure with n^2 elements.
  3. Create a boolean grid available initialized to all false.
  4. For t from 0 to n^2-1:
    • Look up (r, c) = position[t] and mark it available.
    • Union (r, c) with each adjacent cell that is already available.
    • If find(0) == find(n*n - 1), return t.
  5. Return n^2-1 as a fallback (always reached earlier for valid input).

Example Walkthrough

1Sorted cells: [(0,0,0), (1,1,0), (2,0,1), (3,1,1)]
0
1
0
0
2
1
1
3
1/6

Code