Pacific Atlantic Water Flow

Medium

Question

You're given a 2D array which represents the birds-eye view of mountain peaks, where each cell contains that land's height. This mountain is on an island surrounded by oceans - the Pacific Ocean on the north-west edges, and Atlantic Ocean at south-east edges.

When it rains, water can flow in the four cardinal directions (north, west, south, east), however water must follow gravity - it flows toward land that's equal or lower in height.

Give a list of cell coordinates where the rain water there can end up flowing down to both the Pacific or Atlantic oceans.

Input: heights = [[2, 2, 3], [6, 7, 2], [8, 7, 1]]

Output: [(0, 2), (1, 1), (2, 0), (2, 1)]

Every coordinate in the result list can have water flowing to both the Pacific Ocean, or the Atlantic Ocean.

For example...

water at (0, 2) = 3 can flow north into the Pacific, or east into the Atlantic
water at (1, 1) = 7 can flow west > west into the Pacific, or east > south > east into the Atlantic
water at (2, 1) = 7 can flow north > north > west > west into the Pacific, or south into the Atlantic

Note: There are multiple paths that water could flow in each of these coordinates. These are just a couple selected examples.

Input: heights = [[2, 1], [1, 3]]

Output: [(0, 0), (0, 1), (1, 0), (1, 1)]

Every spot on the mountain can have water flowing to both Pacific and Atlantic oceans.

For example...

water at [0, 0] = 2 can flow north into the Pacific, or east > east into the Atlantic
water at [1, 0] = 1 can flow west into the Pacific, or south into the Atlantic
water at [1, 1] = 3 can flow west > west into the Pacific, or south into the Atlantic

Input: heights = [[1, 2, 3, 4], [1, 7, 3, 8], [3, 5, 1, 2], [8, 3, 1, 8]]

Output: [(0, 2), (0, 3), (1, 1), (1, 2), (1, 3), (2, 1), (3, 0)]

The water at the coordinates in the result list can flow to both Pacific and Atlantic oceans.

For example...

water at (1, 1) = 7 can flow north > north into the Pacific, or east > south > east > east into the Atlantic
water at (1, 2) = 3 can flow north > north into the Pacific, or south > south > south into the Atlantic
water at (2, 1) = 5 can flow west > west into the Pacific, or south > south into the Atlantic