Pacific Atlantic Water Flow

🎯

Pacific Atlantic Water Flow

mediumGRAPHAmazonGoogleFacebook

Imagine a continent surrounded by two oceans, and you want to find all the points where water can flow to both oceans. This models how water flows downhill on a grid.

💡 This problem involves understanding how water can flow from higher or equal height cells to lower or equal height neighbors, and requires traversing a grid with graph traversal techniques. Beginners often struggle with the reverse flow concept and managing two sets of reachable cells simultaneously.

📋

Problem Statement

Given an m x n matrix of non-negative integers representing the height of each cell, find all coordinates (i, j) from which water can flow to both the Pacific and Atlantic oceans. Water can flow from a cell to another one if the next cell's height is less than or equal to the current cell's height and is adjacent vertically or horizontally. The Pacific ocean touches the left and top edges of the matrix, and the Atlantic ocean touches the right and bottom edges.

1 ≤ m, n ≤ 2000 ≤ height[i][j] ≤ 10^5

💡

Example

Input"[[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]]"

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

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

• Single cell matrix → cell can flow to both oceans
• All cells have the same height → all cells can flow to both oceans
• Matrix with increasing heights from top-left to bottom-right → only cells near edges can flow to both oceans
• Matrix with decreasing heights from top-left to bottom-right → most cells can flow to both oceans

⚠️

Common Mistakes

Confusing flow direction and starting DFS from each cell

Leads to TLE due to repeated expensive DFS calls

✅ Reverse the flow and start DFS/BFS from ocean edges

Not checking height conditions correctly (using < instead of >= or vice versa)

Incorrect reachable cells, wrong output

✅ Ensure neighbors have height >= current cell when moving from ocean inward

Not marking visited cells before recursive calls

Infinite recursion or stack overflow

✅ Mark cells as visited immediately upon visiting

Forgetting to include all border cells for both oceans

Misses some reachable cells, incomplete results

✅ Add all top and left edges for Pacific, bottom and right edges for Atlantic

Using recursion in languages with small stack limits on large inputs

Stack overflow runtime error

✅ Use iterative BFS approach instead

🧠

Brute Force (DFS from every cell)

💡 This approach tries to simulate the water flow from each cell independently to check if it can reach both oceans. It is straightforward but inefficient, helping beginners understand the problem deeply before optimizing.

Intuition

For each cell, perform two DFS traversals to see if water can reach the Pacific and Atlantic oceans by moving only to neighbors with height less or equal to current cell.

Algorithm

1. For each cell in the matrix:
2. Run DFS to check if it can reach the Pacific ocean by moving only to neighbors with height <= current cell.
3. Run DFS to check if it can reach the Atlantic ocean similarly.
4. If both DFS return true, add the cell to the result.

💡 The challenge is to understand how to simulate water flow and how to check reachability to oceans from each cell separately.

</>

Code

from typing import List

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])

        def dfs(r, c, visited, ocean_check):
            # If cell is on the ocean border, it can reach that ocean
            if ocean_check(r, c):
                return True
            visited.add((r, c))
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and heights[nr][nc] <= heights[r][c]:
                    if dfs(nr, nc, visited, ocean_check):
                        return True
            return False

        result = []
        for i in range(m):
            for j in range(n):
                if dfs(i, j, set(), lambda r, c: r == 0 or c == 0) and dfs(i, j, set(), lambda r, c: r == m - 1 or c == n - 1):
                    result.append([i, j])
        return result

# Driver code
if __name__ == '__main__':
    sol = Solution()
    matrix = [[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]]
    print(sol.pacificAtlantic(matrix))

Line Notes

if not heights or not heights[0]:Check for empty input to avoid errors

def dfs(r, c, visited, ocean_check):Define DFS to explore if cell can reach the ocean defined by ocean_check

if ocean_check(r, c):If current cell is on ocean border, it can reach that ocean

