014 — Pacific Atlantic Water Flow

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

• Original source: Classic reverse-flood-from-borders grid exercise
• Platform: LeetCode — https://leetcode.com/problems/pacific-atlantic-water-flow/
• Topic: graphs
• Difficulty: Medium
• Pattern: reverse flood from borders (two floods + intersection)
• Basic idea inherited from: flood fill (003-flood-fill.md, এই tracker-এর #3); DFS on grid (../dfs.md)

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে একটা m x n grid দেওয়া আছে, প্রতিটা cell-এ একটা উচ্চতা (height)। উপরের ও বাঁদিকের প্রান্ত হলো Pacific মহাসাগর, নিচের ও ডানদিকের প্রান্ত হলো Atlantic। জল কোনো cell থেকে শুধু সমান বা নিচু প্রতিবেশীতে গড়াতে পারে (চার দিকে)। খুঁজে বের করো সেই সব cell, যেখান থেকে জল গড়িয়ে দুই মহাসাগরেই পৌঁছাতে পারে। ফলাফল সেই cell-গুলোর coordinate list।

উদাহরণ

prখান্ত উপরে+বাঁয়ে = Pacific, নিচে+ডানে = Atlantic
জল উঁচু থেকে নিচু (বা সমান) cell-এ গড়ায়
উত্তর: যেসব cell দুই সাগরেই পৌঁছায়

Input ও output

উদাহরণ

Input : heights = [[1,2,2,3],[3,2,3,4],[2,4,5,3]]
Output: কিছু cell (যেমন (0,3),(1,3),(1,0),(2,0),(2,1),(2,2)) যেখান থেকে জল দুই সাগরে পৌঁছায়

Input : heights = [[1]]
Output: [(0,0)]        (একটাই cell, সব প্রান্তেই -> দুই সাগরেই পৌঁছায়)

Edge case (এক সারি): heights = [[1,2,3]] -> তিনটা cell-ই দুই সাগরে পৌঁছায় (top=bottom)

চেনা উদাহরণে বোঝা

ভাবো দুটো নদীমুখ — একটা পশ্চিম তীরে, একটা পূর্ব তীরে — আর তুমি জানতে চাও পাহাড়ি অঞ্চলের কোন কোন বিন্দু থেকে বৃষ্টির জল দুই নদীমুখেই গড়িয়ে নামতে পারে। প্রতিটা বিন্দু থেকে জল ছেড়ে দেখা কষ্টকর। বরং নদীমুখে দাঁড়িয়ে উজানে হাঁটো — যতদূর সমান-বা-উঁচু জমি ধরে ওঠা যায়। পশ্চিম মুখ থেকে যতদূর ওঠা গেল, আর পূর্ব মুখ থেকে যতদূর — দুই পথ যেখানে মেলে, সেই বিন্দুগুলো থেকেই জল দুই দিকেই নামবে।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

মূল ভিত হলো flood fill (003-flood-fill.md, #3) আর grid-এর উপর DFS/BFS (../dfs.md)। কিন্তু এখানে একটা সুন্দর মোচড়: প্রতিটা cell থেকে সাগরের দিকে flood করার বদলে, আমরা সাগরের প্রান্ত থেকে উল্টোদিকে flood করি — উঁচুর দিকে। এটাই dfs.md-তে বলা reverse flood fill। চেনা flood fill, কিন্তু direction উল্টে দিয়ে দুবার চালানো, তারপর দুই reach-এর intersection।

ভেতরের যুক্তি

লুকানো logic: "এই cell থেকে কি Pacific-এ পৌঁছানো যায়?" — এটা সরাসরি জিজ্ঞেস করলে প্রতিটা cell থেকে আলাদা search লাগে, খরচ বেশি। উল্টো করে ভাবো: Pacific যেসব cell-এ পৌঁছাতে পারে (জলের প্রবাহ উল্টে) ঠিক সেই cell-গুলো থেকেই জল Pacific-এ যেতে পারত। তাই সাগর-প্রান্ত থেকে শুরু করে শুধু সমান-বা-উঁচু প্রতিবেশীতে যাও (downhill-এর উল্টো)। দুই সাগর থেকে এমন দুটো reachable set বানাও; যে cell দুটোতেই আছে, সেখান থেকেই জল দুই সাগরে গড়ায়। One-to-many search-কে many-to-one-এ উল্টে দেওয়াই আসল চাল।

কী দিয়ে তথ্য রাখব

• grid (2D list) — heights, input-ই।
• দুটো visited set — pacific ও atlantic, প্রতিটা সাগর থেকে reachable cell।
• DFS recursion বা BFS collections.deque — প্রান্ত থেকে flood করতে।
• direction list [(-1,0),(1,0),(0,-1),(0,1)] — চার প্রতিবেশী।

এটি কেন উপযুক্ত

দুটো আলাদা visited set fit করে কারণ আমরা দুটো স্বাধীন প্রশ্নের উত্তর চাই ("Pacific থেকে কোথায় পৌঁছানো যায়", "Atlantic থেকে কোথায়"), আর শেষে তাদের intersection নিলেই উত্তর — set দুটোর জন্যই দ্রুত membership ও intersection দেয়। DFS/BFS fit করে কারণ এটা reachability — distance নয়, শুধু "পৌঁছানো যায় কিনা", তাই যেকোনো traversal চলে। grid নিজেই adjacency বহন করে (cell-এর চার প্রতিবেশী), তাই আলাদা graph বানানোর দরকার নেই।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

প্রথম সরল চিন্তা: প্রতিটা cell থেকে আলাদা করে DFS/BFS চালিয়ে দেখা সেখান থেকে জল Pacific আর Atlantic দুটোতেই গড়ায় কিনা (downhill যেতে দিয়ে)।

উদাহরণ

1) প্রতিটা cell (r, c)-এর জন্য:
2)   DFS: শুধু সমান-বা-নিচু প্রতিবেশীতে যাও
3)   পথে Pacific প্রান্ত ছুঁলো? Atlantic প্রান্ত ছুঁলো?
4)   দুটোই হলে (r, c)-কে উত্তরে রাখো

