Problem link ও উৎস
- **Original source:** Grid component-size optimization exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Hard
- **Pattern:** component sizes + best merge (একটা 0-কে 1 করে সবচেয়ে বড় island)
- **Basic idea inherited from:** `10`-এর size tracking — DSU-র `size` array-ই এখানে আসল নায়ক
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
`n × n` একটা grid, ঘরে 0 (জল) বা 1 (স্থল)। তোমাকে **সর্বোচ্চ একটা** 0-কে 1-এ বদলানোর সুযোগ দেওয়া হয়েছে (বদলাতে নাও পারো)। এর পরে সম্ভাব্য সবচেয়ে বড় island (পাশাপাশি 1-গুলোর connected group)-এর আকার কত হতে পারে — সেটা বের করো।
```text
grid = [[1, 0],
[0, 1]]
যেকোনো 0-কে 1 করলে দুটো আলাদা 1-island জোড়া যায় -> size 3
উত্তর = 3
```
### Input ও output {#8-example-input-and-output}
```text
Input : grid=[[1,0],[0,1]] Output: 3
Input : grid=[[1,1],[1,0]] Output: 4 (একটা 0 flip -> পুরোটা এক)
Edge : grid=[[1,1],[1,1]] -> কোনো 0 নেই -> n*n = 4
Edge : grid=[[0,0],[0,0]] -> একটাই flip -> 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো কতগুলো আলাদা দ্বীপের মাঝে অগভীর জল। তোমার হাতে একটাই বড় পাথর — সেটা যেকোনো এক জলের ঘরে ফেলে জমি বানাতে পারো। তুমি খুঁজছ এমন একটা ঘর, যেখানে পাথর ফেললে আশেপাশের যত আলাদা দ্বীপ আছে সব সেতুবন্ধ হয়ে এক বিশাল দ্বীপ হয়। একই দ্বীপ যদি দুপাশে থাকে, তার মাপ দুবার গুনলে ভুল — তাই প্রতিটা আলাদা দ্বীপ একবারই গোনো।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত্তি `10`-এর **size tracking** — union by size রাখার সময় প্রতিটা root-এ তার component-এর আকার থাকে। #10-এ island গোনা শিখেছ; এখানে শুধু গোনা নয়, প্রতিটা island-এর **আকার** চাই, কারণ একটা 0 flip করলে চারপাশের island গুলোর আকার যোগ হয়।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic: একটা 0-cell flip করলে নতুন island-এর আকার = `1 + (তার চারপাশের distinct island-গুলোর আকারের যোগফল)`। "distinct" শব্দটা গুরুত্বপূর্ণ — একই island যদি দুই প্রতিবেশী হয়ে আসে, তার আকার একবারই গোনা যাবে। DSU-র root দিয়ে distinct-ness ধরা যায়: একই root মানে একই island। তাই প্রতি 0-এর জন্য প্রতিবেশী root-গুলোকে একটা set-এ রেখে আকার যোগ করি।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** (`n·n` element) যাতে প্রতিটা land-component-এর `size` থাকে, আর প্রতি 0-cell-এ distinct প্রতিবেশী root ধরতে একটা ছোট `set`। কোনো আলাদা graph লাগে না।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
এখানে দুটো কাজ — (1) সব 1-island-কে component-এ ভাগ করা ও তাদের আকার রাখা, (2) একটা 0-এর চারপাশের distinct island-আকার দ্রুত যোগ করা। DSU-র `union` ধাপ 1, আর `find` + `size[root]` ধাপ 2 — দুটোই O(α)। Traversal দিয়েও হয় (প্রতি island-কে id দিয়ে আকার map করে), কিন্তু DSU-তে size একদম built-in, তাই code সরল।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: প্রতিটা 0-cell-কে একে একে 1 ধরো, প্রতিবার পুরো grid-এ DFS চালিয়ে সবচেয়ে বড় island গোনো, সেরা মান রাখো।
```text
1) প্রতিটা 0-cell-এর জন্য:
2) cell-কে temporarily 1 করো
3) পুরো grid-এ DFS করে largest island গোনো
4) cell-কে আবার 0 করো; best update করো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা 0-cell-এর জন্য পুরো grid DFS — `O((n²) · (n²))` = `O(n⁴)`। বড় grid-এ অসহনীয়, কারণ একই island-আকার বারবার গোনা হচ্ছে। DSU দিয়ে আকার গুলো **একবার** হিসেব করে রাখি; তারপর প্রতি 0-এ শুধু 4 প্রতিবেশীর root-size যোগ — পুরোটা `O(n²)`।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **island-আকার গুলো 0-flip-এর আগেই স্থির — প্রতিটা flip শুধু distinct প্রতিবেশী island গুলোকে সেতুবন্ধ করে।** তাই আকার একবার precompute করো; প্রতিটা 0-এর উত্তর = 1 + চারপাশের distinct root-এর size-এর যোগ। distinct ধরতে set লাগবে, নইলে একই island দুবার গোনা হবে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
ধাপ 1: grid scan করে সব পাশাপাশি 1-cell union করো — root-এ size তৈরি। ধাপ 2: প্রতিটা 0-cell-এ 4 প্রতিবেশীর land-root গুলো set-এ রাখো, তাদের size যোগ + 1 → candidate; best রাখো। কোনো 0 না থাকলে উত্তর `n·n` (পুরো grid এক island, flip-এর দরকার নেই)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "এই 0 flip করলে DFS করে দেখি কত বড় হলো" — এই বারবার-DFS ছাড়ো। বদলে আগে থেকেই প্রতিটা island-এর size জেনে রাখো; flip-এর প্রশ্ন তখন নেমে আসে "চারপাশে কোন কোন *আলাদা* island আছে, তাদের size যোগ করো"-তে। precompute + distinct-root যোগই চাবি।
### ছবিতে বোঝা {#7-visual-explanation}
ধাপ 1: সব 1 union করে island-এ ভাগ করো (root-এ size)। ধাপ 2: প্রতিটা 0-কে flip করে distinct প্রতিবেশী-size যোগ করো।
```text
grid: island label (root দিয়ে):
1 1 0 A A .
1 0 1 -> A . B island A size=3, island B size=1
0 0 1 . . B
0-cell flip করে দেখা:
(0,2) flip: প্রতিবেশী -> উপরে নেই, নিচে B, বাঁয়ে A
distinct {A,B} -> 1 + 3 + 1 = 5
(1,1) flip: প্রতিবেশী -> উপরে A, নিচে কিছু না(0), বাঁয়ে A, ডানে B
distinct {A,B} -> 1 + 3 + 1 = 5 <- best
সব 1 হলে (কোনো 0 নেই): উত্তর = n*n
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `grid=[[1,0],[0,1]]`, `n=2`, index `r*2+c`:
1. ধাপ 1: (0,0)=1; ডান (0,1)=0, নিচ (1,0)=0 → কোনো union নেই → island {0} size 1
2. (1,1)=1; প্রতিবেশী সব 0 → island {3} size 1
3. ধাপ 2, (0,1)=0: প্রতিবেশী বাঁ (0,0) root=0 size 1, নিচ (1,1) root=3 size 1 → distinct {0,3} → 1+1+1 = 3
4. (1,0)=0: প্রতিবেশী উপর (0,0) root=0, ডান (1,1) root=3 → distinct {0,3} → 1+1+1 = 3
5. best = **3**
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
class DSU:
def __init__(self, n):
self.parent = list(range(n)) # প্রথমে সবাই নিজের নিজের root
self.size = [1] * n # প্রতিটা group-এ একজন
def find(self, x): # representative + path compression
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, x, y): # union by size; merge হলে True
rx, ry = self.find(x), self.find(y)
if rx == ry:
return False # আগে থেকেই এক group
if self.size[rx] < self.size[ry]:
rx, ry = ry, rx # rx এখন বড় root
self.parent[ry] = rx # ছোটটা বড়টার নিচে ঝোলে
self.size[rx] += self.size[ry]
return True
def largest_island(grid):
n = len(grid)
dsu = DSU(n * n)
# ধাপ 1: সব পাশাপাশি 1-cell union করো
for r in range(n):
for c in range(n):
if grid[r][c] == 1:
if r + 1 < n and grid[r + 1][c] == 1:
dsu.union(r * n + c, (r + 1) * n + c)
if c + 1 < n and grid[r][c + 1] == 1:
dsu.union(r * n + c, r * n + c + 1)
best = 0
has_zero = False
# ধাপ 2: প্রতিটা 0-কে flip করে চারপাশের distinct island size যোগ
for r in range(n):
for c in range(n):
if grid[r][c] == 0:
has_zero = True
seen = set()
total = 1 # নিজের flip-করা cell
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 1:
root = dsu.find(nr * n + nc)
if root not in seen:
seen.add(root)
total += dsu.size[root]
best = max(best, total)
if not has_zero: # পুরো grid 1 — flip-এর দরকার নেই
return n * n
return best
# ---- tests ----
assert largest_island([[1, 0], [0, 1]]) == 3
assert largest_island([[1, 1], [1, 0]]) == 4
assert largest_island([[1, 1], [1, 1]]) == 4 # সব 1, কোনো 0 নেই
assert largest_island([[0, 0], [0, 0]]) == 1 # একটাই flip
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- ধাপ 1 loop — শুধু ডান ও নিচ প্রতিবেশী দেখলেই যথেষ্ট; প্রতিটা edge একবার করে cover হয়, double-union এড়ানো যায়।
- `dsu.size[root]` — union by size রাখায় root-এ component-এর আকার সরাসরি পাওয়া যায়।
- `seen = set()` — একই island দুপাশে থাকলে তার size একবারই যোগ হয়; distinct-ness-এর গার্ড।
- `total = 1` — flip-করা cell নিজে গোনা হয়।
- `has_zero` — যদি grid-এ একটাও 0 না থাকে, ধাপ 2-এ best 0 থেকে যেত; তখন সঠিক উত্তর পুরো grid `n·n`।
- `best = max(best, total)` — সব 0-cell-এর মধ্যে সেরা flip বেছে নেওয়া।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
test 1-এ দুটো বিচ্ছিন্ন 1-cell, মাঝের 0 flip করলে 3। test 2-এ একটাই 0; flip করলে চারপাশের 3 cell-এর island (size 3)-এর সাথে যোগ হয়ে 4। test 3-এ কোনো 0 নেই, `has_zero` False, উত্তর `n·n=4`। test 4-এ সব 0; যেকোনো একটা flip করলে আশেপাশে কোনো land নেই, total 1। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n² · α(n²))** ≈ **O(n²)** — ধাপ 1-এ প্রতিটা cell-এ ধ্রুবসংখ্যক union, ধাপ 2-এ প্রতিটা 0-এ ≤4 `find`; প্রতিটা amortized near-constant।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n²)** — DSU-র `parent`+`size` array; প্রতি 0-cell-এ `seen` set-এ বড়জোর 4টা root, তাই O(1) extra।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- distinct root গার্ড (`seen`) বাদ দেওয়া — একই island দুপাশে থাকলে size double-count হয়; classic bug।
- "কোনো 0 নেই" case ভুলে যাওয়া — তখন best 0 ফেরত যায়, অথচ উত্তর `n·n` হওয়া উচিত।
- ধাপ 1-এ চার দিক union করা (ডান+নিচ যথেষ্ট) — ভুল নয়, কিন্তু অপ্রয়োজনীয় double কাজ।
- `dsu.size[root]`-এর বদলে `dsu.size[nr*n+nc]` ব্যবহার — size শুধু root-এ নির্ভরযোগ্য, non-root node-এ নয়।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: `10`-এর size tracking আর #10 grid DSU। #10-এ island গোনা; এখানে প্রতি island-এর size রেখে best-merge খোঁজা। [../../09-graphs/](../../09-graphs/README.md)-এর island DFS দিয়েও size-map বানিয়ে করা যায়, কিন্তু DSU-তে size built-in বলে সরল। DSU snippet [../concept.md](../concept.md)-র "বারো লাইন"-এ।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Islands II (streaming connectivity) —