if 0 <= nr < m and 0 <= nc < n and (nr, nc) not in visited and heights[nr][nc] <= heights[r][c]:Move only to neighbors with height less or equal and not visited

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] heights;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(i, j, new HashSet<>(), (r, c) -> r == 0 || c == 0) && dfs(i, j, new HashSet<>(), (r, c) -> r == m - 1 || c == n - 1)) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private boolean dfs(int r, int c, Set<String> visited, OceanCheck oceanCheck) {
        String key = r + "," + c;
        if (oceanCheck.isOcean(r, c)) return true;
        visited.add(key);
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] d : directions) {
            int nr = r + d[0], nc = c + d[1];
            String nKey = nr + "," + nc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited.contains(nKey) && heights[nr][nc] <= heights[r][c]) {
                if (dfs(nr, nc, visited, oceanCheck)) return true;
            }
        }
        return false;
    }

    interface OceanCheck {
        boolean isOcean(int r, int c);
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {
            {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}
        };
        System.out.println(sol.pacificAtlantic(matrix));
    }
}

Line Notes

if (oceanCheck.isOcean(r, c)) return true;If current cell is on ocean border, it can reach that ocean

visited.add(key);Mark current cell as visited to avoid cycles

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited.contains(nKey) && heights[nr][nc] <= heights[r][c])Move only to neighbors with height less or equal and not visited

return false;Return false if no path to ocean found from this cell

#include <iostream>
#include <vector>
#include <set>
#include <functional>
using namespace std;

class Solution {
    int m, n;
    vector<vector<int>> heights;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        this->heights = heights;
        m = heights.size();
        n = heights[0].size();
        vector<vector<int>> result;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                set<pair<int,int>> visited1, visited2;
                if (dfs(i, j, visited1, [](int r, int c, int m, int n){ return r == 0 || c == 0; }) &&
                    dfs(i, j, visited2, [](int r, int c, int m, int n){ return r == m - 1 || c == n - 1; })) {
                    result.push_back({i, j});
                }
            }
        }
        return result;
    }

    bool dfs(int r, int c, set<pair<int,int>>& visited, function<bool(int,int,int,int)> oceanCheck) {
        if (oceanCheck(r, c, m, n)) return true;
        visited.insert({r, c});
        int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : directions) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && visited.count({nr, nc}) == 0 && heights[nr][nc] <= heights[r][c]) {
                if (dfs(nr, nc, visited, oceanCheck)) return true;
            }
        }
        return false;
    }
};

int main() {
    Solution sol;
    vector<vector<int>> matrix = {
        {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}
    };
    vector<vector<int>> res = sol.pacificAtlantic(matrix);
    for (auto& cell : res) {
        cout << "[" << cell[0] << "," << cell[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

if (oceanCheck(r, c, m, n)) return true;If current cell is on ocean border, it can reach that ocean

visited.insert({r, c});Mark current cell as visited to avoid cycles

if (nr >= 0 && nr < m && nc >= 0 && nc < n && visited.count({nr, nc}) == 0 && heights[nr][nc] <= heights[r][c])Move only to neighbors with height less or equal and not visited

return false;Return false if no path to ocean found from this cell

var pacificAtlantic = function(heights) {
    if (!heights || heights.length === 0) return [];
    const m = heights.length, n = heights[0].length;

    function dfs(r, c, visited, oceanCheck) {
        if (oceanCheck(r, c)) return true;
        const key = r + ',' + c;
        visited.add(key);
        const directions = [[1,0],[-1,0],[0,1],[0,-1]];
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            const nKey = nr + ',' + nc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited.has(nKey) && heights[nr][nc] <= heights[r][c]) {
                if (dfs(nr, nc, visited, oceanCheck)) return true;
            }
        }
        return false;
    }

    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (dfs(i, j, new Set(), (r, c) => r === 0 || c === 0) && dfs(i, j, new Set(), (r, c) => r === m - 1 || c === n - 1)) {
                result.push([i, j]);
            }
        }
    }
    return result;
};

// Driver code
const matrix = [[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]];
console.log(pacificAtlantic(matrix));

Line Notes

if (!heights || heights.length === 0) return [];Handle empty input gracefully

if (oceanCheck(r, c)) return true;If current cell is on ocean border, it can reach that ocean

visited.add(key);Mark current cell as visited to avoid cycles

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !visited.has(nKey) && heights[nr][nc] <= heights[r][c])Move only to neighbors with height less or equal and not visited

⏱

Complexity

TimeO(m^2 * n^2)

SpaceO(m * n)

For each cell, DFS explores up to O(m*n) cells, leading to O(m^2 * n^2) in total.

💡 For a 100x100 grid, this means 10,000 cells each doing DFS over 10,000 cells, totaling 100 million operations, which is too slow.

Interview Verdict: TLE

This approach is too slow for large inputs but helps understand the problem and DFS traversal.

🧠

Better Approach (Reverse DFS from Oceans)

💡 Instead of checking from each cell if it can reach oceans, start DFS from ocean edges and find all cells that can flow into the ocean. This reduces redundant computations.

Intuition

Water flows from higher to lower or equal height. So starting from ocean edges and moving inward to higher or equal height cells finds all reachable cells for each ocean.

Algorithm

1. Initialize two boolean matrices pacific_reachable and atlantic_reachable.
2. Run DFS from all Pacific border cells, marking reachable cells in pacific_reachable.
3. Run DFS from all Atlantic border cells, marking reachable cells in atlantic_reachable.
4. Collect cells reachable in both matrices as the result.

💡 This approach cleverly reverses the problem direction, avoiding repeated DFS from every cell.

</>

Code

from typing import List

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])

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

        def dfs(r, c, reachable):
            reachable[r][c] = True
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                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]:
                    dfs(nr, nc, reachable)

        for i in range(m):
            dfs(i, 0, pacific_reachable)       # Left edge
            dfs(i, n-1, atlantic_reachable)    # Right edge
        for j in range(n):
            dfs(0, j, pacific_reachable)       # Top edge
            dfs(m-1, j, atlantic_reachable)    # Bottom edge

        result = []
        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

# Driver code
if __name__ == '__main__':
    sol = Solution()
    matrix = [[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]]
    print(sol.pacificAtlantic(matrix))

Line Notes

pacific_reachable = [[False]*n for _ in range(m)]Initialize matrix to track cells reachable from Pacific

def dfs(r, c, reachable):DFS marks all cells reachable from given ocean edge

if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:Move only to neighbors with height >= current cell to simulate reverse flow

for i in range(m):Start DFS from all cells on left and right edges

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] heights;
    private boolean[][] pacificReachable, atlanticReachable;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        pacificReachable = new boolean[m][n];
        atlanticReachable = new boolean[m][n];

        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacificReachable);
            dfs(i, n - 1, atlanticReachable);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacificReachable);
            dfs(m - 1, j, atlanticReachable);
        }

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private void dfs(int r, int c, boolean[][] reachable) {
        if (reachable[r][c]) return;
        reachable[r][c] = true;
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] d : directions) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, reachable);
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {
            {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}
        };
        System.out.println(sol.pacificAtlantic(matrix));
    }
}

Line Notes

pacificReachable = new boolean[m][n];Track cells reachable from Pacific ocean

if (reachable[r][c]) return;Avoid revisiting cells in DFS

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c])Move only to neighbors with height >= current cell

for (int i = 0; i < m; i++)Start DFS from all rows on left and right edges

#include <iostream>
#include <vector>
using namespace std;

class Solution {
    int m, n;
    vector<vector<int>> heights;
    vector<vector<bool>> pacificReachable, atlanticReachable;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        this->heights = heights;
        m = heights.size();
        n = heights[0].size();
        pacificReachable.assign(m, vector<bool>(n, false));
        atlanticReachable.assign(m, vector<bool>(n, false));

        for (int i = 0; i < m; i++) {
            dfs(i, 0, pacificReachable);
            dfs(i, n - 1, atlanticReachable);
        }
        for (int j = 0; j < n; j++) {
            dfs(0, j, pacificReachable);
            dfs(m - 1, j, atlanticReachable);
        }

        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        return result;
    }

    void dfs(int r, int c, vector<vector<bool>>& reachable) {
        if (reachable[r][c]) return;
        reachable[r][c] = true;
        int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for (auto& d : directions) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, reachable);
            }
        }
    }
};

