Limited Time Offer:30% off Hello Interview Premium 🎉

Back to Main

Learn DSA

Introduction

Two Pointers

Overview

Container With Most Water

3-Sum

Triangle Numbers

Move Zeroes

Sort Colors

Trapping Rain Water

Sliding Window

Overview

Longest Substring Without Repeating Characters

Longest Repeating Character Replacement

Overview

Maximum Sum of Subarrays of Size K

Max Points You Can Obtain From Cards

Max Sum of Distinct Subarrays Length k

Intervals

Overview

Can Attend Meetings

Insert Interval

Non-Overlapping Intervals

Merge Intervals

Employee Free Time

Stack

Overview

Valid Parentheses

Decode String

Longest Valid Parentheses

Overview

Daily Temperatures

Largest Rectangle in Histogram

Linked List

Overview

Linked List Cycle

Palindrome Linked List

Remove Nth Node From End of List

Reorder List

Swap Nodes in Pairs

Binary Search

Overview

Apple Harvest (Koko Eating Bananas)

Search in Rotated Sorted Array

Heap

Overview

Kth Largest Element in an Array

K Closest Points to Origin

Find K Closest Elements

Merge K Sorted Lists

Breadth-First Search

Introduction

Overview

Level Order Sum

Rightmost Node

Zigzag Level Order

Maximum Width of Binary Tree

Graphs Overview

Minimum Knight Moves

Rotting Oranges

01-Matrix

Bus Routes

Backtracking

Overview

Word Search

Solution Space Trees

Subsets

Generate Parentheses

Combination Sum

Graphs

Overview

Course Schedule

Course Schedule II

Dynamic Programming

Fundamentals

Solving a Question with Dynamic Programming

Counting Bits

Decode Ways

Maximal Square

Unique Paths

Longest Increasing Subsequence

Word Break

Maximum Profit in Job Scheduling

Greedy Algorithms

Overview

Best Time to Buy and Sell Stock

Gas Station

Jump Game

Trie

Overview

Implement Trie Methods

Prefix Matching

Prefix Sum

Overview

Count Vowels in Substrings

Subarray Sum Equals K

Matrices

Spiral Matrix

Rotate Image

Set Matrix Zeroes

Pricing

Become a Coach

⌘K

Pricing Become a Coach

Get Premium

Depth-First Search

Pacific Atlantic Water Flow

medium

DESCRIPTION (credit Leetcode.com)

You are given an m x n matrix of non-negative integers representing a grid of land. Each value in the grid represents the height of that piece of land.

The Pacific Ocean touches the left and top edges of the matrix, while the Atlantic Ocean touches the right and bottom edges. Water can only flow from a cell to its neighboring cells directly north, south, east, or west, but only if the height of the neighboring cell is equal to or lower than the current cell.

Water can flow from grid[3][2] to the neighboring cells with a lower height.

Write a function to return a list of grid coordinates (i, j) where water can flow to both the Pacific and Atlantic Oceans. Water can flow from all cells directly adjacent to the ocean into that ocean.

Example 1:

Input:


grid = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

Water can flow from the cells with circles above to both the Pacific and Atlantic Oceans

Output:


[
    [0, 2],
    [1, 2],
    [2, 0],
    [2, 1],
    [2, 2]
]

Explanation

To solve this question, we need to traverse the grid to find all cells where water can flow to both the Pacific and Atlantic Oceans, and then find the cells that are contained in both those sets.

Approach 1: Brute Force Approach

Let's focus on how to find all the cells that are reachable from an ocean. One straightforward approach is to iterate over each cell in the graph, and then check if there is a valid path from that cell to the ocean. If there is, we can add it to a set (depending on if it reaches the Pacific or Atlantic Ocean). After iterating over each cell, we can return the intersection of those two sets.

class Solution:
    def pacificAtlantic(self, matrix):
        if not matrix or not matrix[0]:
            return []

        rows, cols = len(matrix), len(matrix[0])
        pacific = set()
        atlantic = set()

        # Try to find a path from r, c to the Pacific or Atlantic ocean
        # via neighboring cells with lower heights
        def dfs(start_r, start_c, r, c, visited):
            if (r, c) in visited:
                return
            
            visited[(r, c)] = True

            if r == 0 or c == 0:
                pacific.add((start_r, start_c))
            if r == rows - 1 or c == cols - 1:
                atlantic.add((start_r, start_c))

            directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] <= matrix[r][c]:
                    dfs(start_r, start_c, nr, nc, visited)
                    visited[(nr, nc)] = False

        # Perform full DFS from each cell.
        for r in range(rows):
            for c in range(cols):
                visited = {}
                dfs(r, c, r, c, visited)
                
        return list(pacific & atlantic)

The problem with this approach is that it is very inefficient. For each cell, we have to perform a full DFS traversal of the entire grid in the worst case, resulting in a run-time of O((m x n)²).

Approach 2: Boundary DFS

The brute-force approach is inefficient because there is a lot of repeat work being done. For example, we have to calculate parts of the same path multiple times as we check if there is a valid path from a cell to the ocean.

The three seperate calls to dfs in the brute-force solution above would calculate parts of the same path multiple times.

A more efficient approach is to use "boundary DFS". With this approach, we "invert" the problem by starting from all cells adjacent to each ocean, and then use DFS to find cells that can flow into that cell. All the cells that we visit during each of these traversals are the set of cells that can flow into the ocean that the DFS originated from.

This is more efficient because it reduces redundant work - once we visit a cell using this traversal, we can mark it as visited so it is not visited by future traversals.

At the end, we can return the intersection of both sets to get the final answer.

Solution

class Solution:
    def pacific_atlantic_flow(self, grid): 
        if not grid or not grid[0]:
            return []

        rows, cols = len(grid), len(grid[0])
        # Step 1: Initialize empty sets
        pacific_reachable = set()
        atlantic_reachable = set()

        def dfs(r, c, reachable):
            reachable.add((r, c))
            for dr, dc in [(1,0), (-1,0), (0,1), (0,-1)]:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    if (nr, nc) not in reachable and grid[nr][nc] >= grid[r][c]:
                        dfs(nr, nc, reachable)

        # initializes DFS from all cells in the Atlantic and Pacific Oceans
        # Note how we share a single visited set
        # across DFS calls that originate from the same ocean
        for r in range(rows):
            dfs(r, 0, pacific_reachable)
            dfs(r, cols - 1, atlantic_reachable)

        for c in range(cols):
            dfs(0, c, pacific_reachable)
            dfs(rows - 1, c, atlantic_reachable)

        # return the intersection of both sets.
        return list(pacific_reachable & atlantic_reachable)

Complexity Analysis

Time Complexity: In Approach #2, we visit each cell once aross all DFS calls that originate from a particular ocean, In the worst case, this means we visit each cell twice, for a total time complextiy of O(m * n). Space Complexity: O(m * n) for the two visited sets that we have to maintain for the DFS traversals.

Next: Introduction

Your account is free and you can post anonymously if you choose.

Sort By

Depth-First Search

Pacific Atlantic Water Flow

DESCRIPTION (credit Leetcode.com)

Explanation

Approach 1: Brute Force Approach

Approach 2: Boundary DFS

Solution

Complexity Analysis

Questions

Learn

Links

Legal

Contact