কোথায় বেশি কাজ হচ্ছে

প্রতিটা cell থেকে আলাদা search চালানো হলো O((m·n)^2) — প্রতিটা DFS পুরো grid ঘুরতে পারে, আর তা m·n বার। অনেক কাজ বারবার হয়: একই downhill path বহু cell-এর জন্য পুনরায় হাঁটা হয়। উল্টো-flood approach পুরো বদলে দেয়: প্রতিটা সাগর থেকে একটাই flood, প্রতিটা cell সর্বোচ্চ দুবার (এক সাগর প্রতি একবার) visit হয় — মোট O(m·n)। One-to-many-কে many-to-one-এ উল্টে দেওয়াই quadratic থেকে linear-এ নামায়।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: "cell থেকে সাগরে জল যায়" = "সাগর থেকে উল্টো-flood-এ cell-এ পৌঁছানো যায়" (direction reverse করে, downhill-এর বদলে uphill)। তাই প্রতিটা cell থেকে না খুঁজে, সাগর-প্রান্ত থেকে দুটো flood চালাও আর intersection নাও — একই উত্তর, কিন্তু বিশাল কম কাজ।

আরও কম কাজে সমাধান

দুটো set বানাও: pacific, atlantic। Pacific প্রান্তের সব cell (top row + left col) থেকে DFS শুরু করে শুধু সমান-বা-উঁচু প্রতিবেশীতে যাও, যা reach করো সব pacific-এ যোগ করো। একইভাবে Atlantic প্রান্ত (bottom row + right col) থেকে atlantic ভরো। শেষে pacific ∩ atlantic — যে cell দুটোতেই, সেই উত্তর। প্রতিটা cell প্রতি সাগরে একবার → O(m·n)।

ভাবনার পরিবর্তন

মোচড়: "প্রতিটা cell থেকে সাগরে পৌঁছাই কিনা খুঁজব" না ভেবে ভাবো "সাগর থেকে উল্টোদিকে উঠে দেখি কোথায় পৌঁছাই — তাহলে এক flood-এই সব cell-এর উত্তর পাই।" Flow-এর direction উল্টে দিয়ে many searches-কে দুটো search-এ মিলিয়ে দাও, তারপর intersection।

ছবিতে বোঝা

ছোট grid (P = Pacific-reachable, A = Atlantic-reachable):

উদাহরণ

heights:          Pacific প্রান্ত = top + left
  1 2 2 3         Atlantic প্রান্ত = bottom + right
  3 2 3 4
  2 4 5 3