int main() {
    Solution sol;
    vector<vector<int>> matrix = {
        {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}
    };
    vector<vector<int>> res = sol.pacificAtlantic(matrix);
    for (auto& cell : res) {
        cout << "[" << cell[0] << "," << cell[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

pacificReachable.assign(m, vector<bool>(n, false));Initialize reachable matrix for Pacific ocean

if (reachable[r][c]) return;Prevent revisiting cells in DFS

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c])Only move to neighbors with height >= current cell

for (int i = 0; i < m; i++)Start DFS from all rows on left and right edges

var pacificAtlantic = function(heights) {
    if (!heights || heights.length === 0) return [];
    const m = heights.length, n = heights[0].length;
    const pacificReachable = Array.from({length: m}, () => Array(n).fill(false));
    const atlanticReachable = Array.from({length: m}, () => Array(n).fill(false));

    function dfs(r, c, reachable) {
        if (reachable[r][c]) return;
        reachable[r][c] = true;
        const directions = [[1,0],[-1,0],[0,1],[0,-1]];
        for (const [dr, dc] of directions) {
            const nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                dfs(nr, nc, reachable);
            }
        }
    }

    for (let i = 0; i < m; i++) {
        dfs(i, 0, pacificReachable);
        dfs(i, n - 1, atlanticReachable);
    }
    for (let j = 0; j < n; j++) {
        dfs(0, j, pacificReachable);
        dfs(m - 1, j, atlanticReachable);
    }

    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                result.push([i, j]);
            }
        }
    }
    return result;
};

// Driver code
const matrix = [[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]];
console.log(pacificAtlantic(matrix));

Line Notes

const pacificReachable = Array.from({length: m}, () => Array(n).fill(false));Initialize matrix to track Pacific reachability

if (reachable[r][c]) return;Avoid revisiting cells in DFS

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c])Move only to neighbors with height >= current cell

for (let i = 0; i < m; i++)Start DFS from all rows on left and right edges

⏱

Complexity

TimeO(m * n)

SpaceO(m * n)

Each cell is visited at most twice (once per ocean) during DFS, so total time is linear in grid size.

💡 For a 100x100 grid, this means about 20,000 operations, which is efficient.

Interview Verdict: Accepted

This approach is efficient and practical for interview coding.

🧠

Optimal Approach (BFS from Oceans)

💡 Using BFS instead of DFS from ocean edges can be easier to implement iteratively and can avoid stack overflow issues in large grids.

Intuition

Start BFS from all ocean border cells simultaneously, expanding inward to higher or equal height neighbors, marking reachable cells.

Algorithm

1. Initialize two queues for Pacific and Atlantic oceans with their border cells.
2. Perform BFS for each ocean, adding neighbors with height >= current cell to the queue and marking them reachable.
3. After BFS completes, find cells reachable from both oceans.
4. Return the list of such cells.

💡 BFS processes cells in waves, which can be conceptually simpler and safer than DFS recursion.

</>

Code

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])

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

        pacific_queue = deque()
        atlantic_queue = deque()

        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

        def bfs(queue, reachable):
            directions = [(1,0),(-1,0),(0,1),(0,-1)]
            while queue:
                r, c = queue.popleft()
                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))

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

        result = []
        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

# Driver code
if __name__ == '__main__':
    sol = Solution()
    matrix = [[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]]
    print(sol.pacificAtlantic(matrix))

Line Notes

pacific_queue = deque()Initialize queue for BFS starting points for Pacific ocean

pacific_reachable[i][0] = TrueMark border cells as reachable initially

while queue:Process cells in BFS order

if 0 <= nr < m and 0 <= nc < n and not reachable[nr][nc] and heights[nr][nc] >= heights[r][c]:Add neighbors with height >= current cell to BFS queue

import java.util.*;

public class Solution {
    private int m, n;
    private int[][] heights;
    private boolean[][] pacificReachable, atlanticReachable;

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        this.heights = heights;
        m = heights.length;
        n = heights[0].length;
        pacificReachable = new boolean[m][n];
        atlanticReachable = new boolean[m][n];

        Queue<int[]> pacificQueue = new LinkedList<>();
        Queue<int[]> atlanticQueue = new LinkedList<>();

