Pacific Atlantic Water Flow

Problem

Given an island height matrix, return the coordinates [r, c] from which water can flow to both the Pacific (top and left edges) and Atlantic (bottom and right edges) oceans, moving to neighbours of equal or lower height.

Run reverse BFS from each ocean border, moving to equal or higher neighbours, and intersect the reachable sets. Return coordinates sorted by row then column.

Hint

Reversing the flow means climbing to equal or taller neighbours from each coast.

Test cases

case 1

in: [[[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]]]

expected: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

case 2

in: [[[1]]]

expected: [[0,0]]

case 3

in: [[[2,1],[1,2]]]

expected: [[0,0],[0,1],[1,0],[1,1]]

case 4

in: [[[3,3],[3,3]]]

expected: [[0,0],[0,1],[1,0],[1,1]]

Starter codePython

def pacific_atlantic(heights):
    # Your code here
    pass

4 test cases · run your code against them in the editor