417. Pacific Atlantic Water Flow

go-leetcode-417.go

/*
417. Pacific Atlantic Water Flow

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:
The order of returned grid coordinates does not matter.
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).




Think:
In the beginning, I did NOT get what are the start points for the flows. Literally, the question only mentions 
"find the flow which reaches Pacific and Atlantic oceans". Therefore, there're no start points.

Well, let's move on. If there's no start spot, can we find the list or spots that can reach the oceans? Yes, for sure,
we can use dfs/bfs "on every cell/spot" and find out which flows would eventually move toward oceans. 
So the formula could denote as 

c < 0 || c >= C,   or r < 0 || r >= R

Given that c stands for column, C represent size of columns in matrix, r stands for row, and R represents size of rows in Matrix 

It's good step. However, it costs too high, O(mxnxmxn) time complexity, since every spots you have to traverse to confirm whether the flow can 
reach oceans. The solution beats 0% with 116ms in golang. Poor performance.

On the other hand, can we concern abount just the boundaries？

c == 0 || c == C-1,   or r == 0 || r == R-1

We can start with this POV. we reverse the procedure. we traverse which paths can reach to those boundaries.
We eliminiate the points into (2x(M+N)), so the time complexity would be O((M+N)xMxN) by DFS/BFS. The different port is that we check a flow from instead,
because we don't know where the start points are from this POV.
Then, we can check out both of the paths if there're intersections.
which means a path exists, and is capable of reaching to both sides,   

visited_P[r][c] && visited_A[r][c]

Checking the paths costs O(MxN) time complexity. Now, We can beats 77.72% submissions with 60ms.
The space complexity would be O(2xMxN) for both sides reachable paths

*/
func pacificAtlantic(matrix [][]int) [][]int {
    
    if matrix == nil || (matrix != nil && len(matrix)<1) {
        return nil
    }
    rst := [][]int{}
    m, n := len(matrix), len(matrix[0])
    visited_P := make([][]bool, m)
    visited_A := make([][]bool, m)
    for i:=0; i < m; i++ {
        visited_P[i] = make([]bool,n)
        visited_A[i] = make([]bool,n)
    }
    for i:=0; i < m; i++ {
        dfs(matrix, visited_P, i, 0)
        dfs(matrix, visited_A, i, n-1)        
    }
    for i:=0; i < n; i++ {
        dfs(matrix, visited_P, 0, i)
        dfs(matrix, visited_A, m-1, i)        
    }
    // fmt.Println(visited_P)
    // fmt.Println(visited_A)
    for r:=0 ; r < m; r++ {
        for c :=0 ; c < n; c++ {
            if visited_P[r][c] && visited_A[r][c] {
                rst = append(rst, []int{r,c})
            }
        }
    }
    
    return rst
}
func dfs(matrix [][]int, visited [][]bool, r, c int) {
    
    dir := [][]int{{0,-1},{0,1},{1,0},{-1,0}}
    m, n := len(matrix), len(matrix[0])
    visited[r][c] = true
    for _, d := range dir {
        R, C := r+d[0], c+d[1]
        if 0 <= R && 0 <= C && R < m && C < n && !visited[R][C] && matrix[r][c] <= matrix[R][C] {
            dfs(matrix, visited, R,C)
            
        }
    }
}