Pacific Atlantic Water Flow - Practice Coding Problems

Pacific Atlantic Water Flow - Problem

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean.

Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.

Input & Output

Example 1 — Basic Island Grid

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

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

💡 Note: These cells can flow water to both Pacific (top/left edges) and Atlantic (bottom/right edges). For example, cell (0,4) with height 5 can flow to Pacific through the top edge and to Atlantic through the right edge.

Example 2 — Simple Small Grid

$ Input: heights = [[1,2,3],[4,5,6],[7,8,9]]

› Output: [[0,2],[1,2],[2,0],[2,1],[2,2]]

💡 Note: Water flows from higher to lower or equal heights. Cell (0,2) can reach Pacific via top edge and Atlantic via right edge. Cell (2,0) can reach Pacific via left edge and Atlantic via bottom edge.

Example 3 — Single Cell

$ Input: heights = [[1]]

› Output: [[0,0]]

💡 Note: A single cell borders both oceans (touches all edges), so water can flow to both Pacific and Atlantic oceans.

Constraints

m == heights.length
n == heights[r].length
1 ≤ m, n ≤ 200
0 ≤ heights[r][c] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Matrix of heights with Pacific (top/left) and Atlantic (bottom/right) boundaries

Flow Rules

Water flows to adjacent cells with equal or lower height

Output

Coordinates of cells that can reach both oceans

Key Takeaway

🎯 Key Insight: Instead of flowing down from each cell, flow up from ocean boundaries to find all reachable cells efficiently

Asked in

G Google 32 a Amazon 28 M Microsoft 15 f Facebook 12

The key insight is to reverse the problem: instead of checking if each cell can reach both oceans, start from the ocean boundaries and find all cells that can be reached. Use reverse DFS from Pacific edges (top/left) and Atlantic edges (bottom/right), then find their intersection. Time: O(mn), Space: O(mn)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS from Each Cell	O(m²n²)	O(mn)	For each cell, run DFS to check if water can reach both oceans
Reverse DFS from Ocean Boundaries	O(mn)	O(mn)	Start DFS from ocean edges and work backward to find all reachable cells

Brute Force DFS from Each Cell — Algorithm Steps

Step 1: For each cell, run DFS to check Pacific reachability
Step 2: For each cell, run DFS to check Atlantic reachability
Step 3: Collect cells that can reach both oceans

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Cell

Start from a cell and check reachability

DFS to Pacific

Run DFS toward top/left edges

DFS to Atlantic

Run DFS toward bottom/right edges

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
int m, n;

bool dfs(int** heights, int r, int c, char* targetOcean, bool** visited) {
    if (visited[r][c]) return false;
    visited[r][c] = true;
    
    if (strcmp(targetOcean, "pacific") == 0) {
        if (r == 0 || c == 0) return true;
    } else {
        if (r == m-1 || c == n-1) return true;
    }
    
    for (int i = 0; i < 4; i++) {
        int nr = r + directions[i][0], nc = c + directions[i][1];
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && heights[nr][nc] <= heights[r][c]) {
            if (dfs(heights, nr, nc, targetOcean, visited)) return true;
        }
    }
    return false;
}

int** solution(int** heights, int heightsSize, int* heightsColSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    if (heightsSize == 0) return NULL;
    
    m = heightsSize;
    n = heightsColSize[0];
    
    int** result = (int**)malloc(m * n * sizeof(int*));
    *returnColumnSizes = (int*)malloc(m * n * sizeof(int));
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            // Allocate visited arrays
            bool** pacificVisited = (bool**)malloc(m * sizeof(bool*));
            bool** atlanticVisited = (bool**)malloc(m * sizeof(bool*));
            for (int k = 0; k < m; k++) {
                pacificVisited[k] = (bool*)calloc(n, sizeof(bool));
                atlanticVisited[k] = (bool*)calloc(n, sizeof(bool));
            }
            
            bool canReachPacific = dfs(heights, i, j, "pacific", pacificVisited);
            bool canReachAtlantic = dfs(heights, i, j, "atlantic", atlanticVisited);
            
            if (canReachPacific && canReachAtlantic) {
                result[*returnSize] = (int*)malloc(2 * sizeof(int));
                result[*returnSize][0] = i;
                result[*returnSize][1] = j;
                (*returnColumnSizes)[*returnSize] = 2;
                (*returnSize)++;
            }
            
            // Free visited arrays
            for (int k = 0; k < m; k++) {
                free(pacificVisited[k]);
                free(atlanticVisited[k]);
            }
            free(pacificVisited);
            free(atlanticVisited);
        }
    }
    
    return result;
}

int main() {
    // Simple parsing for basic test cases
    int heights[3][3] = {{1,2,2},{3,8,6},{2,3,4}};
    int* heightRows[3] = {heights[0], heights[1], heights[2]};
    int heightsColSize[3] = {3, 3, 3};
    
    int returnSize;
    int* returnColumnSizes;
    int** result = solution(heightRows, 3, heightsColSize, &returnSize, &returnColumnSizes);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("[%d,%d]", result[i][0], result[i][1]);
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m²n²)

For each of m×n cells, we run DFS that can visit all m×n cells in worst case

⚠ Quadratic Growth

Space Complexity

O(mn)

DFS recursion stack can go up to m×n depth plus visited arrays

⚡ Linearithmic Space

85.6K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS from Each Cell — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler