417. Pacific Atlantic Water Flow #

Problem #

Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the “Pacific ocean” touches the left and top edges of the matrix and the “Atlantic ocean” touches the right and bottom edges.

Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.

Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.

Note:

1. The order of returned grid coordinates does not matter.
2. Both m and n are less than 150.

Example:

Given the following 5x5 matrix:

  Pacific ~   ~   ~   ~   ~
       ~  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  *
          *   *   *   *   * Atlantic

Return:

[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).

Problem Summary #

Given an m x n matrix of non-negative integers representing the height of each cell on a continent. The “Pacific Ocean” is on the left and top edges of the continent, while the “Atlantic Ocean” is on the right and bottom edges. Water can only flow in the four directions up, down, left, and right, and can only flow from higher to lower elevation or on the same elevation. Find the coordinates of the land cells where water can flow to both the “Pacific Ocean” and the “Atlantic Ocean”.

Solution Approach #

• Brute-force solution: use DFS to search the two-dimensional data once in row-major order, marking the positions that water from the Pacific and Atlantic can reach respectively. Then search once in column-major order, marking the positions that water from the Pacific and Atlantic can reach. Finally, the coordinates that both can reach are the required answer.

Code #

package leetcode

import "math"

func pacificAtlantic(matrix [][]int) [][]int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return nil
	}
	row, col, res := len(matrix), len(matrix[0]), make([][]int, 0)
	pacific, atlantic := make([][]bool, row), make([][]bool, row)
	for i := 0; i < row; i++ {
		pacific[i] = make([]bool, col)
		atlantic[i] = make([]bool, col)
	}
	for i := 0; i < row; i++ {
		dfs(matrix, i, 0, &pacific, math.MinInt32)
		dfs(matrix, i, col-1, &atlantic, math.MinInt32)
	}
	for j := 0; j < col; j++ {
		dfs(matrix, 0, j, &pacific, math.MinInt32)
		dfs(matrix, row-1, j, &atlantic, math.MinInt32)
	}
	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if atlantic[i][j] && pacific[i][j] {
				res = append(res, []int{i, j})
			}
		}
	}
	return res
}

func dfs(matrix [][]int, row, col int, visited *[][]bool, height int) {
	if row < 0 || row >= len(matrix) || col < 0 || col >= len(matrix[0]) {
		return
	}
	if (*visited)[row][col] || matrix[row][col] < height {
		return
	}
	(*visited)[row][col] = true
	dfs(matrix, row+1, col, visited, matrix[row][col])
	dfs(matrix, row-1, col, visited, matrix[row][col])
	dfs(matrix, row, col+1, visited, matrix[row][col])
	dfs(matrix, row, col-1, visited, matrix[row][col])
}