Problem Statement:

Given a matrix m x n that represents the height of each unit cell in a Island, determine which cells can have water flow to both the Pacific and Atlantic oceans. The Pacific ocean touches the left and top edges of the continent, while the Atlantic ocean touches the right and bottom edges.

From each cell, water can only flow to adjacent cells (top, bottom, left, or right) if the adjacent cell's height is less than or equal to the current cell's height.

We need to return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

Example 1:

• Input: [[1,2,3],[4,5,6],[7,8,9]]

• Expected Output: [[0,2],[1,2],[2,0],[2,1],[2,2]]

• Justification: The cells that can flow to both the Pacific and Atlantic oceans are

  • [0,2]:

    • To Pacific Ocean: Directly from [0,2] since it's on the top border.
    • To Atlantic Ocean: [0,2] -> [1,2] -> [2,2].

  • [1,2]:

    • To Pacific Ocean: [1,2] -> [0,2].
    • To Atlantic Ocean: [1,2] -> [2,2].

  • [2,0]:

    • To Pacific Ocean: Directly from [2,0] since it's on the left border.
    • To Atlantic Ocean: [2,0] -> [2,1].

  • [2,1]:

    • To Pacific Ocean: [2,1] -> [2,0].
    • To Atlantic Ocean: [2,1] -> [2,2].

  • [2,2]:

    • To Pacific Ocean: [2,2] -> [1,2] -> [0,2].
    • To Atlantic Ocean: Directly from [2,2] since it's on the bottom-right corner.

Example 2:

• Input: [[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]]
• Justification: The water can flow to both oceans from all cells except from the central cell [1,1].

Example 3:

• Input: [[5,4,3],[4,3,2],[3,2,1]]
• Expected Output: [[0,0],[0,1],[0,2],[1,0],[2,0]]
• Justification: All the leftmost cells can have water flowing to both oceans. Similarly, top cells also satisfy the criteria.

Constraints:

• m == matrix.length
• n == matrix[r].length
• 1 <= m, n <= 200
• 0 <= matrix[r][c] <= 10⁵

Try it yourself

Try solving this question here: