Pacific Atlantic Water Flow Interview Question for Apple

## Data Structures & Algorithms: Pacific Atlantic Water Flow

This problem asks us to find all the cells in a matrix from which water can flow to both the Pacific and Atlantic oceans. The water can only flow to neighboring cells with heights less than or equal to the current cell. The Pacific Ocean borders the top and left edges, and the Atlantic Ocean borders the bottom and right edges.

### 1. Naive Solution (Brute Force)

The brute force approach would involve starting at each cell and performing a depth-first search (DFS) or breadth-first search (BFS) to check if it can reach both oceans. This would involve repeatedly exploring adjacent cells that are not higher than the current cell.

**Algorithm:**

1.  For each cell `(r, c)` in the matrix:
2.  Perform DFS/BFS to check if it can reach the Pacific Ocean.
3.  Perform DFS/BFS to check if it can reach the Atlantic Ocean.
4.  If it can reach both, add it to the result.

**Code (Python):**

```python
def pacific_atlantic_brute_force(heights):
    if not heights or not heights[0]:
        return []
    
    m, n = len(heights), len(heights[0])
    result = []
    
    def can_reach(r, c, ocean, visited):
        if ocean == 'pacific':
            if r < 0 or c < 0:
                return True
        else:
            if r == m or c == n:
                return True
        
        if r < 0 or r >= m or c < 0 or c >= n or (r, c) in visited:
            return False
            
        visited.add((r, c))

        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and heights[nr][nc] <= heights[r][c]:
                if can_reach(nr, nc, ocean, visited):
                    return True

        visited.remove((r,c))
        return False

    for r in range(m):
        for c in range(n):
            pacific_visited = set()
            atlantic_visited = set()
            if can_reach(r, c, 'pacific', pacific_visited) and can_reach(r, c, 'atlantic', atlantic_visited):
                result.append([r, c])
    
    return result

2. Optimal Solution (Reverse DFS/BFS)

The optimal approach leverages the fact that we can start from the oceans and flow inwards. This is more efficient because we only explore cells that can reach the ocean. We use two matrices to keep track of which cells can reach the Pacific and Atlantic oceans, respectively.

Algorithm:

Initialize two matrices, pacific and atlantic, of the same dimensions as heights, filled with False.
Perform DFS/BFS starting from the Pacific Ocean (top and left edges) to mark reachable cells in the pacific matrix.
Perform DFS/BFS starting from the Atlantic Ocean (bottom and right edges) to mark reachable cells in the atlantic matrix.
For each cell (r, c), if both pacific[r][c] and atlantic[r][c] are True, add it to the result.

Code (Python):

def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []
    
    m, n = len(heights), len(heights[0])
    pacific = [[False] * n for _ in range(m)]
    atlantic = [[False] * n for _ in range(m)]
    
    def dfs(r, c, ocean, visited):
        if (r, c) in visited:
            return
        
        visited.add((r, c))
        ocean[r][c] = True
        
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and heights[nr][nc] >= heights[r][c]:
                dfs(nr, nc, ocean, visited)
    
    # Pacific Ocean
    for r in range(m):
        dfs(r, 0, pacific, set())
    for c in range(n):
        dfs(0, c, pacific, set())
        
    # Atlantic Ocean
    for r in range(m):
        dfs(r, n - 1, atlantic, set())
    for c in range(n):
        dfs(m - 1, c, atlantic, set())

    result = []
    for r in range(m):
        for c in range(n):
            if pacific[r][c] and atlantic[r][c]:
                result.append([r, c])
                
    return result

3. Big(O) Run-time Analysis

Naive Solution:

For each cell (r, c), we perform DFS/BFS, which in the worst case, can visit all the cells in the matrix. Therefore the run time for each cell is O(m*n).
We iterate over each cell (mn cells). This makes the overall time complexity O((mn)^2) since the complexity of DFS is O(m*n) and is run for each cell.

Optimal Solution:

We perform DFS/BFS from the edges of the matrix. Each cell is visited at most once. Therefore, the run time for DFS is O(m*n).
We iterate over all cells twice (once from each edge of the matrix), hence O(mn). Then, at the end, we are looping through all cells one last time, so O(mn) + O(mn) + O(mn) which is O(m*n).

Thus the time complexity is O(m*n)

4. Big(O) Space Usage Analysis

Naive Solution:

The visited set will take, at most, O(m*n) space.
The recursion stack can take at most O(m*n) space.
Therefore, the space complexity is O(mn) + O(mn) = O(m*n).

Optimal Solution:

We use two matrices, pacific and atlantic, each of size m x n, so the space complexity is O(m*n) for each matrix.
Also, DFS will take O(m*n) space.
Thus the space complexity becomes O(mn) + O(mn) + O(mn) = O(mn).

5. Edge Cases

Empty Input: If the input matrix heights is empty or has zero dimensions, we should return an empty list.
Single Cell: If the matrix has only one cell, that cell should be included in the result since it can reach both oceans (as defined).
All Same Height: If all cells have the same height, all cells should be in the result because water can flow anywhere.
Matrix with One Row or One Column: The logic for handling these cases should be correctly implemented, as edge cells determine the flow for the rest of the row/column.