Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

145. Pacific Atlantic Water Flow

MediumDay 43 of 60Graphs

An m x n island has the Pacific Ocean touching its top and left edges and the Atlantic Ocean touching its bottom and right edges. heights[r][c] is the height of each cell. Rain water flows from a cell to a neighbour (up, down, left, right) if the neighbour's height is less than or equal to the current height, and flows into an ocean from any edge cell. Return the coordinates [r, c] of every cell from which water can reach both oceans, in any order.

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]]
For example, from [2,2] (height 5) water can go up and left to the Pacific and right and down to the Atlantic.
Example 2
Input: heights = [[1]]
Output: [[0,0]]
A single cell touches both oceans.
Constraints
  • 1 <= m, n <= 200
  • 0 <= heights[r][c] <= 10^5
Hints
Frequently asked at: Google, Amazon, Uber
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min