Swim in Rising Water

▶

Steps

setup

Initialize grid and union-find

We start by initializing the union-find data structure for all 4 cells (0 to 3) and creating a list of all cells with their elevations.

💡 Setting up union-find and the cell list is essential to track connectivity and process cells in elevation order.

Line:

n = len(grid)
uf = UnionFind(n * n)
cells = [(grid[i][j], i, j) for i in range(n) for j in range(n)]

💡 Union-find parent array is initialized to each node being its own parent, meaning no connections yet.

setup

Sort cells by elevation ascending

We sort the list of cells by their elevation values to process them from lowest to highest elevation.

💡 Sorting ensures we simulate water rising and cells becoming accessible in correct order.

Line:

cells.sort()

💡 Processing cells in elevation order allows union-find to connect accessible cells as water level rises.

fill_cells

Process cell (0,0) elevation 0

Mark cell (0,0) as visited and attempt to union with adjacent visited cells (none yet).

💡 Visiting the lowest elevation cell first starts the connectivity from the start point.

Line:

visited[x][y] = True
for dx, dy in directions:
  nx, ny = x + dx, y + dy
  if 0 <= nx < n and 0 <= ny < n and visited[nx][ny]:
    uf.union(index(x,y), index(nx, ny))

💡 No adjacent cells are visited yet, so no unions occur. Cell (0,0) is now accessible.

fill_cells

Process cell (1,0) elevation 1

Mark cell (1,0) as visited and union with adjacent visited cells. It is adjacent to (0,0) which is visited, so union occurs.

💡 Connecting newly accessible cell to previously visited cells builds the path incrementally.

Line:

visited[x][y] = True
for dx, dy in directions:
  nx, ny = x + dx, y + dy
  if 0 <= nx < n and 0 <= ny < n and visited[nx][ny]:
    uf.union(index(x,y), index(nx, ny))

💡 Union connects two accessible cells, expanding the connected component.

compare

Check connectivity after processing (1,0)

Check if start cell (0) and end cell (3) are connected in union-find. They are not connected yet.

💡 Connectivity check determines if a path exists at current water level.

Line:

if uf.find(0) == uf.find(n*n - 1):
  return elevation

💡 Even after connecting two cells, path to end is incomplete.

fill_cells

Process cell (0,1) elevation 2

Mark cell (0,1) as visited and union with adjacent visited cells. It is adjacent to (0,0) which is visited, so union occurs.

💡 Adding another accessible cell and connecting it expands the reachable area.

Line:

visited[x][y] = True
for dx, dy in directions:
  nx, ny = x + dx, y + dy
  if 0 <= nx < n and 0 <= ny < n and visited[nx][ny]:
    uf.union(index(x,y), index(nx, ny))

💡 Union connects cell (0,1) to the existing connected component.

compare

Check connectivity after processing (0,1)

Check if start cell (0) and end cell (3) are connected. They are still not connected.

💡 Connectivity check confirms path is still incomplete.

Line:

if uf.find(0) == uf.find(n*n - 1):
  return elevation

💡 Even with three connected cells, path to end cell is not complete.

fill_cells

Process cell (1,1) elevation 3

Mark cell (1,1) as visited and union with adjacent visited cells. It is adjacent to (1,0) and (0,1), both visited, so unions occur.

💡 Connecting the last cell completes the path from start to end.

Line:

visited[x][y] = True
for dx, dy in directions:
  nx, ny = x + dx, y + dy
  if 0 <= nx < n and 0 <= ny < n and visited[nx][ny]:
    uf.union(index(x,y), index(nx, ny))

💡 Multiple unions connect the last cell to the existing connected component.

compare

Check connectivity after processing (1,1)

Check if start cell (0) and end cell (3) are connected. They are now connected.

💡 Connectivity check confirms a path exists at elevation 3.

Line:

if uf.find(0) == uf.find(n*n - 1):
  return elevation

💡 The minimum time to swim across is the elevation of the last connected cell.

reconstruct

Return final answer

Return the elevation 3 as the minimum time to swim from top-left to bottom-right.

💡 This final step outputs the earliest time when the path is possible.

Line:

return elevation

💡 The answer corresponds to the highest elevation cell in the connected path.

from typing import List

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # STEP 1: Initialize parent array
        self.rank = [0] * n          # STEP 1: Initialize rank array

    def find(self, x):
        while self.parent[x] != x:  # STEP 4: Path compression loop
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)  # STEP 4: Find roots
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[ry] < self.rank[rx]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True


def swimInWater(grid: List[List[int]]) -> int:
    n = len(grid)  # STEP 1: Grid size
    uf = UnionFind(n * n)  # STEP 1: Initialize union-find
    cells = [(grid[i][j], i, j) for i in range(n) for j in range(n)]  # STEP 1: List all cells
    cells.sort()  # STEP 2: Sort cells by elevation ascending
    visited = [[False]*n for _ in range(n)]  # STEP 1: Visited matrix

    def index(x, y):
        return x * n + y

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

    for elevation, x, y in cells:  # STEP 3-9: Process cells in order
        visited[x][y] = True  # STEP 3: Mark cell visited
        for dx, dy in directions:  # STEP 4: Check neighbors
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n and visited[nx][ny]:
                uf.union(index(x,y), index(nx, ny))  # STEP 4: Union adjacent visited cells
        if uf.find(0) == uf.find(n*n - 1):  # STEP 5,7,9: Check connectivity
            return elevation  # STEP 10: Return answer

# Driver code
if __name__ == '__main__':
    grid = [[0,2],[1,3]]
    print(swimInWater(grid))  # Expected output: 3

📊

Swim in Rising Water - Watch the Algorithm Execute, Step by Step

Watching each union and connectivity check reveals how the algorithm incrementally builds paths as water rises, making the abstract union-find operations concrete.

Visiting: none

0

1

2

3

Visiting: none

0

2

1

3

Visiting: 0

0

2

1

3

Visiting: 2

Edge: 2 → 0

0

2

1

3

Visiting: 2

0

2

1

3

Visiting: 1

Edge: 1 → 0

0

2

1

3

Visiting: 1

0

2

1

3

Visiting: 3

Edge: 3 → 2

0

2

1

3

Visiting: 3

0

2

1

3

Visiting: none

0

2

1

3

Key Takeaways

✓ Union-Find efficiently tracks connectivity as cells become accessible in elevation order.

This insight is hard to see from code alone because union-find operations are abstract; watching unions happen stepwise clarifies how connectivity grows.

✓ Processing cells sorted by elevation simulates water rising and reveals the earliest time a path forms.

Seeing the order visually helps understand why sorting is critical and how it drives the algorithm's correctness.

✓ Connectivity checks after each union determine when the start and end become connected, signaling the answer.

The decision to stop when connected is subtle in code but clear when watching the connectivity state change in the visualization.

Practice

1. You are given an undirected, weighted graph and need to find a subset of edges that connects all vertices with the minimum possible total edge weight, without forming any cycles. Which algorithmic approach guarantees an optimal solution efficiently?

easy

A. Dynamic Programming on subsets of edges to find minimum cost spanning subgraph

B. Greedy algorithm sorting edges by weight and using union-find to avoid cycles

C. Depth-First Search to find all spanning trees and pick the minimum weight one

D. Breadth-First Search to find shortest paths and combine them into a spanning tree

Solution

1. Step 1: Understand the problem requirements

   The problem asks for a minimum total edge weight subset connecting all vertices without cycles, which is the definition of a Minimum Spanning Tree (MST).

2. Step 2: Identify the algorithm that guarantees optimal MST efficiently

   Kruskal's algorithm sorts edges by weight and uses union-find to avoid cycles, ensuring minimal total weight and connectivity efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Greedy + union-find is classic MST approach [OK]

Hint: MST needs cycle-free minimal edges; union-find + sorting fits [OK]

Common Mistakes:

