Pacific Atlantic Water Flow

📋

Pacific Atlantic Water Flow

Edge cases:

</>

IDE

def pacificAtlantic(heights: list[list[int]]) -> list[list[int]]:public List<List<Integer>> pacificAtlantic(int[][] heights)vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights)function pacificAtlantic(heights)

def pacificAtlantic(heights):
    # Write your solution here
    pass

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
using namespace std;

vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
    // Write your solution here
    return {};
}

function pacificAtlantic(heights) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: []Returning empty list for non-empty input due to missing initialization or incorrect DFS/BFS.✅ Initialize visited sets and start BFS/DFS from ocean edges, not from each cell.

Wrong: [[1,1]]Only returning cells reachable from one ocean, not both.✅ Compute reachability sets for both oceans separately and return their intersection.

Wrong: [[0,0],[0,1],[1,0]]Incorrect height comparison direction allowing flow only downhill, not reverse flow from oceans.✅ In BFS/DFS, move from ocean edges to neighbors with height >= current cell to simulate reverse flow.

Wrong: TLE or timeoutBrute force DFS from every cell causing O(m^2*n^2) complexity.✅ Use BFS/DFS starting from ocean edges to achieve O(m*n) complexity.

Wrong: Missing cells on edgesOff-by-one errors in ocean boundary initialization.✅ Include all top and left edges for Pacific, bottom and right edges for Atlantic in BFS/DFS start sets.

✓

Test Cases

Try testing your code on empty and minimal inputs to catch base case bugs.

Consider tricky height patterns that break greedy or naive approaches.

Large inputs require efficient O(m*n) BFS/DFS from ocean edges, not brute force.

t1_01basic

