Pacific Atlantic Water Flow

Medium

The problem

heights[r][c] is the height of the land at that cell. Water on a cell can flow to a neighbour (up, down, left or right) that is the same height or lower. The Pacific ocean touches the top row and the left column, and the Atlantic touches the bottom row and the right column. Return every [row, column] from which water can reach both oceans.

Example 1
Input: heights = [[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]]
Output: [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
For example [0, 4] is on the top row (Pacific) and the right column (Atlantic) at the same time. The cells may be returned in any order.
Example 2
Input: heights = [[1]]
Output: [[0, 0]]
The one cell touches both oceans.

Limits

1 ≤ rows, columns ≤ 200
0 ≤ heights[r][c] ≤ 100,000
Rows and columns are counted from 0

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Reverse the question: start from the oceans and go uphill.

The idea

DFS/BFS from all Pacific border cells to cells that are equal or higher; same for Atlantic; answer is the intersection.

Target: O(m·n) time

Go function shape

func pacificAtlantic(heights [][]int) [][]int

Reference solution

Tested with go test. Try it yourself first, then compare.

// PacificAtlantic: instead of asking where each cell's water goes, start from each ocean's border and walk
// UPHILL (to neighbours that are equal or higher). Cells reached from both oceans are the answer.
func PacificAtlantic(heights [][]int) [][]int {
	rows, cols := len(heights), len(heights[0])
	pacific, atlantic := make([][]bool, rows), make([][]bool, rows)
	for i := range pacific {
		pacific[i], atlantic[i] = make([]bool, cols), make([]bool, cols)
	}
	var climb func(seen [][]bool, r, c int)
	climb = func(seen [][]bool, r, c int) {
		seen[r][c] = true
		for _, d := range [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
			nr, nc := r+d[0], c+d[1]
			if nr >= 0 && nc >= 0 && nr < rows && nc < cols && !seen[nr][nc] && heights[nr][nc] >= heights[r][c] {
				climb(seen, nr, nc)
			}
		}
	}
	for r := 0; r < rows; r++ {
		climb(pacific, r, 0)
		climb(atlantic, r, cols-1)
	}
	for c := 0; c < cols; c++ {
		climb(pacific, 0, c)
		climb(atlantic, rows-1, c)
	}
	out := [][]int{}
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if pacific[r][c] && atlantic[r][c] {
				out = append(out, []int{r, c})
			}
		}
	}
	return out
}

Read the lesson: Graphs: BFS / DFS / Topological Sort