Pacific থেকে উল্টো-flood (উঁচুর দিকে, top+left থেকে):
  reach করে অনেক cell উপরে-বাঁয়ে

Atlantic থেকে উল্টো-flood (bottom+right থেকে):
  reach করে অনেক cell নিচে-ডানে

intersection = দুই set-এ common cell:
  মাঝের ridge-এর cell-গুলো (যেমন (1,3),(2,2)) -> এদের থেকে জল দুই সাগরেই গড়ায়

ছোট input-এ ধাপে ধাপে

heights = [[1,2],[3,2]] (2x2):

1. Pacific প্রান্ত = top row (0,0),(0,1) + left col (0,0),(1,0)। এদের থেকে উল্টো-flood (সমান-বা-উঁচু):
2. (0,0)h1 → প্রতিবেশী (0,1)h2 (≥1, যাও), (1,0)h3 (≥1, যাও)। (0,1)h2 → (1,1)h2 (≥2, যাও)। pacific = {(0,0),(0,1),(1,0),(1,1)}।
3. Atlantic প্রান্ত = bottom row (1,0),(1,1) + right col (0,1),(1,1)। উল্টো-flood:
4. (1,1)h2 → (0,1)h2 (≥2, যাও), (1,0)h3 (≥2, যাও)। (1,0)h3 → (0,0)h1 (1<3, না)। (0,1)h2 → (0,0)h1 (না)। atlantic = {(1,0),(1,1),(0,1)}।
5. intersection = {(0,1),(1,0),(1,1)} → এই তিন cell থেকে জল দুই সাগরে গড়ায়।

কোড ও ব্যাখ্যা

Python

Python

from collections import deque


def pacific_atlantic(heights):
    if not heights or not heights[0]:
        return []
    m, n = len(heights), len(heights[0])
    pacific, atlantic = set(), set()
    dirs = ((-1, 0), (1, 0), (0, -1), (0, 1))

    def flood(start_cells, reach):
        # সাগর-প্রান্ত থেকে উল্টো-flood: শুধু সমান-বা-উঁচু প্রতিবেশীতে যাও
        dq = deque(start_cells)
        for cell in start_cells:
            reach.add(cell)
        while dq:
            r, c = dq.popleft()
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if (0 <= nr < m and 0 <= nc < n
                        and (nr, nc) not in reach
                        and heights[nr][nc] >= heights[r][c]):  # uphill (reverse flow)
                    reach.add((nr, nc))
                    dq.append((nr, nc))

    pacific_edge = [(0, c) for c in range(n)] + [(r, 0) for r in range(m)]
    atlantic_edge = [(m - 1, c) for c in range(n)] + [(r, n - 1) for r in range(m)]
    flood(pacific_edge, pacific)
    flood(atlantic_edge, atlantic)

    return sorted(pacific & atlantic)        # দুই সাগরেই পৌঁছায় এমন cell


# ---- tests ----
h1 = [[1, 2, 2, 3], [3, 2, 3, 4], [2, 4, 5, 3]]
res1 = pacific_atlantic(h1)
# প্রতিটা প্রান্ত-cell অন্তত এক সাগরে; কিছু cell দুটোতেই থাকবে
assert (2, 0) in res1 and (0, 3) in res1        # নিচ-বাঁ ও উপর-ডান কোণ
assert all(0 <= r < 3 and 0 <= c < 4 for r, c in res1)

assert pacific_atlantic([[1]]) == [(0, 0)]      # একটাই cell, দুই সাগরে
assert pacific_atlantic([[1, 2, 3]]) == [(0, 0), (0, 1), (0, 2)]  # এক সারি
assert pacific_atlantic([]) == []               # খালি grid

# সমান উচ্চতার grid: প্রতিটা cell দুই সাগরে পৌঁছায়
flat = [[5, 5], [5, 5]]
assert pacific_atlantic(flat) == [(0, 0), (0, 1), (1, 0), (1, 1)]
print("সব test pass!")

কোডের প্রতিটি অংশ

• pacific, atlantic = set(), set() — দুই সাগর থেকে reachable cell আলাদা রাখি; set দ্রুত membership ও intersection দেয়।
• flood(start_cells, reach) — এক সাগরের সব প্রান্ত-cell থেকে শুরু করে উল্টো-flood; multi-source seeding।
• heights[nr][nc] >= heights[r][c] — uphill শর্ত; downhill flow-এর উল্টো, এটাই reverse-flood-এর কেন্দ্র।
• pacific_edge / atlantic_edge — top+left vs bottom+right প্রান্তের cell list।
• pacific & atlantic — set intersection, যে cell দুই সাগরেই পৌঁছায়।
• sorted(...) — deterministic output, tests-এ তুলনার জন্য।

