Problem link ও উৎস
- **Original source:** Classic reverse-flood-from-borders grid exercise
- **Platform:** LeetCode —
- **Topic:** graphs
- **Difficulty:** Medium
- **Pattern:** reverse flood from borders (two floods + intersection)
- **Basic idea inherited from:** flood fill ([003-flood-fill.md](003-flood-fill.md), এই tracker-এর #3); DFS on grid ([../dfs.md](../dfs.md))
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
তোমাকে একটা `m x n` grid দেওয়া আছে, প্রতিটা cell-এ একটা উচ্চতা (height)। উপরের ও বাঁদিকের প্রান্ত হলো **Pacific** মহাসাগর, নিচের ও ডানদিকের প্রান্ত হলো **Atlantic**। জল কোনো cell থেকে শুধু সমান বা **নিচু** প্রতিবেশীতে গড়াতে পারে (চার দিকে)। খুঁজে বের করো সেই সব cell, যেখান থেকে জল গড়িয়ে **দুই মহাসাগরেই** পৌঁছাতে পারে। ফলাফল সেই cell-গুলোর coordinate list।
```text
prখান্ত উপরে+বাঁয়ে = Pacific, নিচে+ডানে = Atlantic
জল উঁচু থেকে নিচু (বা সমান) cell-এ গড়ায়
উত্তর: যেসব cell দুই সাগরেই পৌঁছায়
```
### Input ও output {#8-example-input-and-output}
```text
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)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো দুটো নদীমুখ — একটা পশ্চিম তীরে, একটা পূর্ব তীরে — আর তুমি জানতে চাও পাহাড়ি অঞ্চলের কোন কোন বিন্দু থেকে বৃষ্টির জল দুই নদীমুখেই গড়িয়ে নামতে পারে। প্রতিটা বিন্দু থেকে জল ছেড়ে দেখা কষ্টকর। বরং নদীমুখে দাঁড়িয়ে **উজানে** হাঁটো — যতদূর সমান-বা-উঁচু জমি ধরে ওঠা যায়। পশ্চিম মুখ থেকে যতদূর ওঠা গেল, আর পূর্ব মুখ থেকে যতদূর — দুই পথ যেখানে মেলে, সেই বিন্দুগুলো থেকেই জল দুই দিকেই নামবে।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো **flood fill** ([003-flood-fill.md](003-flood-fill.md), #3) আর grid-এর উপর **DFS/BFS** ([../dfs.md](../dfs.md))। কিন্তু এখানে একটা সুন্দর মোচড়: প্রতিটা cell থেকে সাগরের দিকে flood করার বদলে, আমরা **সাগরের প্রান্ত থেকে উল্টোদিকে** flood করি — উঁচুর দিকে। এটাই dfs.md-তে বলা reverse flood fill। চেনা flood fill, কিন্তু direction উল্টে দিয়ে দুবার চালানো, তারপর দুই reach-এর intersection।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: "এই cell থেকে কি Pacific-এ পৌঁছানো যায়?" — এটা সরাসরি জিজ্ঞেস করলে প্রতিটা cell থেকে আলাদা search লাগে, খরচ বেশি। উল্টো করে ভাবো: **Pacific যেসব cell-এ পৌঁছাতে পারে** (জলের প্রবাহ উল্টে) ঠিক সেই cell-গুলো থেকেই জল Pacific-এ যেতে পারত। তাই সাগর-প্রান্ত থেকে শুরু করে শুধু সমান-বা-**উঁচু** প্রতিবেশীতে যাও (downhill-এর উল্টো)। দুই সাগর থেকে এমন দুটো reachable set বানাও; যে cell **দুটোতেই** আছে, সেখান থেকেই জল দুই সাগরে গড়ায়। One-to-many search-কে many-to-one-এ উল্টে দেওয়াই আসল চাল।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
- **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)]` — চার প্রতিবেশী।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
দুটো আলাদা visited set fit করে কারণ আমরা দুটো স্বাধীন প্রশ্নের উত্তর চাই ("Pacific থেকে কোথায় পৌঁছানো যায়", "Atlantic থেকে কোথায়"), আর শেষে তাদের **intersection** নিলেই উত্তর — set দুটোর জন্যই দ্রুত membership ও intersection দেয়। DFS/BFS fit করে কারণ এটা reachability — distance নয়, শুধু "পৌঁছানো যায় কিনা", তাই যেকোনো traversal চলে। grid নিজেই adjacency বহন করে (cell-এর চার প্রতিবেশী), তাই আলাদা graph বানানোর দরকার নেই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা cell থেকে আলাদা করে DFS/BFS চালিয়ে দেখা সেখান থেকে জল Pacific আর Atlantic দুটোতেই গড়ায় কিনা (downhill যেতে দিয়ে)।
```text
1) প্রতিটা cell (r, c)-এর জন্য:
2) DFS: শুধু সমান-বা-নিচু প্রতিবেশীতে যাও
3) পথে Pacific প্রান্ত ছুঁলো? Atlantic প্রান্ত ছুঁলো?
4) দুটোই হলে (r, c)-কে উত্তরে রাখো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা 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-এ নামায়।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **"cell থেকে সাগরে জল যায়" = "সাগর থেকে উল্টো-flood-এ cell-এ পৌঁছানো যায়"** (direction reverse করে, downhill-এর বদলে uphill)। তাই প্রতিটা cell থেকে না খুঁজে, সাগর-প্রান্ত থেকে দুটো flood চালাও আর intersection নাও — একই উত্তর, কিন্তু বিশাল কম কাজ।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
দুটো 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)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতিটা cell থেকে সাগরে পৌঁছাই কিনা খুঁজব" না ভেবে ভাবো "সাগর থেকে উল্টোদিকে উঠে দেখি কোথায় পৌঁছাই — তাহলে এক flood-এই সব cell-এর উত্তর পাই।" Flow-এর direction উল্টে দিয়ে many searches-কে দুটো search-এ মিলিয়ে দাও, তারপর intersection।
### ছবিতে বোঝা {#7-visual-explanation}
ছোট grid (`P` = Pacific-reachable, `A` = Atlantic-reachable):
```text
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-এ ধাপে ধাপে {#14-step-by-step-dry-run}
`heights = [[1,2],[3,2]]` (2x2):
1. Pacific প্রান্ত = top row `(0,0),(0,1)` + left col `(0,0),(1,0)`। এদের থেকে উল্টো-flood (সমান-বা-উঁচু):
- `(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)}`।
2. Atlantic প্রান্ত = bottom row `(1,0),(1,1)` + right col `(0,1),(1,1)`। উল্টো-flood:
- `(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)}`।
3. intersection = `{(0,1),(1,0),(1,1)}` → এই তিন cell থেকে জল দুই সাগরে গড়ায়।
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```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!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `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 মিলিয়ে দেখা {#17-output-walkthrough}
`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!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(m·n)** — দুটো flood, প্রতিটাতে প্রতিটা cell সর্বোচ্চ একবার visit ও প্রতিটা edge constant-বার দেখা হয়; দুই সাগর মিলিয়েও linear।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(m·n)** — দুটো visited set প্রতিটা O(m·n), আর BFS queue worst case O(m·n)। intersection result-ও সর্বোচ্চ O(m·n)।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- প্রতিটা cell থেকে আলাদা search চালানো (brute force) — O((m·n)^2), reverse-flood না বোঝার ফল।
- flood-এ direction উল্টাতে ভুলে যাওয়া — `>=` (uphill)-এর বদলে `<=` (downhill) লিখলে সম্পূর্ণ ভুল উত্তর।
- দুটো set আলাদা না রেখে একটাতে মিশিয়ে ফেলা — তখন আর intersection বের করা যায় না।
- প্রান্ত-cell গুলোকে seed করার সময় `reach`-এ যোগ করতে ভুলে যাওয়া — শুরুর cell বাদ পড়ে।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: flood fill ([003-flood-fill.md](003-flood-fill.md), #3) আর grid traversal ([../dfs.md](../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।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Enclaves (border থেকে flood, তারপর বাকি গোনা) —