        for (int i = 0; i < m; i++) {
            pacificQueue.offer(new int[]{i, 0});
            atlanticQueue.offer(new int[]{i, n - 1});
            pacificReachable[i][0] = true;
            atlanticReachable[i][n - 1] = true;
        }
        for (int j = 0; j < n; j++) {
            pacificQueue.offer(new int[]{0, j});
            atlanticQueue.offer(new int[]{m - 1, j});
            pacificReachable[0][j] = true;
            atlanticReachable[m - 1][j] = true;
        }

        bfs(pacificQueue, pacificReachable);
        bfs(atlanticQueue, atlanticReachable);

        List<List<Integer>> result = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.add(Arrays.asList(i, j));
                }
            }
        }
        return result;
    }

    private void bfs(Queue<int[]> queue, boolean[][] reachable) {
        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int r = cell[0], c = cell[1];
            for (int[] d : directions) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                    reachable[nr][nc] = true;
                    queue.offer(new int[]{nr, nc});
                }
            }
        }
    }

    // Driver code
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] matrix = {
            {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}
        };
        System.out.println(sol.pacificAtlantic(matrix));
    }
}

Line Notes

Queue<int[]> pacificQueue = new LinkedList<>();Initialize BFS queue for Pacific ocean

pacificReachable[i][0] = true;Mark border cells as reachable initially

while (!queue.isEmpty()) {Process BFS queue until empty

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c])Add neighbors with height >= current cell to BFS queue

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
    int m, n;
    vector<vector<int>> heights;
    vector<vector<bool>> pacificReachable, atlanticReachable;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        this->heights = heights;
        m = heights.size();
        n = heights[0].size();
        pacificReachable.assign(m, vector<bool>(n, false));
        atlanticReachable.assign(m, vector<bool>(n, false));

        queue<pair<int,int>> pacificQueue, atlanticQueue;

        for (int i = 0; i < m; i++) {
            pacificQueue.push({i, 0});
            atlanticQueue.push({i, n - 1});
            pacificReachable[i][0] = true;
            atlanticReachable[i][n - 1] = true;
        }
        for (int j = 0; j < n; j++) {
            pacificQueue.push({0, j});
            atlanticQueue.push({m - 1, j});
            pacificReachable[0][j] = true;
            atlanticReachable[m - 1][j] = true;
        }

        bfs(pacificQueue, pacificReachable);
        bfs(atlanticQueue, atlanticReachable);

        vector<vector<int>> result;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        return result;
    }

    void bfs(queue<pair<int,int>>& q, vector<vector<bool>>& reachable) {
        int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.empty()) {
            auto [r, c] = q.front(); q.pop();
            for (auto& d : directions) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                    reachable[nr][nc] = true;
                    q.push({nr, nc});
                }
            }
        }
    }
};

int main() {
    Solution sol;
    vector<vector<int>> matrix = {
        {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}
    };
    vector<vector<int>> res = sol.pacificAtlantic(matrix);
    for (auto& cell : res) {
        cout << "[" << cell[0] << "," << cell[1] << "] ";
    }
    cout << endl;
    return 0;
}

Line Notes

queue<pair<int,int>> pacificQueue, atlanticQueue;Initialize BFS queues for both oceans

pacificReachable[i][0] = true;Mark ocean border cells as reachable

while (!q.empty()) {Process BFS queue until empty

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c])Add neighbors with height >= current cell to BFS queue

var pacificAtlantic = function(heights) {
    if (!heights || heights.length === 0) return [];
    const m = heights.length, n = heights[0].length;
    const pacificReachable = Array.from({length: m}, () => Array(n).fill(false));
    const atlanticReachable = Array.from({length: m}, () => Array(n).fill(false));

    const pacificQueue = [];
    const atlanticQueue = [];

    for (let i = 0; i < m; i++) {
        pacificQueue.push([i, 0]);
        atlanticQueue.push([i, n - 1]);
        pacificReachable[i][0] = true;
        atlanticReachable[i][n - 1] = true;
    }
    for (let j = 0; j < n; j++) {
        pacificQueue.push([0, j]);
        atlanticQueue.push([m - 1, j]);
        pacificReachable[0][j] = true;
        atlanticReachable[m - 1][j] = true;
    }

    function bfs(queue, reachable) {
        const directions = [[1,0],[-1,0],[0,1],[0,-1]];
        while (queue.length > 0) {
            const [r, c] = queue.shift();
            for (const [dr, dc] of directions) {
                const nr = r + dr, nc = c + dc;
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c]) {
                    reachable[nr][nc] = true;
                    queue.push([nr, nc]);
                }
            }
        }
    }

    bfs(pacificQueue, pacificReachable);
    bfs(atlanticQueue, atlanticReachable);

    const result = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (pacificReachable[i][j] && atlanticReachable[i][j]) {
                result.push([i, j]);
            }
        }
    }
    return result;
};

