Facebook Pixel

417. Pacific Atlantic Water Flow

Problem Description

You're given an m x n matrix representing an island where each cell contains a height value. The island is surrounded by two oceans:

  • Pacific Ocean: touches the left and top edges of the island
  • Atlantic Ocean: touches the right and bottom edges of the island

When it rains on the island, water flows from each cell to neighboring cells (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height. Water that reaches cells adjacent to an ocean flows into that ocean.

Your task is to find all cells from which rainwater can flow to both the Pacific Ocean AND the Atlantic Ocean. Return these cells as a list of coordinates [r, c].

Key Points:

  • Water flows from higher or equal height to lower or equal height cells
  • Water can move in 4 directions: up, down, left, right
  • A cell must be able to reach both oceans (not just one) to be included in the result
  • Cells on the edges are directly adjacent to their respective oceans

Example visualization: If we have a 5ร—5 island, the Pacific Ocean borders are at row 0 and column 0, while the Atlantic Ocean borders are at row 4 and column 4. Water from a cell in the middle needs to find paths to both ocean boundaries following the height rules.

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 a grid where each cell can be connected to its neighbors (up, down, left, right). Water flows between cells based on height relationships, creating edges between nodes (cells). This is essentially a graph traversal problem.

Is it a tree?

  • No: The grid structure with multiple possible paths and potential cycles (water can flow in circles if heights allow) means this is not a tree structure.

Is the problem related to directed acyclic graphs?

  • No: While water flow creates directed edges (from higher/equal to lower/equal heights), the problem isn't about DAG properties like topological ordering. We need to find cells that can reach both oceans.

Is the problem related to shortest paths?

  • No: We don't need to find the shortest path to the oceans. We only need to determine if water can reach both oceans from a given cell, regardless of path length.

Does the problem involve connectivity?

  • Yes: The core of the problem is about connectivity - determining which cells are connected to both the Pacific and Atlantic oceans through valid water flow paths.

Does the problem have small constraints?

  • Yes: The constraints are typically manageable (m ร— n grid with reasonable dimensions), allowing for traversal-based approaches.

DFS/backtracking?

  • Yes: DFS is perfect for exploring all possible flow paths from ocean boundaries inward, marking all reachable cells.

Conclusion: The flowchart suggests using DFS (Depth-First Search) to solve this problem. The solution uses DFS (implemented as BFS in the provided code) to traverse from ocean boundaries inward, finding all cells reachable from each ocean, then returning the intersection of these two sets.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to reverse our thinking. Instead of checking if water from each cell can reach both oceans (which would be inefficient), we ask: "Which cells can be reached FROM each ocean?"

Think about it this way: if water can flow from cell A to the ocean, then we can also trace backwards from the ocean to cell A by going uphill or staying at the same level. This reverse approach is much more efficient.

Here's the thought process:

  1. Start from the ocean boundaries: We know cells touching the Pacific (top/left edges) can definitely reach the Pacific. Similarly, cells touching the Atlantic (bottom/right edges) can reach the Atlantic.

  2. Flow backwards: From these boundary cells, we can "flow uphill" - moving to neighboring cells with heights greater than or equal to the current cell. This simulates the reverse of water flowing downhill.

  3. Mark reachable cells: As we traverse from each ocean, we mark all cells that can be reached. This gives us two sets:

    • Set 1: All cells that can reach the Pacific Ocean
    • Set 2: All cells that can reach the Atlantic Ocean
  4. Find the intersection: The answer is simply the cells that appear in both sets - these are the cells from which water can flow to both oceans.

Why is this approach better? Instead of doing a traversal from each of the m ร— n cells to check if they can reach both oceans (which would be O(m ร— n ร— (m + n))), we only do two traversals starting from the ocean boundaries. This reduces our complexity significantly.

The beauty of this solution lies in recognizing that water flow is reversible in terms of reachability - if water can flow from A to B (going downhill), then we can trace from B to A (going uphill).

Solution Approach

The implementation uses BFS (Breadth-First Search) to execute our reverse-flow strategy. Here's how the solution works:

1. Initialize Data Structures:

  • Two sets vis1 and vis2 to track cells reachable from Pacific and Atlantic oceans respectively
  • Two queues q1 and q2 for BFS traversal from each ocean
  • Variables m and n store the dimensions of the grid

2. Identify Ocean Boundaries:

for i in range(m):
    for j in range(n):
        if i == 0 or j == 0:  # Pacific Ocean (top and left edges)
            vis1.add((i, j))
            q1.append((i, j))
        if i == m - 1 or j == n - 1:  # Atlantic Ocean (bottom and right edges)
            vis2.add((i, j))
            q2.append((i, j))
  • Cells on row 0 or column 0 touch the Pacific Ocean
  • Cells on row m-1 or column n-1 touch the Atlantic Ocean
  • These boundary cells are added to their respective queues and marked as visited

3. BFS Traversal Function:

def bfs(q, vis):
    while q:
        for _ in range(len(q)):
            i, j = q.popleft()
            for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:  # 4 directions
                x, y = i + a, j + b
                if (0 <= x < m and 0 <= y < n and 
                    (x, y) not in vis and 
                    heights[x][y] >= heights[i][j]):  # Can flow "uphill"
                    vis.add((x, y))
                    q.append((x, y))
  • For each cell in the queue, check all 4 neighboring cells
  • The key condition: heights[x][y] >= heights[i][j] - we can move to cells with equal or greater height (reverse flow)
  • If a valid unvisited cell is found, mark it as visited and add to queue

4. Execute BFS from Both Oceans:

bfs(q1, vis1)  # Find all cells reachable from Pacific
bfs(q2, vis2)  # Find all cells reachable from Atlantic

5. Find Intersection:

return [(i, j) for i in range(m) for j in range(n) 
        if (i, j) in vis1 and (i, j) in vis2]
  • Return cells that exist in both vis1 and vis2
  • These are the cells from which water can flow to both oceans

Time Complexity: O(m ร— n) - Each cell is visited at most twice (once from each ocean)

Space Complexity: O(m ร— n) - For the visited sets and queues in worst case

The algorithm elegantly solves the problem by reversing the flow direction and using set intersection to find cells connected to both oceans.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small 3ร—3 example to illustrate the solution approach:

heights = [[3, 3, 5],
           [3, 1, 3],
           [0, 2, 4]]

Step 1: Identify Ocean Boundaries

Pacific Ocean touches:

  • Top row: (0,0), (0,1), (0,2)
  • Left column: (0,0), (1,0), (2,0)

Atlantic Ocean touches:

  • Bottom row: (2,0), (2,1), (2,2)
  • Right column: (0,2), (1,2), (2,2)

Initial state:

  • vis1 (Pacific): {(0,0), (0,1), (0,2), (1,0), (2,0)}
  • vis2 (Atlantic): {(2,0), (2,1), (2,2), (0,2), (1,2)}

Step 2: BFS from Pacific Ocean (reverse flow - going uphill)

Starting from Pacific boundaries, we can reach cells with height โ‰ฅ current:

From (0,0) with height 3:

  • Check (1,0): height 3 โ‰ฅ 3 โœ“ (already in vis1)
  • Check (0,1): height 3 โ‰ฅ 3 โœ“ (already in vis1)

From (0,1) with height 3:

  • Check (1,1): height 1 < 3 โœ— (can't go there)

From (0,2) with height 5:

  • Check (1,2): height 3 < 5 โœ— (can't go there)

From (1,0) with height 3:

  • Check (1,1): height 1 < 3 โœ— (can't go there)

From (2,0) with height 0:

  • Check (2,1): height 2 โ‰ฅ 0 โœ“ (add to vis1)

After processing (2,1) with height 2:

  • Check (1,1): height 1 < 2 โœ— (can't go there)
  • Check (2,2): height 4 โ‰ฅ 2 โœ“ (add to vis1)

Final vis1: {(0,0), (0,1), (0,2), (1,0), (2,0), (2,1), (2,2)}

Step 3: BFS from Atlantic Ocean (reverse flow - going uphill)

Starting from Atlantic boundaries:

From (2,2) with height 4:

  • Check (2,1): height 2 < 4 โœ— (can't go there)
  • Check (1,2): height 3 < 4 โœ— (can't go there)

From (0,2) with height 5:

  • Check (0,1): height 3 < 5 โœ— (can't go there)
  • Check (1,2): height 3 < 5 โœ— (can't go there)

From (2,0) with height 0:

  • Check (1,0): height 3 โ‰ฅ 0 โœ“ (add to vis2)

From (1,0) with height 3:

  • Check (0,0): height 3 โ‰ฅ 3 โœ“ (add to vis2)

From (0,0) with height 3:

  • Check (0,1): height 3 โ‰ฅ 3 โœ“ (add to vis2)

Final vis2: {(2,0), (2,1), (2,2), (0,2), (1,2), (1,0), (0,0), (0,1)}

Step 4: Find Intersection

Cells in both vis1 AND vis2:

  • (0,0) โœ“ in both
  • (0,1) โœ“ in both
  • (0,2) โœ“ in both
  • (1,0) โœ“ in both
  • (2,0) โœ“ in both
  • (2,1) โœ“ in both
  • (2,2) โœ“ in both

Result: [[0,0], [0,1], [0,2], [1,0], [2,0], [2,1], [2,2]]

These are all the cells from which water can flow to both oceans. Notice that (1,1) with height 1 is surrounded by higher cells, creating a "valley" that prevents water from reaching either ocean, and (1,2) can only reach the Atlantic but not the Pacific.

Solution Implementation

1from collections import deque
2from typing import List
3
4class Solution:
5    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
6        """
7        Find all cells where water can flow to both Pacific and Atlantic oceans.
8        Water flows from higher or equal height cells to lower or equal height cells.
9        Pacific ocean touches left and top edges, Atlantic ocean touches right and bottom edges.
10        """
11      
12        def bfs(queue: deque, visited: set) -> None:
13            """
14            Perform BFS to find all cells that can reach the ocean.
15            Start from ocean edges and move to cells with equal or greater height.
16            """
17            while queue:
18                # Process all cells at current level
19                level_size = len(queue)
20                for _ in range(level_size):
21                    curr_row, curr_col = queue.popleft()
22                  
23                    # Check all 4 adjacent cells (up, down, left, right)
24                    directions = [[0, -1], [0, 1], [1, 0], [-1, 0]]
25                    for delta_row, delta_col in directions:
26                        next_row = curr_row + delta_row
27                        next_col = curr_col + delta_col
28                      
29                        # Check if next cell is valid and water can flow backwards
30                        # (from next cell to current cell, which means next >= current)
31                        if (0 <= next_row < rows and 
32                            0 <= next_col < cols and 
33                            (next_row, next_col) not in visited and 
34                            heights[next_row][next_col] >= heights[curr_row][curr_col]):
35                          
36                            visited.add((next_row, next_col))
37                            queue.append((next_row, next_col))
38      
39        # Get grid dimensions
40        rows = len(heights)
41        cols = len(heights[0])
42      
43        # Initialize visited sets and queues for both oceans
44        pacific_visited = set()
45        atlantic_visited = set()
46        pacific_queue = deque()
47        atlantic_queue = deque()
48      
49        # Add border cells to respective ocean queues
50        for row in range(rows):
51            for col in range(cols):
52                # Pacific ocean: top edge (row=0) or left edge (col=0)
53                if row == 0 or col == 0:
54                    pacific_visited.add((row, col))
55                    pacific_queue.append((row, col))
56              
57                # Atlantic ocean: bottom edge (row=rows-1) or right edge (col=cols-1)
58                if row == rows - 1 or col == cols - 1:
59                    atlantic_visited.add((row, col))
60                    atlantic_queue.append((row, col))
61      
62        # Find all cells reachable from each ocean
63        bfs(pacific_queue, pacific_visited)
64        bfs(atlantic_queue, atlantic_visited)
65      
66        # Return cells that can reach both oceans (intersection of both sets)
67        result = []
68        for row in range(rows):
69            for col in range(cols):
70                if (row, col) in pacific_visited and (row, col) in atlantic_visited:
71                    result.append([row, col])
72      
73        return result
74
1class Solution {
2    // Global variables to store the grid and its dimensions
3    private int[][] heights;
4    private int rows;
5    private int cols;
6
7    public List<List<Integer>> pacificAtlantic(int[][] heights) {
8        // Initialize dimensions
9        rows = heights.length;
10        cols = heights[0].length;
11        this.heights = heights;
12      
13        // Queues for BFS from Pacific and Atlantic oceans
14        Deque<int[]> pacificQueue = new LinkedList<>();
15        Deque<int[]> atlanticQueue = new LinkedList<>();
16      
17        // Sets to track visited cells (encoded as row * cols + col)
18        Set<Integer> pacificVisited = new HashSet<>();
19        Set<Integer> atlanticVisited = new HashSet<>();
20      
21        // Initialize starting points for both oceans
22        for (int row = 0; row < rows; row++) {
23            for (int col = 0; col < cols; col++) {
24                // Pacific Ocean: cells on top edge or left edge
25                if (row == 0 || col == 0) {
26                    int encodedPosition = row * cols + col;
27                    pacificVisited.add(encodedPosition);
28                    pacificQueue.offer(new int[] {row, col});
29                }
30                // Atlantic Ocean: cells on bottom edge or right edge
31                if (row == rows - 1 || col == cols - 1) {
32                    int encodedPosition = row * cols + col;
33                    atlanticVisited.add(encodedPosition);
34                    atlanticQueue.offer(new int[] {row, col});
35                }
36            }
37        }
38      
39        // Perform BFS from both oceans to find reachable cells
40        bfs(pacificQueue, pacificVisited);
41        bfs(atlanticQueue, atlanticVisited);
42      
43        // Find cells that can reach both oceans
44        List<List<Integer>> result = new ArrayList<>();
45        for (int row = 0; row < rows; row++) {
46            for (int col = 0; col < cols; col++) {
47                int encodedPosition = row * cols + col;
48                // If cell is reachable from both oceans, add to result
49                if (pacificVisited.contains(encodedPosition) && 
50                    atlanticVisited.contains(encodedPosition)) {
51                    result.add(Arrays.asList(row, col));
52                }
53            }
54        }
55      
56        return result;
57    }
58
59    private void bfs(Deque<int[]> queue, Set<Integer> visited) {
60        // Direction vectors for moving up, right, down, left
61        int[] directions = {-1, 0, 1, 0, -1};
62      
63        while (!queue.isEmpty()) {
64            // Process all cells at current level
65            int levelSize = queue.size();
66            for (int i = 0; i < levelSize; i++) {
67                int[] currentCell = queue.poll();
68                int currentRow = currentCell[0];
69                int currentCol = currentCell[1];
70              
71                // Explore all 4 directions
72                for (int dir = 0; dir < 4; dir++) {
73                    int nextRow = currentRow + directions[dir];
74                    int nextCol = currentCol + directions[dir + 1];
75                    int encodedNextPosition = nextRow * cols + nextCol;
76                  
77                    // Check if next cell is valid and water can flow from it to current cell
78                    if (nextRow >= 0 && nextRow < rows && 
79                        nextCol >= 0 && nextCol < cols && 
80                        !visited.contains(encodedNextPosition) &&
81                        heights[nextRow][nextCol] >= heights[currentRow][currentCol]) {
82                      
83                        // Mark as visited and add to queue for further exploration
84                        visited.add(encodedNextPosition);
85                        queue.offer(new int[] {nextRow, nextCol});
86                    }
87                }
88            }
89        }
90    }
91}
92
1typedef pair<int, int> pii;
2
3class Solution {
4public:
5    vector<vector<int>> heightsGrid;
6    int rows;
7    int cols;
8
9    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
10        // Initialize dimensions and store the heights grid
11        rows = heights.size();
12        cols = heights[0].size();
13        this->heightsGrid = heights;
14      
15        // Queues for BFS from Pacific and Atlantic oceans
16        queue<pii> pacificQueue;
17        queue<pii> atlanticQueue;
18      
19        // Sets to track visited cells for each ocean (using flattened indices)
20        unordered_set<int> pacificVisited;
21        unordered_set<int> atlanticVisited;
22      
23        // Initialize starting points for both oceans
24        for (int row = 0; row < rows; ++row) {
25            for (int col = 0; col < cols; ++col) {
26                // Pacific Ocean: top row and left column
27                if (row == 0 || col == 0) {
28                    int flatIndex = row * cols + col;
29                    pacificVisited.insert(flatIndex);
30                    pacificQueue.emplace(row, col);
31                }
32                // Atlantic Ocean: bottom row and right column
33                if (row == rows - 1 || col == cols - 1) {
34                    int flatIndex = row * cols + col;
35                    atlanticVisited.insert(flatIndex);
36                    atlanticQueue.emplace(row, col);
37                }
38            }
39        }
40      
41        // Perform BFS from both oceans to find all reachable cells
42        bfs(pacificQueue, pacificVisited);
43        bfs(atlanticQueue, atlanticVisited);
44      
45        // Find cells that can reach both oceans
46        vector<vector<int>> result;
47        for (int row = 0; row < rows; ++row) {
48            for (int col = 0; col < cols; ++col) {
49                int flatIndex = row * cols + col;
50                // If cell is reachable from both oceans, add to result
51                if (pacificVisited.count(flatIndex) && atlanticVisited.count(flatIndex)) {
52                    result.push_back({row, col});
53                }
54            }
55        }
56      
57        return result;
58    }
59
60    void bfs(queue<pii>& bfsQueue, unordered_set<int>& visited) {
61        // Direction vectors for up, right, down, left movement
62        vector<int> directions = {-1, 0, 1, 0, -1};
63      
64        while (!bfsQueue.empty()) {
65            // Process all cells at current BFS level
66            int levelSize = bfsQueue.size();
67            for (int i = 0; i < levelSize; ++i) {
68                auto currentCell = bfsQueue.front();
69                bfsQueue.pop();
70              
71                // Check all 4 adjacent cells
72                for (int dir = 0; dir < 4; ++dir) {
73                    int nextRow = currentCell.first + directions[dir];
74                    int nextCol = currentCell.second + directions[dir + 1];
75                    int flatIndex = nextRow * cols + nextCol;
76                  
77                    // Check if next cell is valid, unvisited, and water can flow from it to current cell
78                    if (nextRow >= 0 && nextRow < rows && 
79                        nextCol >= 0 && nextCol < cols && 
80                        !visited.count(flatIndex) && 
81                        heightsGrid[nextRow][nextCol] >= heightsGrid[currentCell.first][currentCell.second]) {
82                      
83                        visited.insert(flatIndex);
84                        bfsQueue.emplace(nextRow, nextCol);
85                    }
86                }
87            }
88        }
89    }
90};
91
1/**
2 * Find all cells where water can flow to both Pacific and Atlantic oceans
3 * Water flows from higher or equal height cells to lower or equal height cells
4 * Pacific ocean touches left and top edges, Atlantic ocean touches right and bottom edges
5 */
6function pacificAtlantic(heights: number[][]): number[][] {
7    const rows = heights.length;
8    const cols = heights[0].length;
9  
10    // Direction vectors for up, right, down, left
11    const directions: number[][] = [
12        [1, 0],   // down
13        [0, 1],   // right
14        [-1, 0],  // up
15        [0, -1],  // left
16    ];
17  
18    // Track how many oceans each cell can reach (0, 1, or 2)
19    const reachableCount: number[][] = new Array(rows)
20        .fill(0)
21        .map(() => new Array(cols).fill(0));
22  
23    // Track visited cells during DFS traversal
24    const visited: boolean[][] = new Array(rows)
25        .fill(0)
26        .map(() => new Array(cols).fill(false));
27
28    /**
29     * Depth-first search to mark all cells reachable from ocean edges
30     * Water flows backwards from ocean to higher or equal elevation cells
31     */
32    const dfs = (row: number, col: number): void => {
33        // Skip if already visited in current traversal
34        if (visited[row][col]) {
35            return;
36        }
37      
38        // Mark cell as reachable from current ocean
39        reachableCount[row][col]++;
40        visited[row][col] = true;
41      
42        const currentHeight = heights[row][col];
43      
44        // Explore all four directions
45        for (const [deltaRow, deltaCol] of directions) {
46            const nextRow = row + deltaRow;
47            const nextCol = col + deltaCol;
48          
49            // Check bounds and if water can flow from next cell to current cell
50            // (heights[nextRow]?.[nextCol] handles boundary checking)
51            if (currentHeight <= (heights[nextRow] ?? [])[nextCol]) {
52                dfs(nextRow, nextCol);
53            }
54        }
55    };
56
57    // Process Pacific Ocean (top edge)
58    for (let col = 0; col < cols; col++) {
59        dfs(0, col);
60    }
61  
62    // Process Pacific Ocean (left edge)
63    for (let row = 0; row < rows; row++) {
64        dfs(row, 0);
65    }
66  
67    // Reset visited array for Atlantic Ocean traversal
68    visited.forEach(row => row.fill(false));
69  
70    // Process Atlantic Ocean (bottom edge)
71    for (let col = 0; col < cols; col++) {
72        dfs(rows - 1, col);
73    }
74  
75    // Process Atlantic Ocean (right edge)
76    for (let row = 0; row < rows; row++) {
77        dfs(row, cols - 1);
78    }
79
80    // Collect all cells that can reach both oceans (count = 2)
81    const result: number[][] = [];
82    for (let row = 0; row < rows; row++) {
83        for (let col = 0; col < cols; col++) {
84            if (reachableCount[row][col] === 2) {
85                result.push([row, col]);
86            }
87        }
88    }
89  
90    return result;
91}
92

Time and Space Complexity

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the heights matrix.

  • The initial setup iterates through all cells once to identify border cells: O(m * n)
  • The BFS from Pacific ocean borders visits each reachable cell at most once: O(m * n)
  • The BFS from Atlantic ocean borders visits each reachable cell at most once: O(m * n)
  • The final iteration to find cells in both sets: O(m * n)
  • Total: O(m * n) + O(m * n) + O(m * n) + O(m * n) = O(m * n)

Space Complexity: O(m * n)

  • vis1 set can contain at most all cells: O(m * n)
  • vis2 set can contain at most all cells: O(m * n)
  • q1 queue can contain at most all cells during BFS: O(m * n)
  • q2 queue can contain at most all cells during BFS: O(m * n)
  • The result list can contain at most all cells: O(m * n)
  • Total: O(m * n) (since these are not all used simultaneously at maximum capacity, the overall space complexity remains O(m * n))

Common Pitfalls

1. Incorrect Flow Direction Logic

One of the most common mistakes is misunderstanding the flow direction when implementing the reverse-flow approach. Students often write:

Incorrect:

# Wrong: checking if we can flow "downhill" in reverse traversal
if heights[next_row][next_col] <= heights[curr_row][curr_col]:
    visited.add((next_row, next_col))

Correct:

# Right: we need to go "uphill" when traversing backwards from ocean
if heights[next_row][next_col] >= heights[curr_row][curr_col]:
    visited.add((next_row, next_col))

Why this matters: Since we're traversing backwards from the ocean, we need to move to cells with equal or greater height. Think of it as asking "which cells could have sent water to the current cell?" - only cells with height โ‰ฅ current cell's height.

2. Using Lists Instead of Sets for Visited Tracking

Using lists for the visited data structure severely impacts performance:

Inefficient:

pacific_visited = []  # O(n) lookup time
atlantic_visited = []

# Checking membership becomes O(n)
if [next_row, next_col] not in pacific_visited:
    pacific_visited.append([next_row, next_col])

Efficient:

pacific_visited = set()  # O(1) lookup time
atlantic_visited = set()

# Checking membership is O(1)
if (next_row, next_col) not in pacific_visited:
    pacific_visited.add((next_row, next_col))

3. Forgetting to Handle Equal Heights

A critical oversight is not allowing water to flow between cells of equal height:

Wrong:

# Only allows strictly greater heights
if heights[next_row][next_col] > heights[curr_row][curr_col]:

Correct:

# Allows equal or greater heights
if heights[next_row][next_col] >= heights[curr_row][curr_col]:

Water can flow horizontally across cells of the same height, which is essential for finding all valid paths.

4. Incorrect Ocean Boundary Identification

Mixing up which edges belong to which ocean:

Common Mistake:

# Wrong assignment of oceans
if row == 0 or col == cols - 1:  # Mixing top with right edge
    pacific_visited.add((row, col))

Correct:

# Pacific: top (row=0) and left (col=0)
if row == 0 or col == 0:
    pacific_visited.add((row, col))

# Atlantic: bottom (row=rows-1) and right (col=cols-1)  
if row == rows - 1 or col == cols - 1:
    atlantic_visited.add((row, col))

5. Not Processing All Cells at Current BFS Level

Forgetting to process all cells at the current level before moving to the next can lead to incorrect traversal:

Problematic:

while queue:
    curr_row, curr_col = queue.popleft()
    # Immediately processing without level separation
    for delta_row, delta_col in directions:
        # ...

Better (though both work for this problem):

while queue:
    level_size = len(queue)
    for _ in range(level_size):
        curr_row, curr_col = queue.popleft()
        # Process all cells at current distance from ocean

While both approaches find the correct cells, level-by-level processing is clearer and helps if you need to track distance from oceans.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?


Recommended Readings

Want a Structured Path to Master System Design Too? Donโ€™t Miss This!

Load More