Pacific Atlantic Water Flow Leetcode Problem 417 [Python Solution]

Welcome to another Python coding challenge!

In this blog post, we will be solving the Pacific Atlantic Water Flow problem, which is LeetCode problem 417. This problem falls under the category of graphs and is of medium difficulty.

The goal is to determine which cells on a rectangular island can send rainwater to both the Pacific and Atlantic Oceans.

We'll explore an efficient Python solution to tackle this problem.

If you're ready, let's dive right into it!

Problem Overview

The problem statement provides us with an m x n rectangular island that borders both the Pacific Ocean and the Atlantic Ocean.

The Pacific Ocean touches the island's left and top edges, while the Atlantic Ocean touches the island's right and bottom edges.

The island is divided into a grid of cells, each represented by an integer value heights[r][c], which indicates the height above sea level of the cell at coordinate (r, c).

Rainwater can flow from a cell to its neighboring cells in the north, south, east, and west directions, but only 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.

Our task is to return a 2D list of grid coordinates called result, where each element result[i] = [ri, ci] denotes that rainwater can flow from cell (ri, ci) to both the Pacific and Atlantic Oceans.

To provide a clearer understanding, let's go through an example.

Example 1:

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]]
Explanation:
The following cells can flow to both the Pacific and Atlantic oceans:
– [0, 4]: Can flow to the Pacific Ocean and the Atlantic Ocean.
– [1, 3]: Can flow to the Pacific Ocean and the Atlantic Ocean.
– [1, 4]: Can flow to the Pacific Ocean and the Atlantic Ocean.
– [2, 2]: Can flow to the Pacific Ocean and the Atlantic Ocean.
– [3, 0]: Can flow to the Pacific Ocean and the Atlantic Ocean.
– [3, 1]: Can flow to the Pacific Ocean and the Atlantic Ocean.
– [4, 0]: Can flow to the Pacific Ocean and the Atlantic Ocean.

Note that there are other possible paths for these cells to flow to the Pacific and Atlantic Oceans.

Constraints:

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 10^5

Now, let's explore the solution to this problem.

Understanding the Constraints

Before diving into the solution, let's take a moment to understand the constraints of the problem.

These constraints will guide us in designing an efficient solution.

The dimensions of the rectangular island are given by m and n.

This means the grid can be relatively large, with up to 200 rows and 200 columns.
2. The heights of the cells are represented by non-negative integers, and the heights can range from 0 to 10^5.
3. We need to return a list of grid coordinates, which means we'll be dealing with 2D lists.

Considering these constraints, we need to ensure that our solution is efficient and can handle larger inputs.

Let's proceed to the solution.

Pacific Atlantic Water Flow LeetCode Problem Solution

1. Bruteforce Approach

One way to approach this problem is to use a brute force method.

We can start from each cell and perform a depth-first search (DFS) or breadth-first search (BFS) to determine whether it can reach the Pacific Ocean and the Atlantic Ocean.

This approach would involve a lot of repeated work, as we would be running a search for each cell, which can lead to a time complexity of O(n * m^2) or worse.

To avoid this inefficiency, we'll explore a more optimized solution.

2. Efficient Approach with DFS

Algorithm:

Get the dimensions of the grid: ROWS and COLS represent the number of rows and columns in the heights grid, respectively.
Initialize two sets: pac (Pacific Ocean) and atl (Atlantic Ocean) to keep track of cells that can reach the Pacific and Atlantic Oceans, respectively.
Implement a DFS function, dfs, which takes the following parameters:
- r (current row)
- c (current column)
- visit (the set to keep track of visited cells)
- prevHeight (the height of the previous cell visited)
The DFS function will perform the following checks for each cell:
– If the cell has already been visited, return.
– If the cell is out of bounds (either in the negative row or column or exceeding ROWS or COLS), return.
– If the height of the cell is less than the prevHeight, return.
Start by iterating through the first row (r = 0) and call the dfs function on each cell in this row.

Pass the pac set as the visit parameter, as this row is connected to the Pacific Ocean.

Next, iterate through the last row (r = ROWS - 1) and call the dfs function on each cell in this row.

Use the atl set for visit as this row is connected to the Atlantic Ocean.

Similarly, iterate through the first column (c = 0) and call the dfs function for each cell in this column, passing the pac set as the visit parameter.
Finally, iterate through the last column (c = COLS - 1) and call the dfs function for each cell in this column, using the atl set for visit.
After these four loops, you will have marked cells that can reach the Pacific Ocean in the pac set and cells that can reach the Atlantic Ocean in the atl set.
Create an empty list res to store the result.
Iterate through every cell in the grid using two nested loops.

For each cell at position (r, c), check if it exists in both pac and atl sets.

If it does, add it to the res list as a coordinate [r, c].

Finally, return the res list as the output, which contains coordinates of cells that can reach both the Pacific and Atlantic Oceans.

Here's the efficient Python code solution:

View on GitHub ➹

def pac

ificAtlantic(self, heights: List[List[int]]) -&gt; List[List[int]]:
    ROWS, COLS = len(heights), len(heights[0])
    pac, atl = set(), set()

    def dfs(r, c, visit, prevHeight):
        if (
            (r, c) in visit
            or r &lt; 0
            or c &lt; 0
            or r == ROWS
            or c == COLS
            or heights[r][c] &lt; prevHeight
        ):
            return
        visit.add((r, c))
        dfs(r + 1, c, visit, heights[r][c])
        dfs(r - 1, c, visit, heights[r][c])
        dfs(r, c + 1, visit, heights[r][c])
        dfs(r, c - 1, visit, heights[r][c])

    for c in range(COLS):
        dfs(0, c, pac, heights[0][c])
        dfs(ROWS - 1, c, atl, heights[ROWS - 1][c])

    for r in range(ROWS):
        dfs(r, 0, pac, heights[r][0])
        dfs(r, COLS - 1, atl, heights[r][COLS - 1])

    res = []
    for r in range(ROWS):
        for c in range(COLS):
            if (r, c) in pac and (r, c) in atl:
                res.append([r, c])
    return res

Now, let's understand the time and space complexity of this solution.

Time and Space Complexity

The time complexity of our efficient approach is O(m * n), where m represents the number of rows and n represents the number of columns in the grid.

This is because we perform a single depth-first search for each cell, and we ensure that each cell is visited at most once.

The space complexity is also O(m * n) due to the space used by the pac and atl sets, which can store up to m * n unique cell coordinates.

Reasoning Behind Our Approach

The reasoning behind our efficient approach is to use depth-first search (DFS) to traverse the grid while keeping track of cells that can reach the Pacific Ocean and the Atlantic Ocean.

By starting from the border cells connected to the oceans and marking cells that are reachable, we can efficiently identify cells that can reach both oceans.

This approach reduces the number of repeated DFS calls, making it a fast and optimal solution.

Conclusion

In this blog post, we've explored the Pacific Atlantic Water Flow problem on LeetCode.

We've provided a Python solution that efficiently identifies cells on a rectangular island that can send rainwater to both the Pacific and Atlantic Oceans.

Our solution is optimized for larger grids and meets the problem's constraints.

If you found this post helpful, please like and engage to support our our platform.

If you have any questions or suggestions, please feel free to comment and share your thoughts.

Coding challenges are a great way to improve your problem-solving skills, and we hope you enjoyed this one!

Question Link: Pacific Atlantic Water Flow on LeetCode

Happy coding!