LeetCode #417 Pacific Atlantic: เดินน้ำย้อนจากสองมหาสมุทร

Pacific Atlantic Water Flow ให้ตารางความสูง น้ำไหลจากช่องหนึ่งไปเพื่อนบ้านที่สูงไม่กว่าเดิม ขอบบน/ซ้ายติด Pacific และขอบล่าง/ขวาติด Atlantic ต้องคืนทุกช่องที่น้ำไหลถึงทั้งสองฝั่งครับ

ถ้าเริ่มปล่อยน้ำจากทุกช่อง เราทำงานเดิมซ้ำมาก เคล็ดลับคือกลับทิศ: เริ่มจากทะเลแล้วเดิน “ขึ้นเขา” ไปยังช่องที่สูงเท่ากันหรือสูงกว่า ช่องที่ทั้งสองทะเลเดินย้อนมาถึงคือคำตอบ

วิธีที่ 1: DFS/BFS จากทุก cell

สำหรับแต่ละช่อง เดินตามทิศน้ำจนรู้ว่าถึงขอบใด เวลา worst case O((mn)²) และมี visited ต่อจุด เหมาะแค่ทำ oracle บนตารางเล็กเพื่อทดสอบวิธีเร็ว

วิธีที่ 2: Reverse multi-source BFS สองรอบ — ค่าเริ่มต้นที่แนะนำ

ใส่ขอบ Pacific ทั้งหมดเป็น source ชุดแรก และขอบ Atlantic เป็น source ชุดที่สอง เดินไปเพื่อนบ้านที่สูงไม่น้อยกว่าช่องปัจจุบัน แต่ละรอบแตะ cell/edge คงที่ จึงเวลา O(mn), พื้นที่ O(mn) แล้ว intersect visited สองชุด ไม่แก้ input และไม่เสี่ยง recursion depth

วิธีที่ 3: DFS สองรอบ

แนวคิดเดียวกับ BFS แต่ใช้ recursion โค้ดสั้นและเหมาะภาษา/constraints ที่ stack เพียงพอ ใน Python ตารางยาวแคบอาจชน recursion limit จึงควรเลือก iterative BFS เป็น default

วิธีที่ 4: Frontier เดียวพร้อม bitmask

เก็บบิตว่า cell ถูกถึงจากทะเลใด แล้วขยาย state ใน queue เดียว ลดจำนวนโครงสร้างบางส่วน แต่ logic การ dedupe ซับซ้อนขึ้นและไม่ได้เปลี่ยน O(mn) เหมาะเมื่อ memory layout สำคัญและมี benchmark รองรับ

เงื่อนไข	เลือก	เหตุผล
ตารางทั่วไป	Reverse BFS สองรอบ	ชัดและ O(mn)
ตารางเล็กมาก/ทำ oracle	เดินจากทุก cell	ตรงนิยาม ตรวจวิธีเร็วได้
ภาษา stack ใหญ่	Reverse DFS	โค้ดกระชับ
memory เข้มงวด	bitmask ต่อ cell	รวมสถานะสองชุด
input มาเป็น stream	ต้องเก็บอย่างน้อย frontier/แถว	การเชื่อมสี่ทิศย้อนกลับต้องเห็นเพื่อนบ้าน
แถว/คอลัมน์เรียง	อาจ prune ได้เฉพาะกรณี	constraints ไม่รับประกัน
อนุญาตแก้ input	ทำ marker ใน grid ได้	แต่ทำให้ API มี side effect ไม่จำเป็น

from collections import deque
import unittest


def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []
    rows, cols = len(heights), len(heights[0])

    def reachable(starts):
        seen = set(starts)
        queue = deque(seen)
        while queue:
            row, col = queue.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if not (0 <= nr < rows and 0 <= nc < cols):
                    continue
                if (nr, nc) in seen or heights[nr][nc] < heights[row][col]:
                    continue
                seen.add((nr, nc))
                queue.append((nr, nc))
        return seen

    pacific = [(0, col) for col in range(cols)] + [(row, 0) for row in range(rows)]
    atlantic = [(rows - 1, col) for col in range(cols)] + [(row, cols - 1) for row in range(rows)]
    both = reachable(pacific) & reachable(atlantic)
    return [list(cell) for cell in sorted(both)]


class WaterFlowTests(unittest.TestCase):
    def test_classic_grid(self):
        grid = [
            [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],
        ]
        expected = [[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]]
        self.assertEqual(pacific_atlantic(grid), expected)

    def test_single_cell_reaches_both(self):
        self.assertEqual(pacific_atlantic([[7]]), [[0, 0]])

    def test_empty(self):
        self.assertEqual(pacific_atlantic([]), [])


if __name__ == "__main__":
    unittest.main()

Edge cases และ trade-off

ขอบมุมถูกใส่ซ้ำได้แต่ set จัดการให้ ตารางค่าเท่ากันทั้งหมดจะ reachable ทั้งหมด เงื่อนไขย้อนทิศต้องเป็น neighbor >= current; เขียนกลับด้านเพียงตัวเดียวผลจะผิดเงียบ ๆ การ sort ผลในตัวอย่างมีเพื่อให้ test deterministic ไม่จำเป็นต่อ LeetCode

Recap

• กลับโจทย์จาก “น้ำไปทะเล” เป็น “ทะเลเดินขึ้นเขา”
• ใช้ multi-source จากขอบทั้งสองชุด
• intersect visited เพื่อหาคำตอบ
• ทดสอบ 1×1, ค่าเท่ากัน และตารางว่างในโค้ด reusable
• ค่าเริ่มต้นภายใต้ constraints ของโจทย์: reverse BFS สองรอบ