Second solution: From all locations where water flows in (pacific and atlantic coasts), see how far the water would flow in the land and mark those locations as reachable by both pacific and atlantic coasts. Then at the end, locations which were reachable by both coasts will be added to the final se
(matrix [][]int)
| 7 | // by both pacific and atlantic coasts. Then at the end, locations which were reachable |
| 8 | // by both coasts will be added to the final set of coordinates to return. |
| 9 | func pacificAtlantic(matrix [][]int) [][]int { |
| 10 | if len(matrix) == 0 { |
| 11 | return matrix |
| 12 | } |
| 13 | |
| 14 | // create matrices to represent where water can flow |
| 15 | // into the land from the pacific and the atlantic |
| 16 | pacific := make([][]bool, len(matrix)) |
| 17 | for i := range pacific { |
| 18 | pacific[i] = make([]bool, len(matrix[0])) |
| 19 | } |
| 20 | atlantic := make([][]bool, len(matrix)) |
| 21 | for i := range atlantic { |
| 22 | atlantic[i] = make([]bool, len(matrix[0])) |
| 23 | } |
| 24 | |
| 25 | // explore from the east (atlantic) and west (pacific), |
| 26 | // marking each spot the water could flow into the land. |
| 27 | for r := 0; r < len(matrix); r++ { |
| 28 | explore(matrix, &pacific, math.MinInt32, r, 0) |
| 29 | explore(matrix, &atlantic, math.MinInt32, r, len(matrix[0])-1) |
| 30 | } |
| 31 | |
| 32 | // explore from the south (atlantic) and north (pacific), |
| 33 | // marking each spot the water could flow into the land. |
| 34 | for c := 0; c < len(matrix[0]); c++ { |
| 35 | explore(matrix, &pacific, math.MinInt32, 0, c) |
| 36 | explore(matrix, &atlantic, math.MinInt32, len(matrix)-1, c) |
| 37 | } |
| 38 | |
| 39 | // coordinates that had atlantic and pacific ocean flow into them are returned |
| 40 | coordinates := make([][]int, 0) |
| 41 | for r := 0; r < len(matrix); r++ { |
| 42 | for c := 0; c < len(matrix[r]); c++ { |
| 43 | if pacific[r][c] && atlantic[r][c] { |
| 44 | coordinates = append(coordinates, []int{r, c}) |
| 45 | } |
| 46 | } |
| 47 | } |
| 48 | |
| 49 | return coordinates |
| 50 | } |
| 51 | |
| 52 | func explore(matrix [][]int, visited *[][]bool, prev, r, c int) { |
| 53 | v := *visited |