Problem Description

You have an n x n grid where each cell contains an integer representing the elevation at that position. When it starts raining, the water level rises uniformly over time. At any time t, the water level is at height t, which means any cell with elevation ≤ t becomes submerged (accessible for swimming).

You start at the top-left corner (0, 0) and want to reach the bottom-right corner (n-1, n-1). You can swim from one cell to any of its 4 adjacent cells (up, down, left, right) only if both cells have elevations ≤ t at time t. Swimming takes no time - you can travel infinite distances instantly as long as the cells are accessible.

The goal is to find the minimum time t at which you can swim from the starting position to the ending position. In other words, what's the smallest water level needed so that there exists a valid path from (0, 0) to (n-1, n-1) where all cells along the path are submerged?

For example, if you have a 2x2 grid:

[[0, 2],
 [1, 3]]

At time t = 3, all cells are submerged (have elevation ≤ 3), allowing you to swim from (0,0) to (1,1). The answer would be 3 since you need to wait until the water reaches level 3 to have a complete path.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves an n×n grid where we need to find a path from one cell to another. Each cell can be considered a node, and the 4-directional adjacency represents edges. The water level constraint determines which edges are traversable at time t.

Is it a tree?

• No: The grid structure has cycles (you can move in 4 directions and potentially return to the same cell), so it's not a tree structure.

Is the problem related to directed acyclic graphs?

• No: The grid allows bidirectional movement between adjacent cells, and cycles are possible, so it's not a DAG.

Is the problem related to shortest paths?

• No: We're not looking for the shortest path in terms of distance. Instead, we're looking for the minimum time (water level) that allows any valid path to exist from start to end.

Does the problem involve connectivity?

• Yes: The core question is about connectivity - at what minimum water level do the start and end positions become connected through submerged cells? We need to determine when cells with elevation ≤ t form a connected component containing both (0,0) and (n-1, n-1).

Disjoint Set Union

• Yes: The flowchart leads us to DSU (Disjoint Set Union), which is exactly what the solution uses. The algorithm processes cells in order of increasing elevation (time), unions adjacent submerged cells, and checks when the start and end positions belong to the same connected component.

Conclusion: The flowchart correctly identifies this as a connectivity problem best solved with Disjoint Set Union. While DFS could be used (by trying different water levels and checking connectivity), DSU is more efficient as it incrementally builds connected components as the water rises.

Intuition

Think about what happens as the water level rises from 0 to higher values. Initially, at time t = 0, only cells with elevation 0 are accessible. As time increases to t = 1, cells with elevation ≤ 1 become accessible, and so on.

The key insight is that we're looking for the exact moment when a path first becomes available from start to end. Before this critical time, the start and end positions are in separate "islands" of accessible cells. At the critical time, these islands merge into one connected region.

This naturally leads to a Union-Find (Disjoint Set Union) approach. We can simulate the water rising by processing cells in order of their elevation. For each elevation level:

1. The cell at that elevation becomes "active" (submerged)
2. We check its 4 neighbors - if they're already submerged (elevation ≤ current time), we unite them into the same connected component
3. After each union operation, we check if the start (0, 0) and end (n-1, n-1) are now in the same connected component

The moment they become connected is our answer - that's the minimum water level needed.

Why is this more efficient than trying different water levels with DFS? Instead of repeatedly checking connectivity at different water levels (which would involve multiple graph traversals), we build the connectivity incrementally. We process each cell exactly once in elevation order, and union operations are nearly constant time with path compression. This gives us an elegant O(n² log n) solution (dominated by sorting if needed) or O(n²) if we process elevations from 0 to n²-1 in order.

The solution cleverly uses the array hi to map each elevation value to its position in the grid, allowing us to process cells in the exact order they become submerged.

Learn more about Depth-First Search, Breadth-First Search, Union Find, Binary Search and Heap (Priority Queue) patterns.

Solution Approach

The implementation uses Union-Find (Disjoint Set Union) to efficiently track when the start and end positions become connected as the water level rises.

Data Structures:

