You get the height map heights of a rectangular island. It is an array of m rows, and each row is an array of n integers. Each number is the height of one square cell. Rows count from 0 at the top, and columns from 0 at the left.
The Pacific touches the island's top and left edges. The Atlantic touches its bottom and right edges.
Return every cell whose rain can reach both oceans, as a slice of [r, c] pairs. List them row by row from the top. Within a row, go from left to right.
Water flows from a cell to the cell directly above, below, left or right of it. It only flows to a cell that is no higher (lower or the same height). A cell on the edge of the island drains into the ocean on that side.
Example 1:
Input: heights = [ [3, 3, 4, 5], [2, 6, 7, 3], [1, 5, 4, 2], [4, 2, 1, 1] ] Output: [[0, 3], [1, 1], [1, 2], [2, 1], [3, 0]] Explanation: The corners [0, 3] and [3, 0] touch both oceans. Water from [1, 2] (height 7) flows to [0, 2] on the top edge. It also flows to [1, 3] on the right edge. Water from [2, 1] (height 5) flows to [2, 0] on the left edge. It also flows to [3, 1] on the bottom edge. Water from [1, 1] (height 6) flows down to [2, 1], then on from there. [2, 2] (height 4) is left out. Its water reaches the Atlantic. But the 7 above it and the 5 to its left block the way to the Pacific.
Example 2:
Input: heights = [[4, 2, 7]] Output: [[0, 0], [0, 1], [0, 2]] Explanation: There is only one row. Every cell is on both the top edge and the bottom edge.
Example 3:
Input: heights = [ [1, 4], [4, 1] ] Output: [[0, 1], [1, 0]] Explanation: [0, 0] touches only the Pacific. Both its neighbors are higher, so its water can't reach the Atlantic. [1, 1] touches only the Atlantic. It is stuck in the same way.
Constraints:
- 1 to 200 rows.
- 1 to 200 columns.
- All rows have the same length.
- Every height is from 0 to 100,000.
Note:
Your algorithm should run in O(m · n) time and use O(m · n) extra space.
You could follow the water down from every cell, with one search per cell. That can cost O((m · n)2). Think of a large flat lake in the middle of the island. Each cell's search wanders over the whole lake before it gives up. The tutorial turns the question around and climbs up from the oceans instead. A BFS starts from all the cells along the Pacific's edges at once. The BFS in 01 Matrix starts from all the zeros in the same way. It moves to a neighbor only when the neighbor is at least as high. That is because water from there could flow down to here. Every cell it reaches can send its water to the Pacific. A second BFS does the same from the Atlantic's edges. The answer is the cells that both searches reach. Each search visits every cell at most once.
Free plan: 30 tutor messages. PRO is unlimited.
