Python DSA Demos

Algorithm Notes

Summary: Pacific Atlantic Water Flow — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.

Big-O Guide

Source

"""
Pacific Atlantic Water Flow

TODO: Add problem description
"""

from src.interview_workbook.leetcode._registry import register_problem
from src.interview_workbook.leetcode._types import Category, Difficulty


class Solution:
    def solve(self, heights):
        """Return coordinates from which water can flow to both Pacific and Atlantic."""
        if not heights:
            return []
        rows, cols = len(heights), len(heights[0])

        def dfs(r, c, visited, prevHeight):
            if (
                r < 0
                or c < 0
                or r >= rows
                or c >= cols
                or (r, c) in visited
                or heights[r][c] < prevHeight
            ):
                return
            visited.add((r, c))
            dfs(r + 1, c, visited, heights[r][c])
            dfs(r - 1, c, visited, heights[r][c])
            dfs(r, c + 1, visited, heights[r][c])
            dfs(r, c - 1, visited, heights[r][c])

        pacific, atlantic = set(), set()
        for c in range(cols):
            dfs(0, c, pacific, heights[0][c])
            dfs(rows - 1, c, atlantic, heights[rows - 1][c])
        for r in range(rows):
            dfs(r, 0, pacific, heights[r][0])
            dfs(r, cols - 1, atlantic, heights[r][cols - 1])

        return list(pacific & atlantic)


def demo():
    """Run a demo for the Pacific Atlantic Water Flow problem."""
    solver = Solution()
    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],
    ]
    result = solver.solve(heights)
    return str(sorted(result))


register_problem(
    id=417,
    slug="pacific_atlantic_water_flow",
    title="Pacific Atlantic Water Flow",
    category=Category.GRAPHS,
    difficulty=Difficulty.MEDIUM,
    tags=["array", "dfs", "bfs"],
    url="https://leetcode.com/problems/pacific-atlantic-water-flow/",
    notes="",
)