// Driver code
const matrix = [[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]];
console.log(pacificAtlantic(matrix));

Line Notes

const pacificReachable = Array.from({length: m}, () => Array(n).fill(false));Initialize matrix to track Pacific reachability

pacificReachable[i][0] = true;Mark border cells as reachable initially

while (queue.length > 0) {Process BFS queue until empty

if (nr >= 0 && nr < m && nc >= 0 && nc < n && !reachable[nr][nc] && heights[nr][nc] >= heights[r][c])Add neighbors with height >= current cell to BFS queue

⏱

Complexity

TimeO(m * n)

SpaceO(m * n)

Each cell is visited at most twice during BFS, once per ocean, so total time is linear in grid size.

💡 For a 100x100 grid, this means about 20,000 operations, which is efficient and safe from recursion limits.

Interview Verdict: Accepted

BFS is a robust alternative to DFS, especially for large inputs or languages with recursion limits.

📊

All Approaches - One-Glance Tradeoffs

💡 The reverse DFS or BFS from ocean edges is the best approach to implement in interviews due to efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (DFS from each cell)	O(m^2 * n^2)	O(m * n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Reverse DFS from Oceans	O(m * n)	O(m * n)	Possible on large grids	N/A	Code this for recursive approach
3. BFS from Oceans	O(m * n)	O(m * n)	No	N/A	Code this for iterative approach

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach and its inefficiency.Introduce the reverse DFS approach from ocean edges.Discuss BFS as an alternative to DFS.Code the optimal approach and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 15min → Test & Discuss: 7min. Total ~30min

What the Interviewer Tests

Understanding of graph traversal, ability to optimize brute force, handling edge cases, and clear communication of approach and complexity.

Common Follow-ups

• What if diagonal moves were allowed? → Modify directions array accordingly.
• How to handle very large grids? → Use BFS to avoid stack overflow and optimize memory.
• Can you do this with less space? → Possibly, but tracking two oceans requires separate visited sets.
• What if heights can be negative? → Algorithm remains the same as comparisons are relative.

💡 These follow-ups test adaptability and deeper understanding of the problem constraints and variations.

🔍

Pattern Recognition

When to Use

1) Grid with height or weight constraints, 2) Need to find cells reachable from multiple sources, 3) Flow or movement constrained by height comparisons, 4) Two distinct sets of reachable cells to intersect.

Signature Phrases

water can flow from cell to oceancells that can reach both Pacific and Atlantic

NOT This Pattern When

Classic single-source shortest path or simple flood fill without multiple sets or reverse flow.

Similar Problems

Number of Islands - grid traversal and connected componentsWalls and Gates - multi-source BFS to find shortest distancesRotting Oranges - BFS spreading from multiple sources

Practice

1. Consider the following Python code that counts connected components using BFS. What is the value of count returned by countComponents(4, [[0,1],[2,3]])?

easy

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Trace BFS starting from node 0

   Nodes 0 and 1 are connected, so BFS visits both, marking them visited. This forms one component.

2. Step 2: Trace BFS starting from node 2

   Nodes 2 and 3 are connected, BFS visits both, marking them visited. This forms the second component.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two disconnected pairs -> 2 components [OK]

Hint: Count increments once per unvisited node BFS start [OK]

Common Mistakes:

• Counting edges instead of components
• Off-by-one in count increment

2. What is the time complexity of the BFS-based algorithm to count connected components in an undirected graph with n nodes and e edges?

medium