Output মিলিয়ে দেখা

pacific_atlantic(h1): Pacific প্রান্ত (top+left) থেকে উল্টো-flood এক set, Atlantic প্রান্ত (bottom+right) থেকে আরেক set; দুটোর intersection-এ থাকে নিচ-বাঁ কোণ (2,0), উপর-ডান কোণ (0,3) সহ ridge-cell গুলো। single cell [[1]] সব প্রান্তেই → [(0,0)]। এক সারি [[1,2,3]]-এ top=bottom, প্রতিটা cell দুই সাগরে → তিন cell। খালি grid → []। flat grid-এ সব cell দুই সাগরে। সব assert pass, শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

O(m·n) — দুটো flood, প্রতিটাতে প্রতিটা cell সর্বোচ্চ একবার visit ও প্রতিটা edge constant-বার দেখা হয়; দুই সাগর মিলিয়েও linear।

অতিরিক্ত জায়গা

O(m·n) — দুটো visited set প্রতিটা O(m·n), আর BFS queue worst case O(m·n)। intersection result-ও সর্বোচ্চ O(m·n)।

যে ভুলগুলো এড়াতে হবে

• প্রতিটা cell থেকে আলাদা search চালানো (brute force) — O((m·n)^2), reverse-flood না বোঝার ফল।
• flood-এ direction উল্টাতে ভুলে যাওয়া — >= (uphill)-এর বদলে <= (downhill) লিখলে সম্পূর্ণ ভুল উত্তর।
• দুটো set আলাদা না রেখে একটাতে মিশিয়ে ফেলা — তখন আর intersection বের করা যায় না।
• প্রান্ত-cell গুলোকে seed করার সময় reach-এ যোগ করতে ভুলে যাওয়া — শুরুর cell বাদ পড়ে।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: flood fill (003-flood-fill.md, #3) আর grid traversal (../dfs.md)। এটা flood fill-এর একটা গভীর মোচড়: প্রবাহের direction উল্টে দিয়ে "কে কোথায় পৌঁছায়"-কে "কোথা থেকে কে পৌঁছায়"-তে বদলানো, আর দুটো flood-এর intersection নেওয়া। মূল নতুন শিক্ষা — "প্রতিটা source থেকে খোঁজা" (one-to-many) প্রায়ই "target থেকে উল্টো খোঁজা" (many-to-one)-তে উল্টে দিয়ে quadratic থেকে linear-এ নামানো যায়। এই reverse-thinking পরে অনেক grid ও graph problem-এ কাজে লাগে। পরের ধাপ: directed graph-এ cycle আছে কিনা — #15।

পরের অনুশীলন

• Number of Enclaves (border থেকে flood, তারপর বাকি গোনা) — https://leetcode.com/problems/number-of-enclaves/
• Surrounded Regions (border-connected অংশ আলাদা করা) — https://leetcode.com/problems/surrounded-regions/
• Walls and Gates (multi-source BFS, border-ধাঁচ) — https://leetcode.com/problems/walls-and-gates/

কৌশলটি মনে রাখুন

Reverse flood from borders: "প্রতিটা cell থেকে কোনো লক্ষ্যে পৌঁছানো যায় কিনা" প্রশ্নকে উল্টে দাও — লক্ষ্য (প্রান্ত/সাগর) থেকে flow-এর direction উল্টে flood করো, যা reach করো সেটাই উত্তর। একাধিক লক্ষ্য থাকলে প্রতিটার জন্য আলাদা flood করে set-গুলোর intersection নাও। one-to-many search → কয়েকটা many-to-one flood, O(cells)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: "Pacific Atlantic = দুটো reverse flood (সাগর থেকে উঁচুর দিকে) + intersection; প্রতিটা cell থেকে খোঁজার বদলে প্রান্ত থেকে উল্টো-flood।" যখনই 'প্রতিটা cell/node থেকে কোনো boundary বা target-এ পৌঁছাই কিনা' দেখবে — flow উল্টে boundary থেকে flood করার কথা ভাবো, আর একাধিক boundary হলে intersection নাও।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।