A grid of heights touches the Pacific on its top and left edges, and the Atlantic on its bottom and right edges. Water flows from a cell to a neighbour with equal or lower height. Return every cell from which water can reach both oceans.
DSA Animator › DSA Revision › Graph › Pacific Atlantic Water Flow
Remember: when many sources ask the same question, search backwards from the targets. Flowing down becomes climbing up. The video solves Pacific Atlantic Water Flow (LeetCode 417, Medium) with the Reverse Multi-Source DFS pattern from the Graph topic, and you can replay every step in the interactive Pacific Atlantic Water Flow animation.
A grid of heights touches the Pacific on its top and left edges, and the Atlantic on its bottom and right edges. Water flows from a cell to a neighbour with equal or lower height. Return every cell from which water can reach both oceans.
For the classic 5 by 5 grid, seven cells can reach both oceans. They are 0 4, 1 3, 1 4, 2 2, 3 0, 3 1 and 4 0.
Starting a search from every single cell, and checking whether it reaches each ocean, repeats the same work again and again. That is O of the grid size squared.
Turn the question around, and let water climb up from the oceans instead. From the Pacific edges, move to neighbours that are equal or higher, and mark everything you reach. Do the same from the Atlantic edges with a second marking. A cell reachable in both searches can drain into both oceans.
Start the Pacific search from the top row and the left column. Climbing uphill marks 16 cells, mostly in the top left part. Start the Atlantic search from the bottom row and the right column. It also marks 16 cells, mostly in the bottom right part. The cells marked by both are the answer. There are seven of them, including the peak of height 5 in the centre.
In code, keep two boolean grids, one for each ocean. Run a DFS from every edge cell of each ocean. The DFS moves to a neighbour only if it is inside the grid, not visited, and at least as high. Collect cells true in both grids, so it's O of rows times columns.
Remember: when many sources ask the same question, search backwards from the targets. Flowing down becomes climbing up.