Pacific Atlantic Water Flow
You are given a grid heights of non-negative integers, where heights[r][c] is the height of the cell in row r and column c. The Pacific ocean touches the top row and the left column. The Atlantic ocean touches the bottom row and the right column.
Water can flow from a cell to a neighboring cell (up, down, left or right) if the neighbor is equally high or lower. Water can flow from a cell on the edge into the ocean next to that edge. Return every cell from which water can flow to both oceans, as a list of [row, column] pairs sorted by row and then by column.
Examples
Darker cells hold bigger numbers. Outlined cells are the answer: rain on them can flow to both oceans.
Darker cells hold bigger numbers. Outlined cells are the answer: rain on them can flow to both oceans.
Darker cells hold bigger numbers. Outlined cells are the answer: rain on them can flow to both oceans.
Constraints
- 1 <= number of rows, number of columns <= 200
- 0 <= heights[r][c] <= 100,000
Stuck? Take one hint at a time
Common mistakes
- Searching forwards from every cell and so doing quadratic work.
- Using the wrong direction in the reverse search: going backwards you move to neighbors that are at least as high, not lower.
- Starting the Pacific search only from the top row and forgetting the left column, or the same slip for the Atlantic.
- Using strict comparison, which blocks water on flat ground. Equal heights do allow flow.
- Recursing on a 200 by 200 grid, which can exceed the stack in some languages. Use a queue or a stack.
Questions an interviewer may ask next
- Water may also flow diagonally. What changes in the code, and in the answer?
- Water flows only to strictly lower neighbors. How do the searches change, and what happens on flat plateaus?
- There are three oceans along different edges. How does the idea generalize? (One reverse search per ocean, then intersect.)
- The grid is too large to hold two seen grids at once. Can you reduce the memory? (Mark each cell with two bits in one grid, or run the Pacific search first and keep only its bit.)
[[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]]
[[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.