• Thinking DFS or BFS can find MST optimally
• Assuming DP on subsets is efficient here
• Believing greedy without cycle checks works

2. What is the time complexity of the optimal union-find solution for the Most Stones Removed with Same Row or Column problem, given n stones?

medium

A. O(n α(n)) where α is the inverse Ackermann function, due to union-find operations

B. O(n^2) due to checking all pairs of stones

C. O(n log n) because of sorting stones by coordinates

D. O(n) since each stone is processed once without extra overhead

Solution

1. Step 1: Analyze union-find operations

   Each union/find operation runs in nearly O(1) amortized time, specifically O(α(n)) where α is inverse Ackermann.

2. Step 2: Count total operations

   We perform at most 2n find operations and n union operations, total O(n α(n)).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Union-find with path compression and rank -> O(n α(n)) [OK]

Hint: Union-find with path compression -> near-linear time [OK]

Common Mistakes:

• Assuming O(n^2) from brute force pairwise checks
• Confusing sorting complexity with union-find
• Ignoring inverse Ackermann function in complexity

3. What is the time complexity of the optimal DFS with adjacency list conversion approach for finding the number of provinces in an n x n connectivity matrix?

medium

A. O(n + e), where e is the number of edges

B. O(n log n), because of sorting neighbors during adjacency list creation

C. O(n^3), due to nested loops in DFS and adjacency list construction

D. O(n^2), because the adjacency matrix must be fully scanned

Solution

1. Step 1: Identify loops in adjacency list construction

   Constructing adjacency list requires scanning the entire n x n matrix, which is O(n^2).

2. Step 2: Analyze DFS traversal cost

   DFS visits each node and edge once. In worst case, edges can be O(n^2), so DFS is O(n + e) = O(n^2).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Overall time dominated by adjacency list construction and DFS traversal [OK]

Hint: Adjacency matrix scan dominates -> O(n^2) [OK]

Common Mistakes:

• Confusing adjacency list DFS as O(n+e) ignoring matrix scan
• Assuming sorting neighbors adds log factor

4. What is the time complexity of the optimal Union-Find algorithm with path compression and union by rank when finding the redundant connection in a graph with n edges?

medium

A. O(n²) because each union operation may traverse all nodes

B. O(n * α(n)) where α(n) is the inverse Ackermann function, nearly constant

C. O(n log n) due to sorting edges before union operations

D. O(n) because each edge is processed once without overhead

Solution

1. Step 1: Identify number of union/find operations

   There are n edges, each triggers at most one union and two finds.

2. Step 2: Analyze complexity of find with path compression and union by rank

   Each find/union operation runs in amortized O(α(n)) time, where α(n) is inverse Ackermann function, which grows extremely slowly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Union-Find with optimizations runs in near-linear time O(n * α(n)) [OK]

Hint: Inverse Ackermann function α(n) is almost constant [OK]

Common Mistakes:

• Assuming O(n²) due to nested loops
• Confusing sorting complexity with union-find
• Ignoring path compression benefits

5. Suppose the Accounts Merge problem is extended so that emails can be reused across multiple users (e.g., shared family emails). Which modification to the union-find approach correctly handles this scenario?

hard

A. Use a graph with edges between accounts and emails, then find connected components allowing multiple parents

B. Keep union-find as is; emails connected once belong to a single user

C. Modify union-find to allow multiple parents per node to represent shared emails

D. Assign emails to users greedily by first occurrence, ignoring overlaps

Solution

1. Step 1: Understand the new constraint

   Emails can belong to multiple users, so union-find's single parent per node model breaks down.

2. Step 2: Choose correct data structure

   A bipartite graph connecting accounts and emails with connected components allows shared emails without forcing merges.

3. Step 3: Evaluate other options

   Union-find cannot represent multiple parents; greedy assignment loses correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Graph approach models shared emails correctly [OK]

Hint: Union-find assumes disjoint sets; shared emails break this [OK]

Common Mistakes:

• Trying to modify union-find for multiple parents
• Ignoring shared emails and merging incorrectly