417 — Pacific Atlantic Water Flow
Restating Info We’re Already Given:
- Treating the matrix like a map, the north and west borders are the Pacific Ocean and the south and east borders are the Atlantic Ocean.
- Following the map analogy, each value represents the altitude at that (row, col) pair and thus water will flow from higher to lower (or same altitude) ground.
- Water only flows in 4 directions, not 8.
Questions/Clarifications to Possibly Ask Interviewer (If starting information we’re given isn’t sufficient to begin):
- To confirm, if we have a 1 x 1, 1 x n, or m x 1 matrix, then we should return every index pair?
Discuss Naive Solution:
Naively, we could BFS from each index pair to see if from there, water can reach both oceans. For pairs that can reach both oceans, we add them to a result array and return it. However, this isn’t efficient as we’re going to be doing a lot of recalculations. One run of BFS has a runtime of |V| +|E|, and a m x n matrix has (m x n) nodes and ((m-1 * n) + (m*n-1)) edges for a runtime of O(m*n). When run on each index pair (m *n of them), this makes for a total runtime of O(m²n²).
Discuss Alternative Solution:
The heights matrix does not change. Thus, we know that once we have determined whether an index pair can reach either ocean, that it will never change. To improve upon the previous solution, we could use 2 sets to cache index pairs that reach each ocean. That way, during our BFS, we can check for any index whether the result has been calculated to avoid performing recalculations.
Discuss Optimal Solution:
Instead, we could begin our BFS search from both oceans. Expanding inward from the metaphorical coast, we can return a list of indices reachable from that ocean and return the intersection of the indices reachable from both oceans respectively.
Code Optimal Solution:
Runtime/Space Complexity:
The runtime complexity is O(m*n) because for a matrix with all values equal, we have to visit each index pair twice (once each for Pacific and Atlantic BFS searches).
The space complexity is O(m*n). This worst case scenario occurs for a heights matrix that is a 1 x 1, 1 x n, or m x 1 matrix as the pacificBorder and atlanticBorder deques contain m * n pairs.
Test Cases:
- 1 x 1 matrix
- 1 x n matrix
- m x 1 matrix
- m x n matrix
