Problem link ও উৎস
- **Original source:** Classic creative-grouping exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** creative union keys (rows/cols as nodes)
- **Basic idea inherited from:** `10`-এর grouping pattern; এখানে row আর column নিজেরাই DSU node — DSU-র আসল interview-শক্তি
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
2D সমতলে কতগুলো stone, প্রতিটার `[row, col]` দেওয়া। একটা stone **সরানো যায়** যদি ওই same row বা same column-এ আরও একটা stone থাকে। তুমি যতবার খুশি সরাতে পারো; বলো **সর্বোচ্চ কতগুলো** stone সরানো সম্ভব।
```text
stones = (0,0)(0,1)(1,0)(1,2)(2,1)(2,2)
সব stone row/column শৃঙ্খলে একে অপরের সাথে যুক্ত -> এক group
n - (group-সংখ্যা) = 6 - 1 = 5 -> উত্তর: 5
```
### Input ও output {#8-example-input-and-output}
```text
Input : [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
Output: 5 (সব এক group; 6 - 1)
Input : [[0,0],[0,2],[1,1],[2,0],[2,2]]
Output: 3 (দুই group; 5 - 2)
Edge case (একটা stone): [[0,0]] -> 0 (সঙ্গী নেই)
Edge case (দুই বিচ্ছিন্ন): [[0,0],[1,1]] -> 0 (দুই group, কেউ সরে না)
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো প্রতিটা **row একটা করিডোর**, প্রতিটা **column একটা করিডোর**। একটা stone হলো এক row-করিডোর আর এক col-করিডোর-এর সংযোগস্থলে রাখা একটা দরজা — সে ওই দুই করিডোরকে যুক্ত করে দেয়। দুটো করিডোর যদি কোথাও একটা stone-দরজা দিয়ে জোড়া থাকে, তারা একই "ভবন"-এর অংশ। এক ভবনের যত stone, একটা বাদে সব সরানো যায়।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
মূল ভিত হলো এই tracker-এর **grouping pattern (Pattern D)**, তবে একটা সৃজনশীল মোচড়সহ। সরাসরি stone-কে stone-এর সাথে জোড়ার বদলে, **row আর column-কেই DSU node বানাও**। যেসব stone একই row বা column শেয়ার করে — সরাসরি বা ঘুরিয়ে — তারা এক group। এই "row/col-কে node" দৃষ্টিভঙ্গিই DSU-র আসল interview-শক্তি।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic দুই অংশে:
- **কত সরানো যায়:** একটা connected group-এ `k` stone থাকলে, তুমি `k − 1` টা সরাতে পারো — শেষ একটা রেখে দিতে হয় (সরানোর নিয়মে অন্তত একটা সঙ্গী লাগে)। তাই মোট সরানো = `n − (group-সংখ্যা)`।
- **কীভাবে group বানাবে:** দুটো stone যুক্ত যদি তারা row বা column শেয়ার করে। একই row-এর সব stone এক group, একই column-এরও — তাই **প্রতিটা row আর প্রতিটা column-কে node ধরে** ওই stone-এর row-node ও col-node union করলে শৃঙ্খলটা আপনাআপনি গড়ে।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **DSU** যেখানে node দুই ধরনের: row-গুলো আর column-গুলো (collision এড়াতে column-কে আলাদা namespace, যেমন `col + 10001` বা একটা dictionary দিয়ে id)। প্রতিটা stone তার row-node আর col-node union করে। শেষে আলাদা root-সংখ্যা গুনি।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা "কয়টা আলাদা যুক্ত দল?" — grouping, path নয়। কিন্তু সরাসরি stone-জোড়া union করলে O(n²) তুলনা লাগত। row/column-কে node বানানোর creative চাল-এ প্রতিটা stone মাত্র **একটা** union করে (তার row ও col), আর shared row/col আপনাআপনি stone-দের জুড়ে দেয় — DSU তখন সবচেয়ে elegant fit।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: stone-গুলোকে node ভাবো; প্রতি জোড়া stone তুলনা করো — row বা column মিললে edge। তারপর DFS/BFS দিয়ে connected component গোনো; উত্তর = n − component।
```text
1) প্রতি জোড়া (i, j): row সমান বা col সমান হলে -> edge
2) DFS দিয়ে component গোনো
3) উত্তর = n - component-সংখ্যা
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি জোড়া stone তুলনা করা O(n²), তারপর DFS — বড় n-এ ধীর। row/col-কে node বানানোর চালে প্রতিটা stone মাত্র দুটো union করে (row+col), মোট O(n·α) ≈ O(n)। জোড়া-তুলনা সম্পূর্ণ বাদ — shared row/col নিজেই stone-দের জুড়ে দেয়। এটাই creative-key-র মূল লাভ।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **row আর column-কে DSU node বানাও — stone নিজে edge।** একটা stone `(r, c)` তার row-node আর col-node-কে union করে; একই row বা col-এর stone-গুলো তখন এক group-এ এসে পড়ে আপনাআপনি, কোনো জোড়া-তুলনা ছাড়াই। উত্তর = n − (group-সংখ্যা)।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
DSU নাও যেখানে row-id আর col-id আলাদা থাকে (col-কে `col + offset` বা dict-id দিয়ে আলাদা করো, যাতে row 0 আর col 0 না মেশে)। প্রতিটা stone-এ `union(row_id, col_id)`। শেষে stone-গুলোর representative-set-এর আকার = group-সংখ্যা; উত্তর `n − group-সংখ্যা`। মোট O(n·α)।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "কোন কোন stone একই row/col-এ, জোড়ায় জোড়ায় মিলাই" — এই জোড়া-তুলনার চিন্তা ছাড়ো। বদলে ভাবো "প্রতিটা row আর column একটা করিডোর (node); stone ওই দুই করিডোর জোড়ার আঠা।" Element (stone) নয়, তার **coordinate-গুলোকে** node বানানোই এই problem-এর আসল চাবি — DSU-র সবচেয়ে সৃজনশীল রূপ।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা stone-এ তার row-node আর col-node union করো; group-সংখ্যা বের করে `n − group` ফেরাও।
```text
stones: (0,0) (0,1) (1,0) row-node: r0,r1 ; col-node: c0,c1
(0,0): union(r0, c0) r0—c0 যুক্ত
(0,1): union(r0, c1) r0 আগেই group-এ -> c1-ও টেনে আনে: {r0,c0,c1}
(1,0): union(r1, c0) c0 আগের group-এ -> r1-ও যোগ: {r0,r1,c0,c1}
forest (এক group):
r0
/ | \
c0 c1 r1 সব 3 stone এক group
group-সংখ্যা = 1 -> সরানো যায় = n - group = 3 - 1 = 2
------ দুই আলাদা group: (0,0)(0,1)(2,2) ------
(0,0),(0,1): {r0,c0,c1} (2,2): {r2,c2} (আলাদা!)
group-সংখ্যা = 2 -> সরানো = 3 - 2 = 1
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `[[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]`, n=6 (row-id = r, col-id = c আলাদা namespace):
1. (0,0) → `union(r0, c0)` → {r0,c0}
2. (0,1) → `union(r0, c1)` → r0 group-এ, c1 যোগ → {r0,c0,c1}
3. (1,0) → `union(r1, c0)` → c0 group-এ, r1 যোগ → {r0,r1,c0,c1}
4. (1,2) → `union(r1, c2)` → r1 group-এ, c2 যোগ → {r0,r1,c0,c1,c2}
5. (2,1) → `union(r2, c1)` → c1 group-এ, r2 যোগ → সব এক group
6. (2,2) → `union(r2, c2)` → দুটোই আগেই এক group → `False`, কিছু বদলায় না
7. stone-গুলোর distinct root = 1 → উত্তর = `6 − 1` = **5**
## কোড ও ব্যাখ্যা {#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
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 remove_stones(stones):
n = len(stones)
dsu = DSU(n) # node হবে stone-index, key দিয়ে জোড়া
row_first = {} # প্রতিটা row প্রথম যে stone-এ দেখা
col_first = {} # প্রতিটা col প্রথম যে stone-এ দেখা
for i, (r, c) in enumerate(stones):
if r in row_first:
dsu.union(i, row_first[r]) # একই row -> আগের stone-এর সাথে merge
else:
row_first[r] = i
if c in col_first:
dsu.union(i, col_first[c]) # একই col -> আগের stone-এর সাথে merge
else:
col_first[c] = i
roots = {dsu.find(i) for i in range(n)} # distinct group-সংখ্যা
return n - len(roots) # প্রতি group থেকে একটা বাদে সব সরে
# ---- tests ----
assert remove_stones([[0, 0], [0, 1], [1, 0], [1, 2], [2, 1], [2, 2]]) == 5
assert remove_stones([[0, 0], [0, 2], [1, 1], [2, 0], [2, 2]]) == 3
assert remove_stones([[0, 0]]) == 0 # সঙ্গী নেই
assert remove_stones([[0, 0], [1, 1]]) == 0 # দুই আলাদা group
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dsu = DSU(n)` — এই বাস্তবায়নে node হলো **stone-index**, আর row/col-কে dictionary-key বানিয়ে stone-দের জোড়া হয় (row/col-id সরাসরি node বানানোর সমতুল্য, কিন্তু index-collision-মুক্ত)।
- `row_first` / `col_first` — প্রতিটা row বা column প্রথম যে stone-এ দেখা গেছে, সেটা মনে রাখে — যাতে একই row/col-এর পরের stone আগের stone-এর সাথে merge করতে পারে।
- `if r in row_first: dsu.union(i, row_first[r])` — এই stone-এর row আগে দেখা গেলে, এখনকার stone-কে সেই আগের stone-এর সাথে এক group-এ আনো।
- col-এর জন্য একই — একই column-এর stone-দের জোড়ে।
- `roots = {dsu.find(i) for i in range(n)}` — সব stone-এর representative জড়ো করে distinct group-সংখ্যা বের করা।
- `return n - len(roots)` — প্রতি group থেকে একটা stone রেখে বাকি সব সরানো যায়, তাই n − group।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ সব stone row/col শৃঙ্খলে এক group → distinct root 1 → 6−1 = 5। দ্বিতীয়টায় দুটো আলাদা group তৈরি হয় (একটা corner-জোড়া, একটা মাঝের একা সারি/স্তম্ভ) → 5−2 = 3। একক-stone case-এ 1 group, কোনো সঙ্গী নেই → 1−1 = 0। দুই-বিচ্ছিন্ন case-এ 2 group → 2−2 = 0। শেষে print: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n · α(n))** ≈ **O(n)** — প্রতিটা stone বড়জোর দুটো union (row + col), প্রতিটা amortized near-constant; শেষে n বার `find`। জোড়া-তুলনার O(n²) সম্পূর্ণ এড়ানো।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(n)** — `parent` + `size` array, আর `row_first` / `col_first` map — সবই stone-সংখ্যার সমানুপাতিক।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- row-id আর col-id একই namespace-এ রাখা (যেমন raw `row` আর raw `col`) — তখন row 0 আর col 0 ভুল করে মিশে যায়; offset (`col + 10001`) বা আলাদা dict-id লাগে। (এখানে stone-index-কে node করে সেই ফাঁদ এড়ানো হয়েছে।)
- `n − group`-এর বদলে `group` বা `n` ফেরানো — উত্তর হলো সরানো-সংখ্যা = মোট − টিকে-থাকা।
- জোড়ায় জোড়ায় stone union করার চেষ্টা (O(n²)) — creative-key পুরো এই খরচ মুছে দেয়।
- distinct root গুনতে `find` না করে `parent` ব্যবহার করা — classic DSU bug।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি: এই tracker-এর grouping pattern (Pattern D) — shared key দিয়ে union। এখানে নতুনত্ব হলো **key নিজেই node** (row/column), element নয়। DFS দিয়েও stone-জোড়ার graph-এ component গোনা যায়, কিন্তু সেজন্য O(n²) edge গড়তে হয়; row/col-কে node বানানো DSU সেই খরচ এড়ায়। এই "coordinate-কে node" চোখটাই grid/geometry problem-এ DSU-র শক্তি।
### পরের অনুশীলন {#22-similar-harder-problems}
- Number of Islands (DSU variant — cell-কে node) —