• p: Parent array for Union-Find, where p[i] stores the parent of node i. Initially, each cell is its own parent.
• hi: Maps each elevation value to its flattened grid position. Since elevations range from 0 to n²-1, hi[elevation] = row * n + col.

Algorithm Steps:

1. Initialize Union-Find structure:

   • Create parent array p where each cell (flattened to 1D index) is initially its own parent
   • A cell at position (i, j) is mapped to index i * n + j

2. Build elevation-to-position mapping:

   for i, row in enumerate(grid):
       for j, h in enumerate(row):
           hi[h] = i * n + j

   This allows us to process cells in order of increasing elevation.

3. Process cells by increasing elevation (time):

   for t in range(n * n):
       i, j = hi[t] // n, hi[t] % n

   At time t, the cell with elevation t becomes active. We extract its 2D coordinates from the flattened index.

4. Union with adjacent submerged cells:

   • For each of the 4 adjacent cells (x, y):
     • Check if it's within bounds and already submerged (grid[x][y] <= t)
     • If yes, union it with the current cell using p[find(x * n + y)] = find(hi[t])

5. Check connectivity:

   • After each union operation, check if find(0) == find(n * n - 1)
   • If the start (index 0) and end (index n²-1) are in the same component, return current time t

Find function with path compression:

def find(x):
    if p[x] != x:
        p[x] = find(p[x])  # Path compression
    return p[x]

The algorithm guarantees we find the minimum time because we process cells in strictly increasing order of elevation. The first moment the start and end become connected is the minimum water level needed for a valid path to exist.

Time Complexity: O(n² × α(n²)) where α is the inverse Ackermann function, practically O(n²) Space Complexity: O(n²) for the parent array and elevation mapping

Example Walkthrough

Let's walk through a small 3x3 grid example to illustrate the solution approach:

Grid:
[[0, 6, 7],
 [2, 8, 1],
 [3, 4, 5]]

Step 1: Initialize Union-Find

• Create parent array p where each cell is its own parent
• p = [0, 1, 2, 3, 4, 5, 6, 7, 8] (each index points to itself)
• Flattened indices: (0,0)→0, (0,1)→1, (0,2)→2, (1,0)→3, (1,1)→4, (1,2)→5, (2,0)→6, (2,1)→7, (2,2)→8

Step 2: Build elevation-to-position mapping

hi[0] = 0 (position 0,0)
hi[1] = 5 (position 1,2)
hi[2] = 3 (position 1,0)
hi[3] = 6 (position 2,0)
hi[4] = 7 (position 2,1)
hi[5] = 8 (position 2,2)
hi[6] = 1 (position 0,1)
hi[7] = 2 (position 0,2)
hi[8] = 4 (position 1,1)

Step 3: Process cells by increasing elevation

Time t=0: Cell (0,0) with elevation 0 becomes active

• Check neighbors: No neighbors are submerged yet
• Components: {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}
• Start (0) and end (8) not connected

Time t=1: Cell (1,2) with elevation 1 becomes active

• Check neighbors: No neighbors are submerged yet
• Components: {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}
• Start (0) and end (8) not connected

Time t=2: Cell (1,0) with elevation 2 becomes active

• Check neighbor (0,0): elevation 0 ≤ 2, so union them
• Union operation: p[find(3)] = find(0) → Components merge
• Components: {0,3}, {1}, {2}, {4}, {5}, {6}, {7}, {8}
• Start (0) and end (8) not connected

Time t=3: Cell (2,0) with elevation 3 becomes active

• Check neighbor (1,0): elevation 2 ≤ 3, so union them
• Union operation: p[find(6)] = find(3) → Components merge
• Components: {0,3,6}, {1}, {2}, {4}, {5}, {7}, {8}
• Start (0) and end (8) not connected

Time t=4: Cell (2,1) with elevation 4 becomes active

• Check neighbor (2,0): elevation 3 ≤ 4, so union them
• Union operation: p[find(7)] = find(6) → Components merge
• Components: {0,3,6,7}, {1}, {2}, {4}, {5}, {8}
• Start (0) and end (8) not connected

Time t=5: Cell (2,2) with elevation 5 becomes active

