What is the time complexity of Pacific Atlantic Water Flow?

The optimal solution has a time complexity of O(m*n).

What is the space complexity of Pacific Atlantic Water Flow?

The space complexity is O(m*n).

What data structures are used to solve Pacific Atlantic Water Flow?

This problem uses Array, Depth-First Search, Breadth-First Search, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Pacific Atlantic Water Flow?

Insight 1: Instead of starting from each cell and trying to reach both oceans (which would be inefficient), it's much more efficient to start from the oceans and find all cells reachable from them. Insight 2: We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid from the edges (oceans) and mark the cells that are reachable.

Which companies ask LeetCode 417. Pacific Atlantic Water Flow in interviews?

This problem is frequently asked at Coupang, Nutanix, ServiceNow.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Pacific Atlantic Water Flow - LeetCode 417 Solution

Pacific Atlantic Water Flow - Complete Solution Guide

Pacific Atlantic Water Flow is LeetCode problem 417, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 d

Detailed Explanation

The problem asks us to find all cells in a given `m x n` matrix (representing an island's heights) from which water can flow to both the Pacific and Atlantic oceans. The Pacific Ocean touches the top and left edges, and the Atlantic Ocean touches the bottom and right edges. Water can only flow from a cell to its neighboring cells (north, south, east, west) if the neighboring cell's height is less than or equal to the current cell's height. We need to return a list of coordinates `[r, c]` that can reach both oceans.

Solution Approach

The solution uses Breadth-First Search (BFS) to find all cells reachable from the Pacific and Atlantic oceans, respectively. It initializes two sets, `pacific_reachable` and `atlantic_reachable`, to keep track of the cells reachable from each ocean. It starts BFS from all edge cells adjacent to the Pacific and Atlantic. The BFS explores adjacent cells only if their height is greater than or equal to the current cell's height. Finally, it finds the intersection of the two sets to identify cells reachable from both oceans.

Step-by-Step Algorithm

Step 1: Create two sets, `pacific_reachable` and `atlantic_reachable`, to store the coordinates reachable from each ocean.
Step 2: Identify the starting cells for BFS from the Pacific Ocean (cells on the top and left edges) and the Atlantic Ocean (cells on the bottom and right edges).
Step 3: Perform BFS from the Pacific starting cells. In each step, explore the adjacent cells (up, down, left, right). Add the adjacent cell to `pacific_reachable` if it's within bounds, not already visited, and its height is greater than or equal to the current cell's height.
Step 4: Perform BFS from the Atlantic starting cells, similar to Step 3, but add reachable cells to `atlantic_reachable`.
Step 5: Find the intersection of `pacific_reachable` and `atlantic_reachable`. The cells in this intersection are reachable from both oceans.
Step 6: Convert the coordinates in the intersection set into a list of lists and return the result.

Key Insights

Insight 1: Instead of starting from each cell and trying to reach both oceans (which would be inefficient), it's much more efficient to start from the oceans and find all cells reachable from them.
Insight 2: We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid from the edges (oceans) and mark the cells that are reachable.
Insight 3: A crucial observation is that water flows from higher or equal height cells to lower height cells or to the ocean. This means we should explore the grid starting from the ocean boundaries and moving to the inland cells with heights equal to or greater than the current cell.

Complexity Analysis

Time Complexity: O(m*n)

Space Complexity: O(m*n)

Topics

This problem involves: Array, Depth-First Search, Breadth-First Search, Matrix.

Companies

Asked at: Coupang, Nutanix, ServiceNow.

Pacific Atlantic Water Flow | LeetCode 417

Medium

Array Depth-First Search Breadth-First Search Matrix

Time: O(m*n)Space: O(m*n)

Solution Code

Available in:

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.HashSet;

class Solution {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        if (heights == null || heights.length == 0 || heights[0].length == 0) {
            return new ArrayList<>();
        }

        int m = heights.length;
        int n = heights[0].length;

        class Pair {
            int row, col;

            public Pair(int row, int col) {
                this.row = row;
                this.col = col;
            }

            @Override
            public boolean equals(Object o) {
                if (this == o) return true;
                if (o == null || getClass() != o.getClass()) return false;
                Pair pair = (Pair) o;
                return row == pair.row && col == pair.col;
            }

            @Override
            public int hashCode() {
                int result = row;
                result = 31 * result + col;
                return result;
            }
        }

        
        
        

        
        
        
        

        
        
        
        
        
        

        

        

        

        

        Set<Pair> pacificReachable = bfs(heights, getPacificStarts(heights));
        Set<Pair> atlanticReachable = bfs(heights, getAtlanticStarts(heights));

        Set<Pair> resultSet = new HashSet<>(pacificReachable);
        resultSet.retainAll(atlanticReachable);

        List<List<Integer>> result = new ArrayList<>();
        for (Pair coord : resultSet) {
            List<Integer> list = new ArrayList<>();
            list.add(coord.row);
            list.add(coord.col);
            result.add(list);
        }

        return result;
    }

    private Set<Pair> bfs(int[][] heights, List<Pair> starts) {
        int m = heights.length;
        int n = heights[0].length;
        Queue<Pair> queue = new LinkedList<>(starts);
        Set<Pair> reachable = new HashSet<>(starts);

        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            Pair current = queue.poll();
            int row = current.row;
            int col = current.col;

            for (int[] dir : directions) {
                int r = row + dir[0];
                int c = col + dir[1];

                if (r >= 0 && r < m && c >= 0 && c < n) {
                    Pair neighbor = new Pair(r, c);
                    if (!reachable.contains(neighbor) && heights[r][c] >= heights[row][col]) {
                        reachable.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
        }
        return reachable;
    }

    private List<Pair> getPacificStarts(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        List<Pair> starts = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            starts.add(new Pair(r, 0));
        }
        for (int c = 1; c < n; c++) {
            starts.add(new Pair(0, c));
        }
        return starts;
    }

    private List<Pair> getAtlanticStarts(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        List<Pair> starts = new ArrayList<>();
        for (int r = 0; r < m; r++) {
            starts.add(new Pair(r, n - 1));
        }
        for (int c = 0; c < n - 1; c++) {
            starts.add(new Pair(m - 1, c));
        }
        return starts;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 417: Pacific Atlantic Water Flow - Detailed explanation and solution approaches.

Topics

Array Depth-First Search Breadth-First Search Matrix

Companies

CoupangNutanixServiceNow

Stats

Difficulty:Medium

Languages:4

Companies:3

Problem #:417

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

6 steps

1
Step 1: Create two sets, `pacific_reachable` and `atlantic_reachable`, to store the coordinates reachable from each ocean.
2
Step 2: Identify the starting cells for BFS from the Pacific Ocean (cells on the top and left edges) and the Atlantic Ocean (cells on the bottom and right edges).
3
Step 3: Perform BFS from the Pacific starting cells. In each step, explore the adjacent cells (up, down, left, right). Add the adjacent cell to `pacific_reachable` if it's within bounds, not already visited, and its height is greater than or equal to the current cell's height.
4
Step 4: Perform BFS from the Atlantic starting cells, similar to Step 3, but add reachable cells to `atlantic_reachable`.
5
Step 5: Find the intersection of `pacific_reachable` and `atlantic_reachable`. The cells in this intersection are reachable from both oceans.
6
Step 6: Convert the coordinates in the intersection set into a list of lists and return the result.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(m*n)

💾

Space Complexity

O(m*n)

📝

Why?

The time complexity arises because each cell in the matrix could be visited during the BFS traversals starting from both Pacific and Atlantic oceans. The space complexity results from storing the reachable cells from each ocean in respective sets, potentially storing all cells in the worst case. The BFS queue size is also bounded by O(m*n).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

Instead of BFS, we can use DFS to explore the reachable cells from each ocean. The overall logic remains the same, starting from the ocean boundaries and exploring adjacent cells with heights equal to or greater than the current cell's height.

Time: O(m*n)Space: O(m*n) in the worst case due to recursion depth, but practically might be smaller than BFS. In the best case, if the flow is largely constrained, the stack could be much smaller

Trade-offs: DFS can be more memory-efficient than BFS in some cases, but can also lead to stack overflow issues with large input grids. BFS guarantees to find the shortest path if that were relevant, while DFS may not.

✨

Key Insights

1Insight 1: Instead of starting from each cell and trying to reach both oceans (which would be inefficient), it's much more efficient to start from the oceans and find all cells reachable from them.
2Insight 2: We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the grid from the edges (oceans) and mark the cells that are reachable.
3Insight 3: A crucial observation is that water flows from higher or equal height cells to lower height cells or to the ocean. This means we should explore the grid starting from the ocean boundaries and moving to the inland cells with heights equal to or greater than the current cell.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Empty input `heights` matrix or a matrix with zero rows/columns. The code handles this by returning an empty list, as specified in the problem description.
Edge case 2: A matrix with only one cell (e.g., `[[1]]`). The code correctly identifies that this cell is reachable from both oceans and returns `[[0, 0]]`.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Starting the search from each cell in the matrix and trying to reach both oceans. This is highly inefficient and leads to TLE (Time Limit Exceeded) errors.

✗Common mistake 2: Not checking the bounds (row and column indices) of adjacent cells before exploring them, which can cause array index out-of-bounds errors.

✗Common mistake 3: Forgetting the equal height check when exploring adjacent cells. Water can flow to cells with the same height as the current cell.

✗Common mistake 4: Not marking visited nodes can cause infinite loops in the BFS/DFS traversal.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Analyzing water flow in geographical terrains, where the matrix represents terrain elevation and the algorithm determines which areas are reachable by rainwater from different water sources (oceans/rivers).

🏦Real-world scenario 2: Network routing, where the matrix represents network connectivity, and the algorithm identifies reachable nodes from different entry points.

🎮Real-world scenario 3: Image segmentation, where the matrix represents pixel intensities, and the algorithm groups pixels based on connectivity and intensity similarity.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 28, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 14

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 7

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Pacific Atlantic Water Flow"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?