Why it works
- Water runs from a cell down into a neighbour no higher than it. Reversed, a climb from the coast to neighbours at least as high reaches exactly the cells whose water can run down to that coast.
- So two climbs, one from each ocean’s coast, mark everything at once, instead of a separate downhill walk from every cell.
- A cell belongs to the answer exactly when both climbs reached it.
Complexity
Time O(rows × cols): each climb enters every cell at most once, and there are two climbs. Memory O(rows × cols) for the two sets and the call stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