• Check neighbor (2,1): elevation 4 ≤ 5, so union them
• Check neighbor (1,2): elevation 1 ≤ 5, so union them
• Union operations merge components
• Components: {0,3,6,7,8,5}, {1}, {2}, {4}
• Start (0) and end (8) are now connected!
• Return t=5

The minimum water level needed is 5. At this level, we can swim from (0,0) → (1,0) → (2,0) → (2,1) → (2,2), forming a valid path where all cells have elevation ≤ 5.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n² × α(n²)) where n is the dimension of the grid and α is the inverse Ackermann function.

• Creating the position mapping array hi takes O(n²) time as we iterate through all grid cells
• The main loop runs for at most n² iterations (from t = 0 to t = n² - 1)
• In each iteration, we check 4 neighbors, performing at most 4 union operations
• Each union operation involves two find operations, which take O(α(n²)) amortized time with path compression
• The condition check find(0) == find(n * n - 1) also involves two find operations
• Total: O(n²) + O(n² × 4 × α(n²)) = O(n² × α(n²))

Since α(n²) grows extremely slowly and is effectively constant for all practical values, the time complexity can be considered O(n²) for practical purposes.

Space Complexity: O(n²)

• The parent array p stores n² elements: O(n²)
• The height-to-position mapping array hi stores n² elements: O(n²)
• The recursion stack for find operations can go up to O(n²) depth in the worst case before path compression, but with path compression it becomes O(log(n²)) = O(log n)
• Total: O(n²) + O(n²) + O(log n) = O(n²)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Union Operation Without Find

A critical mistake is performing union operations without properly using the find function to get the root representatives:

Incorrect:

# Wrong: directly assigning parents without finding roots
parent[neighbor_idx] = current_cell_idx

Correct:

# Correct: union the roots of both sets
parent[find(neighbor_idx)] = find(current_cell_idx)

Without using find, you're not actually merging the entire connected components but just reassigning individual nodes, which breaks the Union-Find structure.

2. Checking Connectivity at Wrong Time

The connectivity check is placed inside the neighbor loop, which causes premature termination:

Issue: The check happens after each individual union operation rather than after processing all neighbors of the current cell. This could theoretically return an incorrect result if the path requires multiple unions at the same time level.

Solution: Move the connectivity check outside the neighbor loop:

for time in range(n * n):
    current_cell_idx = elevation_to_position[time]
    current_row = current_cell_idx // n
    current_col = current_cell_idx % n
  
    # Process all neighbors first
    for delta_row, delta_col in directions:
        neighbor_row = current_row + delta_row
        neighbor_col = current_col + delta_col
      
        if (0 <= neighbor_row < n and 
            0 <= neighbor_col < n and 
            grid[neighbor_row][neighbor_col] <= time):
            neighbor_idx = neighbor_row * n + neighbor_col
            parent[find(neighbor_idx)] = find(current_cell_idx)
  
    # Then check connectivity once after all unions
    if find(0) == find(n * n - 1):
        return time

3. Confusion Between Elevation Values and Time

The problem states elevations are unique and range from 0 to n²-1, which conveniently matches the time progression. However, if the elevation values were arbitrary (not necessarily 0 to n²-1), the current approach would fail.

More Robust Solution for Arbitrary Elevations:

# Sort all cells by elevation
cells = []
for i in range(n):
    for j in range(n):
        cells.append((grid[i][j], i, j))
cells.sort()

# Process in order of increasing elevation
for elevation, row, col in cells:
    # Union with already-processed neighbors
    for dr, dc in directions:
        nr, nc = row + dr, col + dc
        if (0 <= nr < n and 0 <= nc < n and 
            grid[nr][nc] <= elevation):
            # Union operation
            parent[find(nr * n + nc)] = find(row * n + col)
  
    # Check connectivity
    if find(0) == find(n * n - 1):
        return elevation

4. Missing Path Compression Optimization

While the find function includes path compression, ensure it's consistently applied. Without it, the find operation could degrade to O(n) in worst case, making the overall complexity O(n³).

Always use path compression:

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # Compress path
    return parent[x]