Input{"heights":[[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]}

Expected[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

⏱ Performance - must finish in 2000ms

Cells listed can flow water to both oceans following the height rules.

💡 Consider starting DFS/BFS from the ocean edges instead of each cell.

💡 Use two boolean matrices to track reachability to Pacific and Atlantic separately.

💡 Return cells reachable from both matrices by intersecting the sets.

Why it failed: Incorrect output means DFS/BFS logic or ocean boundary conditions are wrong. Fix by ensuring reverse flow from oceans and height comparison (next cell height >= current).

✓ Correctly identifies all cells that can flow to both oceans.

t1_02basic

Input{"heights":[[10,10,10],[10,1,10],[10,10,10]]}

Expected[[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]

⏱ Performance - must finish in 2000ms

All edge cells and those adjacent to edges except the low center cell can flow to both oceans.

💡 Check cells on edges first as they can always reach an ocean.

💡 Cells with lower height surrounded by higher ones may not reach both oceans.

💡 Use BFS/DFS from edges and mark reachable cells to find intersection.

Why it failed: Missing edge cells or including center cell means incorrect boundary or height checks. Fix by correctly initializing ocean reachability from edges and comparing heights properly.

✓ Correctly handles cells blocked by lower height neighbors.

t2_01edge

Input{"heights":[]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty matrix input returns empty list as no cells exist.

💡 Check for empty input before processing.

💡 Return empty list immediately if matrix or first row is empty.

💡 Avoid index errors by validating input size upfront.

Why it failed: Code crashes or returns non-empty output on empty input. Fix by adding input validation: if not heights or not heights[0]: return [].

✓ Handles empty input gracefully.

t2_02edge

Input{"heights":[[42]]}

Expected[[0,0]]

⏱ Performance - must finish in 2000ms

Single cell matrix can flow to both oceans as it touches all edges.

💡 Single cell is on all edges by definition.

💡 Check that your code handles 1x1 matrix correctly.

💡 Return that single cell as reachable to both oceans.

Why it failed: Fails to include single cell in output. Fix by ensuring edge conditions include single cell matrix.

✓ Correctly returns single cell for 1x1 matrix.

t2_03edge

Input{"heights":[[5,5,5],[5,5,5],[5,5,5]]}

Expected[[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]

⏱ Performance - must finish in 2000ms

All cells have same height, so water can flow freely to both oceans from any cell.

💡 When all heights are equal, water can flow in any direction.

💡 Check that your DFS/BFS does not block flow due to equal heights.

💡 All cells should be reachable from both oceans.

Why it failed: Excludes some cells due to strict height comparison (e.g. next height < current). Fix by allowing next height <= current height.

✓ Correctly includes all cells with equal heights.

t2_04edge

Input{"heights":[[1,2,3],[4,5,6],[7,8,9]]}

Expected[[0,0],[0,1],[0,2],[1,0],[2,0]]

⏱ Performance - must finish in 2000ms

Matrix with increasing heights from top-left to bottom-right; only cells near edges can flow to both oceans.

💡 Increasing heights restrict flow to edges only.

💡 Check that flow respects height constraints and ocean boundaries.

💡 Use BFS/DFS from edges to find reachable cells.

Why it failed: Incorrectly includes interior cells that cannot flow to both oceans. Fix by enforcing height and boundary conditions correctly.

✓ Correctly identifies only edge cells reachable to both oceans.

t3_01corner

Input{"heights":[[1,2,3],[8,9,4],[7,6,5]]}

Expected[[0,2],[1,2],[2,0],[2,1],[2,2]]

⏱ Performance - must finish in 2000ms

Greedy approach fails here; only certain cells can flow to both oceans due to height constraints.

💡 Greedy approach picking highest neighbors first can miss valid paths.

💡 Use BFS/DFS from oceans to find all reachable cells instead of greedy local decisions.

💡 Reverse flow approach ensures all valid paths are found.

Why it failed: Greedy approach returns incomplete set missing some reachable cells. Fix by using BFS/DFS from ocean edges instead of greedy local max.

✓ Correctly finds all cells reachable to both oceans despite tricky height gradients.

t3_02corner

Input{"heights":[[10,9,8,7],[11,10,9,6],[12,11,10,5],[13,12,11,4]]}

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

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack style and unbounded flow; flow must respect height constraints strictly.

💡 Do not confuse flow with unlimited moves ignoring height constraints.

💡 Each move must go to a cell with height <= current cell.

💡 Use BFS/DFS with proper height checks to avoid invalid paths.

Why it failed: Incorrectly includes cells that cannot flow due to ignoring height constraints. Fix by enforcing height[next] <= height[current] in traversal.

✓ Correctly respects height constraints in flow.

t3_03corner

Input{"heights":[[1,2,3,4],[2,3,4,5],[3,4,5,6],[4,5,6,7]]}

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

⏱ Performance - must finish in 2000ms

Tests off-by-one errors in boundary checks; only edge and some near-edge cells can flow to both oceans.

💡 Check your boundary conditions carefully for ocean edges.

💡 Ensure you include top and left edges for Pacific, bottom and right for Atlantic.

💡 Verify indices and ranges used in BFS/DFS initialization.

Why it failed: Misses cells on edges due to off-by-one errors in ocean boundary initialization. Fix by correctly including all top/left and bottom/right edge cells.

✓ Correctly includes all edge cells reachable to both oceans.

t4_01performance

Input{"heights":[[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99],[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100],[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101],[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102],[4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103],[5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104],[6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105],[7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106],[8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107],[9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, m=100 matrix with increasing heights; O(m*n) BFS/DFS must complete within 2 seconds.

💡 Brute force DFS from every cell is O(m^2*n^2) and will TLE.

💡 Use BFS/DFS starting from ocean edges to achieve O(m*n) complexity.

💡 Avoid repeated work by marking visited cells for each ocean.

Why it failed: TLE indicates brute force approach used. Fix by implementing BFS/DFS from ocean edges with memoization.

✓ Efficient O(m*n) solution confirmed by passing performance test.

Practice

1. Consider the following Python code implementing flood fill using DFS. Given the input image = [[1,1,1],[1,1,0],[1,0,1]], starting pixel (sr=1, sc=1), and newColor=2, what is the final image returned?

easy

A. [[1,1,1],[1,2,0],[1,0,1]]

B. [[2,2,2],[2,2,0],[2,0,2]]

C. [[2,2,2],[2,2,0],[2,0,1]]

D. [[2,2,2],[2,2,2],[2,2,2]]

Solution

1. Step 1: Trace dfs starting at (1,1) with original color=1

   The pixel at (1,1) is recolored to 2. Its neighbors with color 1 are (0,1), (2,1) is 0 so skipped, (1,0), and (1,2) is 0 skipped.

2. Step 2: Recursively recolor connected pixels with color 1

   All connected pixels with color 1 reachable from (1,1) are recolored to 2, resulting in [[2,2,2],[2,2,0],[2,0,1]]. The pixel at (2,2) remains 1 as it is not connected 4-directionally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Only connected pixels with original color changed [OK]

Hint: Trace DFS calls carefully to find connected pixels [OK]

Common Mistakes:

• Changing pixels diagonally connected
• Forgetting to check boundaries

2. Examine the following buggy code snippet for the optimal BFS approach. Which line contains the subtle bug that can cause incorrect results or infinite loops?

medium

A. Line that sets dist[nr][nc] = dist[r][c] + 1 without checking if dist[nr][nc] == -1

B. Line that initializes dist[r][c] = 0 for land cells

C. Line that appends initial land cells to the queue

D. Line that returns -1 if all cells are land or water

Solution

1. Step 1: Identify that updating dist[nr][nc] without checking if it was visited causes overwriting distances.

   This leads to revisiting cells multiple times, causing infinite loops or incorrect distances.

2. Step 2: The missing condition dist[nr][nc] == -1 before updating and enqueueing is the bug.

   Without it, BFS does not behave correctly as a shortest path search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Visited check prevents infinite loops and ensures correct distances [OK]

Hint: Always check if neighbor is unvisited before updating distance [OK]

Common Mistakes:

• Forgetting visited check causes infinite loops
• Misplacing initialization lines
• Incorrect early return conditions

3. What is the worst-case space complexity of the in-place DFS solution for the Number of Islands problem on an m x n grid, considering the recursion stack usage?

medium

A. O(1) -- since the grid is modified in-place, no extra space is needed.

B. O(min(m, n)) -- recursion depth limited by smaller grid dimension.

C. O(m*n) -- recursion stack can grow up to the size of the entire grid in worst case.

D. O(m + n) -- recursion stack limited by sum of rows and columns.

Solution

1. Step 1: Identify auxiliary space usage

   The grid is modified in-place, so no extra data structures are used except recursion stack.

2. Step 2: Analyze recursion stack depth

   In worst case (e.g., one large island), DFS can recurse over all cells, leading to recursion stack depth O(m*n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Recursion stack can be as large as all grid cells in worst case [OK]

Hint: Recursion stack can be as large as island size [OK]

Common Mistakes:

• Assuming constant space due to in-place modification
• Confusing recursion depth with grid dimensions

4. Suppose the graph nodes can be reused in multiple disconnected components, and the input to cloneGraph is a list of nodes representing multiple disconnected graphs. Which modification to the BFS-based cloneGraph algorithm correctly handles cloning all components without duplicating nodes or missing any?

hard

A. Initialize a global visited map and run BFS starting from each node in the list, skipping nodes already visited.

B. Run cloneGraph separately on each node in the list without tracking visited nodes globally.

C. Modify cloneGraph to clone only the first node and ignore others, assuming all are connected.

D. Use node values as keys in visited map to avoid revisiting nodes across components.

Solution

1. Step 1: Understand the problem with multiple disconnected components

   Cloning must cover all components without duplicating nodes shared across components.

2. Step 2: Modify BFS to handle multiple start nodes with global visited

   Use a global visited map and run BFS from each node in the input list, skipping nodes already cloned to avoid duplicates.

3. Step 3: Reject incorrect approaches

   Running cloneGraph separately without global visited causes duplicates; using node values as keys fails with duplicate values.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Global visited map prevents duplicates across components [OK]

Hint: Use global visited map when cloning multiple components [OK]

Common Mistakes:

• Running BFS separately without global visited causes duplicates
• Using node values as keys breaks cloning correctness

5. Suppose the problem changes: fresh oranges can become rotten multiple times, and rot can spread back to previously rotten oranges if it results in a faster rot time. Which modification to the DFS-based solution correctly handles this scenario?

hard

A. Switch to a brute force simulation updating the grid minute by minute until no changes

B. Keep the original DFS with pruning but run it multiple times until no updates occur

C. Use a multi-source BFS but do not track times, just mark visited once

D. Remove the pruning condition that skips DFS if time_grid[r][c] <= time, allowing revisits with better times

Solution

1. Step 1: Understand new rot dynamics

   Rot can improve previously recorded rot times, so pruning based on time_grid[r][c] <= time is invalid.

2. Step 2: Modify DFS to allow revisits with better times

   Removing pruning condition enables DFS to update time_grid when a faster rot path is found.

3. Step 3: Confirm correctness

   This ensures all cells have minimum rot times even if rot spreads back to previously rotten oranges.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing revisits with better times handles dynamic rot spread correctly [OK]

Hint: Allow revisits if they improve rot time [OK]

Common Mistakes:

• Keeping pruning causes stale times
• Using BFS without time tracking
• Brute force is inefficient