Leetcode 417. Pacific Atlantic Water Flow

Problem

You are given a rectangular elevation map represented as an m × n matrix of integers, where each cell contains the height above sea level at that position. Rain falls uniformly across the entire map.

Water can flow from any cell to its four adjacent neighbors (up, down, left, right) if the neighboring cell's height is less than or equal to the current cell's height.

The map is bordered by two river basins:

• The Northern Basin touches all cells in the top row
• The Western Basin touches all cells in the leftmost column
• The Southern Basin touches all cells in the bottom row
• The Eastern Basin touches all cells in the rightmost column

For simplicity, we group:

• Northern and Western basins together (call this "Basin A")
• Southern and Eastern basins together (call this "Basin B")

Your task is to find all cells where rainwater can flow to both Basin A and Basin B.

Return the result as a list of coordinates [row, col] in any order.

Requirements

1. Identify all cells that can reach both basin groups
2. Water flows from higher or equal elevation to lower or equal elevation
3. Return coordinates as a list of [row, col] pairs
4. The order of returned coordinates does not matter

Constraints

• 1 ≤ m, n ≤ 200
• 0 ≤ heights[i][j] ≤ 105
• Optimize for time complexity; avoid redundant traversals
• Expected time complexity: O(m × n)
• Expected space complexity: O(m × n)

Examples

Example 1:

Input: heights = [[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]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Explanation: Basin A (North/West) is at the top and left edges. Basin B (South/East) is at the bottom and right edges. The cells in the output can flow to both basins.

Example 2:

Input: heights = [[2,2],[2,2]] Output: [[0,0],[0,1],[1,0],[1,1]] Explanation: All cells have equal height, so water can flow in all directions, reaching both basins.

Example 3:

Input: heights = [[5]] Output: [[0,0]] Explanation: A single cell borders both basin groups.

Hint 1: Reverse the Flow Direction Instead of trying to determine where water can flow FROM each cell, think about which cells water can reach when starting FROM the basin edges. Work backwards (uphill) from the boundaries.

Hint 2: Two Separate Searches Perform two independent graph traversals: one starting from all Basin A edges (top and left), and another from all Basin B edges (bottom and right). In each traversal, move to cells with height greater than or equal to the current cell (flowing uphill in the reverse direction).

Hint 3: Finding the Intersection After running both traversals, the cells that appear in both reachability sets are exactly the cells from which water can reach both basins. Use sets or boolean matrices to track reachable cells efficiently.

Full Solution `` Approach Explanation:

The key insight is to reverse the problem: instead of checking where water flows TO from each cell, we determine which cells can be reached FROM each basin boundary by flowing uphill (to cells of equal or greater height).

1. Two Reachability Sets: We maintain two boolean matrices tracking which cells can reach Basin A and Basin B respectively.

2. Multi-Source DFS from Borders:

   • For Basin A: Start DFS from all cells on the top row and left column
   • For Basin B: Start DFS from all cells on the bottom row and right column
   • During DFS, we move to neighbors with height ≥ current height (uphill flow in reverse)

3. Intersection: Cells marked as reachable in both matrices are the answer.

Time Complexity: O(m × n) – Each cell is visited at most once per DFS traversal (twice total).

Space Complexity: O(m × n) – For the two reachability matrices and the recursion stack in the worst case.

def findDualBasinCells(heights):
    if not heights or not heights[0]:
        return []
    
    m, n = len(heights), len(heights[0])
    
    # Track which cells can reach each basin
    reachable_a = [[False] * n for _ in range(m)]
    reachable_b = [[False] * n for _ in range(m)]
    
    def dfs(row, col, reachable):
        # Mark current cell as reachable
        reachable[row][col] = True
        
        # Explore all four neighbors
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            
            # Check bounds
            if 0 <= new_row < m and 0 <= new_col < n:
                # Check if not visited and height allows flow (uphill in reverse)
                if not reachable[new_row][new_col] and heights[new_row][new_col] >= heights[row][col]:
                    dfs(new_row, new_col, reachable)
    
    # Start DFS from Basin A borders (top row and left column)
    for col in range(n):
        dfs(0, col, reachable_a)  # Top row
    for row in range(m):
        dfs(row, 0, reachable_a)  # Left column
    
    # Start DFS from Basin B borders (bottom row and right column)
    for col in range(n):
        dfs(m - 1, col, reachable_b)  # Bottom row
    for row in range(m):
        dfs(row, n - 1, reachable_b)  # Right column
    
    # Find cells reachable from both basins
    result = []
    for row in range(m):
        for col in range(n):
            if reachable_a[row][col] and reachable_b[row][col]:
                result.append([row, col])
    
    return result