Practice/Meta/Leetcode 417. Pacific Atlantic Water Flow

Leetcode 417. Pacific Atlantic Water Flow

CodingMust

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.