A. O(e log n) due to sorting adjacency lists before BFS

B. O(n²) because BFS visits all nodes and edges repeatedly

C. O(n + e) because each node and edge is visited once during BFS

D. O(n + e²) because edges are checked multiple times

Solution

1. Step 1: Identify BFS visits each node once

   Each node is enqueued and dequeued exactly once, so node visits are O(n).

2. Step 2: Identify BFS visits each edge twice

   Each undirected edge is checked from both endpoints, so edge visits are O(e).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sum of node and edge visits -> O(n + e) [OK]

Hint: BFS visits nodes and edges once each [OK]

Common Mistakes:

• Assuming BFS repeats visits causing O(n²)
• Confusing edge visits with sorting cost

3. Suppose the graph edges can be reused multiple times (i.e., the graph can have parallel edges and cycles). Which modification to the BFS-based valid_tree algorithm correctly determines if the graph is still a valid tree under these relaxed constraints?

hard

A. Use Union-Find data structure to detect cycles and ensure connectivity despite parallel edges.

B. Remove the edge count check and rely solely on BFS cycle detection.

C. Modify BFS to ignore revisiting any node regardless of parent to handle parallel edges.

D. Count edges and nodes, and if edges >= n, return false immediately.

Solution

1. Step 1: Understand problem change

   Allowing parallel edges and cycles breaks the simple edge count == n-1 assumption.

2. Step 2: Identify robust approach

   Union-Find efficiently detects cycles and connectivity even with parallel edges and multiple components.

3. Step 3: Why other options fail

   Removing edge count check loses pruning; ignoring revisits breaks cycle detection; counting edges >= n is insufficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Union-Find handles complex graphs with cycles and parallel edges [OK]

Hint: Union-Find handles cycle detection with parallel edges [OK]

Common Mistakes:

• Relying on edge count only
• Ignoring revisits incorrectly
• Simple BFS fails with parallel edges

4. Suppose the problem is modified so that diagonal neighbors (top-left, top-right, bottom-left, bottom-right) are also considered connected. Which of the following changes to the BFS algorithm correctly adapts to this new requirement without double counting or missing cells?

hard

A. Add diagonal neighbors to the neighbor list and keep the rest of the BFS code unchanged

B. Use DFS instead of BFS because BFS cannot handle diagonal connections

C. Keep neighbor list unchanged but run BFS twice, once for horizontal/vertical and once for diagonals

D. Add diagonal neighbors to the neighbor list and also mark visited cells immediately when enqueuing them

Solution

1. Step 1: Add diagonal neighbors to the neighbor list

   Include all 8 directions: horizontal, vertical, and diagonal neighbors.

2. Step 2: Mark cells as visited when enqueuing

   This prevents adding the same cell multiple times from different neighbors, avoiding double counting.

3. Step 3: Keep BFS traversal logic unchanged otherwise

   Running BFS twice or switching to DFS is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Mark visited on enqueue avoids duplicates with expanded neighbors [OK]

Hint: Mark visited on enqueue when neighbors increase [OK]

Common Mistakes:

• Not marking visited on enqueue causing duplicates
• Running BFS multiple times unnecessarily
• Thinking BFS can't handle diagonals

5. Suppose the problem is modified so that you can only move in 4 directions (up, down, left, right) instead of 8. Which of the following statements about the shortest path algorithm is true?

hard

A. Greedy Best-First Search guarantees shortest path with 4-direction moves

B. Bidirectional BFS still finds the shortest path, but the path length may be longer due to restricted moves

C. DFS with backtracking becomes optimal since fewer directions reduce complexity

D. Dynamic Programming is required to handle the reduced movement directions

Solution

1. Step 1: Understand movement restriction impact

   Reducing to 4 directions limits possible paths, potentially increasing shortest path length.

2. Step 2: Evaluate algorithm suitability

   Bidirectional BFS still finds shortest path efficiently; DFS and greedy do not guarantee shortest path.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bidirectional BFS adapts to movement constraints, still optimal [OK]

Hint: Bidirectional BFS adapts to movement constraints [OK]

Common Mistakes:

• Assuming DFS or greedy become optimal
• Thinking DP is needed for movement changes