Pacific Atlantic Water Flow

▶

Steps

setup

Initialize grid dimensions and reachable matrices

Determine the grid size and create two matrices to track cells reachable from the Pacific and Atlantic oceans, initially all False.

💡 Setting up these matrices is crucial to mark which cells can be reached by water flowing from each ocean.

Line:

m, n = len(heights), len(heights[0])
pacific_reachable = [[False]*n for _ in range(m)]
atlantic_reachable = [[False]*n for _ in range(m)]

💡 We need separate tracking for each ocean to later find their intersection.

setup

Initialize Pacific and Atlantic queues with border cells

Add all cells on the Pacific (top row and left column) and Atlantic (bottom row and right column) borders to their respective BFS queues and mark them reachable.

💡 Starting BFS from ocean borders simulates water flowing inward from the oceans.

Line:

for i in range(m):
    pacific_queue.append((i, 0))
    atlantic_queue.append((i, n-1))
    pacific_reachable[i][0] = True
    atlantic_reachable[i][n-1] = True
for j in range(n):
    pacific_queue.append((0, j))
    atlantic_queue.append((m-1, j))
    pacific_reachable[0][j] = True
    atlantic_reachable[m-1][j] = True

💡 Border cells are trivially reachable from their respective oceans.

traverse

Start BFS for Pacific ocean: dequeue (0,0)

Dequeue cell (0,0) from Pacific queue to explore its neighbors for possible water flow.

💡 Processing this cell lets us find adjacent cells where water can flow uphill or on equal height.

Line:

r, c = queue.popleft()

💡 BFS explores neighbors only if they are higher or equal height to simulate water flowing uphill.

expand

Explore neighbors of (0,0) for Pacific BFS

Check neighbors of (0,0): (1,0) and (0,1). Both have heights >= 1, so mark reachable and enqueue if not already.

💡 Only neighbors with height >= current cell can be reached by water flowing uphill or flat.

Line:

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:
        reachable[nr][nc] = True
        queue.append((nr, nc))

💡 Water can flow from (0,0) to these neighbors, expanding the reachable area.

traverse

Start BFS for Atlantic ocean: dequeue (0,4)

Dequeue cell (0,4) from Atlantic queue to explore neighbors for water flow towards Atlantic ocean.

💡 Processing Atlantic BFS similarly explores reachable cells from Atlantic borders.

Line:

r, c = queue.popleft()

💡 BFS from Atlantic ocean expands inward from the right and bottom borders.

expand

Explore neighbors of (0,4) for Atlantic BFS

Check neighbors (0,3) and (1,4). Both have heights less than or equal to 5, so mark reachable and enqueue if not already.

💡 Neighbors must have height >= current cell to be reachable by water flowing uphill or flat.

Line:

for dr, dc in directions:
    nr, nc = r + dr, c + dc
    if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:
        reachable[nr][nc] = True
        queue.append((nr, nc))

💡 Only neighbors with height >= current cell are added to BFS queue.

traverse

Continue BFS for Pacific: dequeue (1,0)

Dequeue cell (1,0) from Pacific queue to explore neighbors for water flow.

💡 Processing next cell in Pacific BFS to expand reachable cells.

Line:

r, c = queue.popleft()

💡 BFS continues layer by layer from ocean borders.

expand

Explore neighbors of (1,0) for Pacific BFS

Neighbors (0,0), (2,0), (1,1) checked. (0,0) already visited. (2,0) height 2 < 3 no enqueue. (1,1) height 2 < 3 no enqueue.

💡 Only neighbors with height >= current cell are enqueued.

Line:

if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:

💡 BFS does not expand downhill, preserving water flow constraints.

traverse

Continue BFS for Atlantic: dequeue (3,4)

Dequeue cell (3,4) from Atlantic queue to explore neighbors for water flow.

💡 Processing next Atlantic cell to expand reachable area.

Line:

r, c = queue.popleft()

💡 Atlantic BFS explores inward from ocean borders similarly to Pacific BFS.

expand

Explore neighbors of (3,4) for Atlantic BFS

Neighbors (2,4), (3,3), (4,4) checked. (4,4) height 4 < 5 no enqueue. (3,3) height 4 < 5 no enqueue. (2,4) height 1 < 5 no enqueue.

💡 No neighbors meet height criteria to expand Atlantic BFS from (3,4).

Line:

if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:

💡 BFS expansion stops where neighbors are lower height.

traverse

Complete BFS for Pacific and Atlantic oceans

BFS completes for both oceans, marking all reachable cells in pacific_reachable and atlantic_reachable matrices.

💡 After BFS, we know which cells can flow to each ocean independently.

Line:

bfs(pacific_queue, pacific_reachable)
bfs(atlantic_queue, atlantic_reachable)

💡 Reachability matrices now fully represent water flow constraints.

prune

Find cells reachable from both oceans

Iterate over all cells and select those marked reachable in both pacific_reachable and atlantic_reachable matrices.

💡 Intersection of reachable sets gives cells where water can flow to both oceans.

Line:

for i in range(m):
    for j in range(n):
        if pacific_reachable[i][j] and atlantic_reachable[i][j]:
            result.append([i, j])

💡 Only cells reachable from both oceans satisfy the problem condition.

reconstruct

Return final result

Return the list of cells that can flow water to both Pacific and Atlantic oceans.

💡 This completes the algorithm by outputting the solution.

Line:

return result

💡 The problem is solved by BFS expansions and intersection of reachable sets.

from typing import List
from collections import deque

class Solution:
    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        if not heights or not heights[0]:
            return []
        m, n = len(heights), len(heights[0])  # STEP 1

        pacific_reachable = [[False]*n for _ in range(m)]  # STEP 1
        atlantic_reachable = [[False]*n for _ in range(m)]  # STEP 1

        pacific_queue = deque()  # STEP 2
        atlantic_queue = deque()  # STEP 2

        for i in range(m):  # STEP 2
            pacific_queue.append((i, 0))
            atlantic_queue.append((i, n-1))
            pacific_reachable[i][0] = True
            atlantic_reachable[i][n-1] = True
        for j in range(n):  # STEP 2
            pacific_queue.append((0, j))
            atlantic_queue.append((m-1, j))
            pacific_reachable[0][j] = True
            atlantic_reachable[m-1][j] = True

        def bfs(queue, reachable):  # STEP 3-11
            directions = [(1,0),(-1,0),(0,1),(0,-1)]
            while queue:
                r, c = queue.popleft()  # STEP 3,5,7,9
                for dr, dc in directions:  # STEP 4,6,8,10
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:
                        reachable[nr][nc] = True
                        queue.append((nr, nc))

        bfs(pacific_queue, pacific_reachable)  # STEP 11
        bfs(atlantic_queue, atlantic_reachable)  # STEP 11

        result = []  # STEP 12
        for i in range(m):
            for j in range(n):
                if pacific_reachable[i][j] and atlantic_reachable[i][j]:
                    result.append([i, j])
        return result  # STEP 13

📊

Pacific Atlantic Water Flow - Watch the Algorithm Execute, Step by Step

Watching the BFS expansions from both oceans simultaneously reveals how water flow constraints propagate through the grid, clarifying the problem intuitively.

Visiting: none

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

4,0

4,1

4,2

4,3

4,4

Visiting: none

0,0

0,1

0,2

0,3

0,4

1,0

1,1

1,2

1,3

1,4

2,0

2,1

2,2

2,3

2,4

3,0

3,1

3,2

3,3

3,4

4,0

4,1

4,2

4,3

4,4

Queue / Stack

0,01,02,03,04,00,10,20,30,41,42,43,44,4

Visiting: 0,0

0,0

0,1

1,0

1,1

0,2

0,3

0,4

1,4

2,4

3,0

4,0

4,4

Queue / Stack

1,02,03,04,00,10,20,30,41,42,43,44,4

Visiting: none

0,0

0,1

1,0

1,1

0,2

0,3

0,4

1,4

2,4

3,0

4,0

4,4

Queue / Stack

1,02,03,04,00,10,20,30,41,42,43,44,41,00,1

Visiting: 0,4

0,4

0,3

1,4

2,4

3,4

4,4

Queue / Stack

0,31,42,43,44,4

Visiting: none

0,4

3,4

0,3

1,4

2,4

4,4

Queue / Stack

0,31,42,43,44,43,4

Visiting: 1,0

1,0

0,1

2,0

1,1

Queue / Stack

2,03,04,00,10,20,30,41,42,43,44,41,00,1

Visiting: none

1,0

0,1

2,0

1,1

Queue / Stack

2,03,04,00,10,20,30,41,42,43,44,40,1

Visiting: 3,4

3,4

4,4

3,3

2,4

Queue / Stack

0,31,42,44,43,4

Visiting: none

3,4

4,4

0,3

1,4

2,4

Queue / Stack

0,31,42,44,4

Visiting: none

0,4

1,3

1,4

2,2

3,0

3,1

4,0

Visiting: none

0,4

1,3

1,4

2,2

3,0

3,1

4,0

Key Takeaways

✓ BFS from ocean borders simulates water flowing uphill or flat, revealing reachable cells.

This insight is hard to see from code alone because the BFS direction and height condition interplay is subtle.

✓ Separate BFS traversals for Pacific and Atlantic oceans allow independent reachability marking.

Visualizing two BFS queues clarifies how the algorithm finds intersections of reachable cells.

✓ Only neighbors with height >= current cell are enqueued, enforcing water flow constraints.

Seeing BFS prune neighbors based on height helps understand why some paths are blocked.

Practice

1. Consider the following Python code for checking if a graph is a valid tree. What is the return value when calling valid_tree(4, [[0,1],[1,2],[2,3]])?

easy

A. true

B. false

C. Raises an exception

D. Returns null

Solution

1. Step 1: Check edge count

   Edges count is 3, nodes count is 4, so edges == n-1 condition passes.

2. Step 2: BFS traversal and cycle detection

   Starting from node 0, BFS visits nodes 0,1,2,3 without revisiting any node or detecting cycles. All nodes are visited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph is connected and acyclic, so valid tree [OK]

Hint: Edges must be n-1 and BFS visits all nodes [OK]

Common Mistakes:

• Confusing cycle detection with revisiting parent
• Forgetting to check all nodes visited

2. Consider the following BFS-based code snippet for finding the max area of an island in a grid. Given the input grid below, what is the final returned max area?

grid = [
  [0,1,0],
  [1,1,0],
  [0,0,1]
]

from collections import deque

def maxAreaOfIsland(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()
    max_area = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and (r, c) not in visited:
                queue = deque([(r, c)])
                area = 0
                while queue:
                    row, col = queue.popleft()
                    if (row, col) in visited:
                        continue
                    visited.add((row, col))
                    area += 1
                    for nr, nc in [(row+1,col),(row-1,col),(row,col+1),(row,col-1)]:
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in visited:
                            queue.append((nr, nc))
                max_area = max(max_area, area)
    return max_area

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace BFS starting at (0,1)

   Queue starts with (0,1). Visit (0,1), area=1. Add neighbors (1,1) and (0,0) is water, (0,2) water, (-1,1) invalid. Next visit (1,1), area=2. Add neighbors (2,1) water, (0,1) visited, (1,2) water, (1,0) land and not visited -> add (1,0). Next visit (1,0), area=3. Add neighbors (2,0) water, (0,0) water, (1,1) visited, (1,-1) invalid.

2. Step 2: BFS ends with area=3 for first island. Next island at (2,2) alone area=1. Max area = max(3,1) = 3

   But note (0,1), (1,1), (1,0) are connected forming area 3.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Largest connected island has 3 cells [OK]

Hint: Trace BFS queue expansions carefully [OK]

Common Mistakes:

• Counting diagonal neighbors
• Double counting visited cells
• Off-by-one in area increment

3. What is the time complexity of the optimal Dijkstra-based algorithm for finding the cheapest flight within K stops, given n cities and E flights? Assume the graph is represented as adjacency lists and a min-heap is used. A) O(n^2) because we may visit all nodes multiple times. B) O(E log E) because each edge can be pushed into the heap once. C) O(n log n) because Dijkstra runs in that time on sparse graphs. D) O(K * E) because we relax edges up to K times.

medium

A. O(n^2) because we may visit all nodes multiple times.

B. O(K * E) because we relax edges up to K times.

C. O(E log E) because each edge can be pushed into the heap once.

D. O(n log n) because Dijkstra runs in that time on sparse graphs.

Solution

1. Step 1: Identify heap operations

   Each edge can be pushed into the heap at most once per stops count, but stops ≤ K limits pushes. The heap size is bounded by O(E).

2. Step 2: Analyze complexity

   Each push/pop operation costs O(log E), so total time is O(E log E). The stops constraint prevents exponential blowup.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Heap operations dominate; stops limit expansions [OK]

Hint: Heap operations on edges dominate complexity [OK]

Common Mistakes:

• Assuming O(n^2) from classic Dijkstra on adjacency matrix
• Ignoring that stops limit expansions
• Confusing Bellman-Ford complexity with this approach

4. Examine the following buggy code snippet for the minimum effort path problem. Which line contains the subtle bug that can cause incorrect results or inefficiency?

medium

A. Line initializing dist with infinity values

B. Line checking if effort > dist[r][c] to skip outdated entries

C. Line calculating next_effort using sum of efforts instead of max

D. Line pushing new effort and coordinates into the heap

Solution

1. Step 1: Identify cost calculation

   The problem requires minimizing the maximum edge effort, but the code sums efforts, which is incorrect.

2. Step 2: Understand impact

   Summing efforts leads to wrong path cost and incorrect minimal effort path.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Replacing sum with max fixes correctness [OK]

Hint: Min effort = max edge, not sum [OK]

Common Mistakes:

• Using sum instead of max for effort
• Skipping heap entries incorrectly
• Misinitializing dist array

5. Suppose the problem is modified so that land cells can appear or disappear dynamically, and you need to efficiently update the maximum distance after each change. Which approach best supports efficient incremental updates?

hard

A. Use DFS from each water cell to find nearest land after each update.

B. Re-run the multi-source BFS from scratch after each update to recompute distances.

C. Use a dynamic BFS that updates distances only for affected cells using a queue of changed cells.

D. Precompute all distances once and answer queries without updates.

Solution

1. Step 1: Re-running BFS from scratch after each update is too costly for frequent updates.

   DFS is inefficient and does not guarantee shortest paths.

2. Step 2: Dynamic BFS updates distances only for cells affected by land changes, efficiently maintaining correct distances.

   Precomputing once fails to handle updates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Incremental BFS updates only affected cells after changes [OK]

Hint: Incremental BFS updates only affected cells after changes [OK]

Common Mistakes:

• Recomputing entire BFS each update
• Using DFS for shortest path
• Ignoring updates after precomputation