LeetCode 417: Pacific Atlantic Water Flow

[github-actions]

LeetCode 417: Pacific Atlantic Water Flow

Category: Graph
Difficulty: See LeetCode
Solution File: src/graph/pacific_atlantic_water_flow.py
Test File: tests/test_pacific_atlantic_water_flow.py

Problem Description

There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean.
The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the
island's right and bottom edges.

The island is partitioned into a grid of square cells. You are given an m x n integer matrix
heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c).

Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

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]]

Example 2:
Input: heights = [[1]]
Output: [[0,0]]

Constraints:

• m == heights.length
• n == heights[r].length
• 1 <= m, n <= 200

Tasks

• Implement the solution in src/graph/pacific_atlantic_water_flow.py
• Ensure all test cases pass
• Analyze time complexity
• Analyze space complexity