Pacific Atlantic Water Flow

shriyanshi24jindal

Mar 29th, 2026

142

Never

Not a member of GistPad yet? Sign Up, it unlocks many cool features!

Java 16.86 KB | None | 0 0

copy raw download clone embed print report

class Solution {
/**
* Key Observation: Water can flow from cell A → B if: height[B] ≤ height[A]
* Instead of simulating water from every cell to the ocean (very expensive), we reverse the flow:
* We move from ocean → inside and only go to cells with equal or greater height.
height[next] >= height[current] - This tells us which cells can reach the ocean.
* We maintain two visited matrices:
pacific[n][m] -> cells that can reach Pacific
atlantic[n][m] -> cells that can reach Atlantic
* Start DFS From Ocean Borders
Pacific Ocean touches:
Top row
Left column
So run DFS from: (i,0) for all rows (0,j) for all columns
Mark all reachable cells in pacific.
Atlantic Ocean touches:
Last row
Right column
So run DFS from: (n-1,j) for all rows (i,m-1) for all columns
Mark all reachable cells in Atlantic.
* DFS moves to neighbors only if height is increasing or equal.
Condition preventing DFS:
1. Out of bounds
2. Already visited
3. Next height < previous height
* Explore All 4 Directions
From every cell we visit:
down -> (i+1, j)
right -> (i, j+1)
left -> (i, j-1)
up -> (i-1, j)
Find Cells That Reach Both Oceans
Finally iterate the grid:
if(pacific[i][j] && atlantic[i][j])
add to result
*/
public List<List<Integer>> pacificAtlantic(int[][] heights) {
List<List<Integer>> res = new ArrayList<>();
int n = heights.length;
int m = heights[0].length;
boolean[][] pacific = new boolean[n][m];
boolean[][] atlantic = new boolean[n][m];
for(int i=0; i<n ;i++)
{
// 0th column
// -1 and -1 represent the old ith and jth cell
markCells(heights, pacific, i, 0, -1, -1, n, m);
// last column
// -1 and -1 represent the old ith and jth cell
markCells(heights, atlantic, i, m-1, -1, -1, n, m);
}
for(int j=0; j<m ;j++)
{
// 0th row
// -1 and -1 represent the old ith and jth cell
markCells(heights, pacific, 0, j, -1, -1, n, m);
// last row
// -1 and -1 represent the old ith and jth cell
markCells(heights, atlantic, n-1, j, -1, -1, n, m);
}
for(int i=0; i<n; i++)
{
for(int j=0; j<m; j++)
{
if(pacific[i][j] == true && atlantic[i][j] == true)
{
List<Integer> temp = new ArrayList<>();
temp.add(i);
temp.add(j);
if(!res.contains(temp))
res.add(temp);
}
}
}
return res;
}
public void markCells(int[][] heights, boolean[][] visited, int i, int j, int oldi, int oldj, int n, int m)
{
// if the current height is less than or equal to the old cell's height then water can't flow
if(i < 0 || j < 0 || i >= n || j >= m || visited[i][j] == true ||
(oldi >=0 && oldj >=0 && heights[oldi][oldj] > heights[i][j]))
return;
visited[i][j] = true;
// visiting in all 4-directions
markCells(heights, visited, i+1, j, i, j, n, m);
markCells(heights, visited, i, j+1, i, j, n, m);
markCells(heights, visited, i, j-1, i, j, n, m);
markCells(heights, visited, i-1, j, i, j, n, m);
}
}

RAW Paste Data Copied

class Solution {
    /**
    * Key Observation: Water can flow from cell A → B if: height[B] ≤ height[A]
    * Instead of simulating water from every cell to the ocean (very expensive), we reverse the flow:
    * We move from ocean → inside and only go to cells with equal or greater height.
        height[next] >= height[current] - This tells us which cells can reach the ocean.
    * We maintain two visited matrices:
        pacific[n][m]   -> cells that can reach Pacific
        atlantic[n][m]  -> cells that can reach Atlantic
    * Start DFS From Ocean Borders
        Pacific Ocean touches:
            Top row
            Left column
        So run DFS from: (i,0)  for all rows (0,j)  for all columns
        Mark all reachable cells in pacific.
        Atlantic Ocean touches:
            Last row
            Right column
        So run DFS from: (n-1,j)  for all rows (i,m-1)  for all columns
        Mark all reachable cells in Atlantic.
    * DFS moves to neighbors only if height is increasing or equal.
        Condition preventing DFS:
        1. Out of bounds
        2. Already visited
        3. Next height < previous height
    * Explore All 4 Directions
        From every cell we visit:
        down   -> (i+1, j)
        right  -> (i, j+1)
        left   -> (i, j-1)
        up     -> (i-1, j)
    
    Find Cells That Reach Both Oceans
        Finally iterate the grid:
            if(pacific[i][j] && atlantic[i][j])
                add to result
    */
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        List<List<Integer>> res = new ArrayList<>();

int n = heights.length;
        int m = heights[0].length;
        boolean[][] pacific = new boolean[n][m];
        boolean[][] atlantic = new boolean[n][m];

for(int i=0; i<n ;i++)
        {
            // 0th column
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, pacific, i, 0, -1, -1, n, m);

// last column
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, atlantic, i, m-1, -1, -1, n, m);
        }

for(int j=0; j<m ;j++)
        {
            // 0th row
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, pacific, 0, j, -1, -1, n, m);

// last row
            // -1 and -1 represent the old ith and jth cell
            markCells(heights, atlantic, n-1, j, -1, -1, n, m);
        }

for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(pacific[i][j] == true && atlantic[i][j] == true)
                {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(i);
                    temp.add(j);
                    if(!res.contains(temp))
                        res.add(temp);
                }
            }
        }
        return res;
    }

public void markCells(int[][] heights, boolean[][] visited, int i, int j, int oldi, int oldj, int n, int m)
    {
        // if the current height is less than or equal to the old cell's height then water can't flow
        if(i < 0 || j < 0 || i >= n || j >= m || visited[i][j] == true || 
            (oldi >=0 && oldj >=0 && heights[oldi][oldj] > heights[i][j]))
            return;
        
        visited[i][j] = true;
        // visiting in all 4-directions
        markCells(heights, visited, i+1, j, i, j, n, m);
        markCells(heights, visited, i, j+1, i, j, n, m);
        markCells(heights, visited, i, j-1, i, j, n, m);
        markCells(heights, visited, i-1, j, i, j, n, m);
    }
}