Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Pacific Atlantic Water Flow (medium)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement:

You are given a matrix grid of size m x n, where each matrix[i][j] represents the height of the Island at i<sup>th</sup> row and j<sup>th</sup> column position from the sea level. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges.

Due to heavy rain, there is a lot of water on each cell of the island. It is given that 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 result, where result[i] = [r<sub>i</sub>, c<sub>i</sub>] represents that rainwater can flow from cell (r<sub>i</sub>, c<sub>i</sub>) to both the Pacific and Atlantic oceans.

Example 1:

  • Input: matrix =
[[1,2,2,3],
 [3,2,3,4],
 [2,4,5,3],
 [5,7,1,4]]
  • Expected Output: [[0, 3], [1, 3], [2, 2], [3, 0], [3, 1]]
Image
  • Justification: The cells that can flow to both the Pacific and Atlantic oceans are [[0, 3], [1, 3], [2, 2], [3, 0], [3, 1]]
    • [0,3]:
      • [0, 3] -> Pacific Ocean.
      • [0, 3] -> Atlantic Ocean.
    • [1,3]:
      • [1, 3] -> [0, 3] -> Pacific Ocean.
      • [1, 3] -> Atlantic Ocean.
    • [2, 2]:
      • [2, 2] -> [1, 2] -> [0, 2] -> Pacific Ocean.
      • [2, 2] -> [2, 3] -> Atlantic Ocean.
    • [3,0]:
      • [3, 0] -> Pacific Ocean.
      • [3, 0] -> Atlantic Ocean.
    • [3,1]:
      • [3, 1] -> [3, 0] -> Pacific Ocean.
      • [3, 1] -> Atlantic Ocean.

Example 2:

  • Input: matrix =
[[1,2,3],
 [4,5,6],
 [7,8,9]]
  • Expected Output: [[0,2],[1,2],[2,0],[2,1],[2,2]]
Image
  • Justification: The cells that can flow to both the Pacific and Atlantic oceans are
    • [0,2]:
      • [0, 2] -> Pacific Ocean.
      • [0, 2] -> Atlantic Ocean.
    • [1,2]:
      • [1,2] -> [0,2] -> Pacific Ocean.
      • [1,2] -> Atlantic Ocean.
    • [2,0]:
      • [2, 0] -> Pacific Ocean.
      • [2, 0] -> Atlantic Ocean.
    • [2,1]:
      • [2,1] -> [1,1] -> [1, 0] -> Pacific Ocean.
      • [2,1] -> Atlantic Ocean.
    • [2,2]:
      • [2, 2] -> Pacific Ocean.
      • [2, 2] -> Atlantic Ocean.

Example 3:

  • Input: matrix =
[[10,10,10],
 [10,1,10],
 [10,10,10]]
  • Expected Output: [[0,0],[0,1],[0,2],[1,0],[1,2],[2,0],[2,1],[2,2]]
Image
  • Justification: The water can flow to both oceans from all cells except from the central cell [1,1].

Constraints:

  • m == matrix.length
  • n == matrix[r].length
  • 1 <= m, n <= 200
  • 0 <= matrix[r][c] <= 10<sup>5</sup>

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible