Problem link ও উৎস
- **Original source:** Classic record-merging exercise
- **Platform:** LeetCode —
- **Topic:** disjoint set union
- **Difficulty:** Medium
- **Pattern:** merging records by shared keys
- **Basic idea inherited from:** `05-hashing`-এর map bucketing + `10`-এর grouping; shared email দিয়ে account union, তারপর find দিয়ে bucket
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো account দেওয়া; প্রতিটা একটা list — প্রথম element নাম, বাকিগুলো email। দুটো account **একই ব্যক্তির** যদি তারা **অন্তত একটা email শেয়ার** করে (নাম মিললেও email না মিললে আলাদা)। তোমাকে account-গুলো merge করতে হবে: প্রতিটা merged account = নাম + তার সব email বর্ণানুক্রমে sorted।
```text
acc0 = ["John", "a@x.com", "b@x.com"]
acc1 = ["John", "a@x.com", "c@x.com"] <- a@x.com শেয়ার করে
acc2 = ["Mary", "m@x.com"]
acc0 আর acc1 এক ব্যক্তি (a@x.com সাঁকো) ->
["John", "a@x.com", "b@x.com", "c@x.com"] আর ["Mary", "m@x.com"]
```
### Input ও output {#8-example-input-and-output}
```text
Input :
[["John","johnsmith@mail.com","john_newyork@mail.com"],
["John","johnsmith@mail.com","john00@mail.com"],
["Mary","mary@mail.com"],
["John","johnnybravo@mail.com"]]
Output (sorted):
[["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
["John","johnnybravo@mail.com"],
["Mary","mary@mail.com"]]
Edge case (একই দুই account): [["A","a@m.com"],["A","a@m.com"]] -> [["A","a@m.com"]]
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো ছড়িয়ে-ছিটিয়ে থাকা contact card, প্রতিটায় একজনের কিছু email। তুমি একই লোকের card-গুলো এক করতে চাও। নিয়ম: দুটো card-এ **একটা common email** থাকলেই তারা একই লোক — তখন এক card-কে আরেকটার সাথে clip করে দাও (union)। common email-এর শৃঙ্খল ধরে অনেক card একসাথে জুড়ে যায়, যদিও দুই প্রান্তের card-এ হয়তো একটাও common email নেই।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
দুটো ভিত একসাথে: [../../05-hashing/](../../05-hashing/README.md)-এর **map bucketing** — কোন email আগে কোন account-এ দেখেছি, সেটা একটা hash-map-এ রাখো; আর এই tracker-এর **grouping pattern (Pattern D)** — shared email পেলেই দুই account union করো। DSU হলো equivalence-relation engine; "একটা email শেয়ার করে, transitively" — ঠিক DSU-আকৃতির সম্পর্ক।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **equivalence relation** account-দের উপর: "email শেয়ার করে" সম্পর্কটা reflexive, symmetric, আর transitive (acc0–acc1 আর acc1–acc2 শেয়ার করলে তিনজনই এক ব্যক্তি, যদিও acc0 আর acc2 হয়তো সরাসরি কোনো email শেয়ার করে না)। এই transitive merge-ই key — তাই node হিসেবে **account** নাও, আর shared email-কে union করার সাঁকো বানাও।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
তিনটা: একটা **DSU** account-সংখ্যা-সমান (account index = node); একটা **hash-map** `email → প্রথম যে account-এ দেখা গেছে` (শেয়ার ধরতে); আর শেষে একটা **map** `root → set of emails` (merged ফল গড়তে)।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
প্রশ্নটা বিশুদ্ধ "কোন record-গুলো একই entity?" — grouping, path নয়। DSU shared-key দিয়ে record merge করার জন্য আদর্শ, আর hash-map দ্রুত বলে দেয় কোন email আগে কোথায় ছিল। দুটো মিলে transitive merge near-constant time-এ সারে — DFS-এর adjacency গড়া ছাড়াই।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
সরল চিন্তা: account-গুলোকে node ভাবো; যেকোনো দুই account email শেয়ার করলে তাদের মধ্যে edge। তারপর DFS/BFS দিয়ে connected component বের করো, প্রতিটা component-এর সব email জড়ো করে sort করো।
```text
1) প্রতি জোড়া account তুলনা করে shared email আছে কি না দেখো -> edge
2) DFS দিয়ে account-গুলোর component বের করো
3) প্রতি component: সব email union (set), sort, নাম যোগ করো
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতি জোড়া account তুলনা করা O(A²) (A = account-সংখ্যা), প্রতিটায় email-set মেলানো আরও খরচ — বড় input-এ ধীর। DSU + hash-map পথে প্রতিটা email একবারই দেখো: map বলে দেয় owner, union সাঁকো বাঁধে — মোট কার্যত email-সংখ্যার রৈখিক (sort বাদে)। জোড়া-তুলনার দরকারই নেই।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **node হবে account, আর email হবে union করার সাঁকো** — email নিজে node নয়। প্রতিটা email প্রথমবার একটা account "owns"; পরে একই email আরেক account-এ দেখলে দুটো account union করো। এই owner-map-ই transitive merge-কে O(email)-এ নামিয়ে আনে।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
account-সংখ্যা-সমান DSU নাও আর একটা `email → owner-account` map। প্রতিটা account ঘুরে তার প্রতিটা email দেখো: map-এ থাকলে এখনকার account-কে owner-এর সাথে union করো, নাহলে এখনকার account-কে owner করে map-এ রাখো। শেষে প্রতিটা email-কে তার owner-এর `find`-root অনুযায়ী bucket করো; প্রতি bucket-এ নাম + sorted email বসাও। মোট O(N·α + N log N), N = মোট email।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "প্রতি জোড়া account মিলিয়ে দেখি email শেয়ার করে কি না" — এই জোড়া-তুলনার চিন্তা ছাড়ো। বদলে ভাবো "প্রতিটা email-কে জিজ্ঞেস করি — তোমাকে আগে কে দাবি করেছিল? করে থাকলে ওই দুই account এক।" এক email = এক সাঁকো — জোড়া-তুলনা মুছে যায়।
### ছবিতে বোঝা {#7-visual-explanation}
প্রতিটা email প্রথমবার দেখলে map-এ owner account রাখো; আবার দেখলে এখনকার account-কে আগের owner-এর সাথে union করো।
```text
accounts:
acc0 John: a@x, b@x
acc1 John: a@x, c@x
acc2 Mary: m@x
email_to_acc (প্রথম দেখা): {}
acc0: a@x নতুন -> owner[a@x]=0 ; b@x নতুন -> owner[b@x]=0
acc1: a@x আগে দেখা (owner 0) -> union(1, 0) ; c@x নতুন -> owner[c@x]=1
acc2: m@x নতুন -> owner[m@x]=2
DSU: *0 *2 (acc1 ঝোলে acc0-র নিচে)
|
1
root অনুযায়ী email জড়ো করো:
find(0)=0, find(1)=0, find(2)=2; email map থেকে:
root 0 -> {a@x, b@x, c@x} (acc0+acc1)
root 2 -> {m@x}
প্রতি bucket: নাম (root account থেকে) + sorted email
-> ["John", a@x, b@x, c@x]
-> ["Mary", m@x]
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input (সংক্ষেপে): `acc0=[John,a,b], acc1=[John,a,c], acc2=[Mary,m], acc3=[John,j]`:
1. acc0: `a` নতুন → owner[a]=0; `b` নতুন → owner[b]=0
2. acc1: `a` আগে দেখা (owner 0) → `union(1,0)`; `c` নতুন → owner[c]=1
3. acc2: `m` নতুন → owner[m]=2
4. acc3: `j` নতুন → owner[j]=3
5. bucket by root: root 0 → {a,b,c}; root 2 → {m}; root 3 → {j}
6. ফল: ["John",a,b,c], ["Mary",m], ["John",j] — প্রতিটায় email sorted, list-ও sorted
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
from collections import defaultdict
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 accounts_merge(accounts):
dsu = DSU(len(accounts))
email_to_acc = {} # email -> প্রথম যে account দাবি করেছে
for i, acc in enumerate(accounts):
for email in acc[1:]: # acc[0] নাম, বাকি সব email
if email in email_to_acc:
dsu.union(i, email_to_acc[email]) # shared email -> merge
else:
email_to_acc[email] = i
merged = defaultdict(set) # root -> সেই ব্যক্তির সব email
for email, i in email_to_acc.items():
merged[dsu.find(i)].add(email)
res = []
for root, emails in merged.items():
name = accounts[root][0] # root account থেকে নাম
res.append([name] + sorted(emails))
return sorted(res)
# ---- tests ----
out = accounts_merge([
["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["John", "johnsmith@mail.com", "john00@mail.com"],
["Mary", "mary@mail.com"],
["John", "johnnybravo@mail.com"],
])
assert out == [
["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
["John", "johnnybravo@mail.com"],
["Mary", "mary@mail.com"],
]
assert accounts_merge([["A", "a@m.com"], ["A", "a@m.com"]]) == [["A", "a@m.com"]]
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `dsu = DSU(len(accounts))` — node হলো account, তাই DSU-র size account-সংখ্যা।
- `for email in acc[1:]` — index 0 নাম, তাই index 1 থেকে email-গুলো ঘুরি।
- `if email in email_to_acc: dsu.union(i, email_to_acc[email])` — email আগে কেউ দাবি করে থাকলে, এখনকার account-কে সেই আগের account-এর সাথে merge করো।
- `else: email_to_acc[email] = i` — নতুন email হলে এখনকার account-কে এর owner হিসেবে রাখো।
- `merged[dsu.find(i)].add(email)` — প্রতিটা email-কে তার owner-এর representative-root অনুযায়ী bucket করো; এক root = এক ব্যক্তি।
- `name = accounts[root][0]` — bucket-এর root-account থেকে নাম নাও (group-এর সবার নাম একই)।
- `res.append([name] + sorted(emails))` ও `return sorted(res)` — প্রতিটা account-এ email sorted, আর পুরো list-ও sorted (deterministic output)।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
প্রথম test-এ acc0 আর acc1 `johnsmith@mail.com` শেয়ার করে → এক ব্যক্তি, তিন email একত্রে sorted; acc2 (Mary) আলাদা; acc3 (johnnybravo) আলাদা John — মোট তিনটা merged account, list sorted। দ্বিতীয়টায় দুই identical account এক email শেয়ার করে এক হয়ে যায় → একটাই account। শেষে print: `সব test pass!`।
### JavaScript ও test cases {#25-javascript-solution-with-test-cases}
account = node; email = সাঁকো; `email → owner` Map দিয়ে union, তারপর root অনুযায়ী bucket + sort।
```javascript
const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
class DSU {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.size = new Array(n).fill(1);
}
find(x) {
while (this.parent[x] !== x) { this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; }
return x;
}
union(x, y) {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
if (this.size[rx] < this.size[ry]) [rx, ry] = [ry, rx];
this.parent[ry] = rx; this.size[rx] += this.size[ry];
return true;
}
}
// প্রতিটা account: [name, email1, email2, ...]; merged accounts sorted ফেরত
function accountsMerge(accounts) {
const dsu = new DSU(accounts.length);
const emailToAcc = new Map(); // email -> প্রথম যে account দাবি করেছে
accounts.forEach((acc, i) => {
for (let k = 1; k < acc.length; k++) { // acc[0] নাম, বাকি email
const email = acc[k];
if (emailToAcc.has(email)) dsu.union(i, emailToAcc.get(email)); // shared -> merge
else emailToAcc.set(email, i);
}
});
const merged = new Map(); // root -> Set of emails
for (const [email, i] of emailToAcc) {
const root = dsu.find(i); // parent নয়, find!
if (!merged.has(root)) merged.set(root, new Set());
merged.get(root).add(email);
}
const res = [];
for (const [root, emails] of merged) {
const name = accounts[root][0];
res.push([name, ...[...emails].sort()]); // email sorted
}
res.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0)); // list-ও sorted (deterministic)
return res;
}
// ---- test cases (example + edge) ----
const out = accountsMerge([
["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["John", "johnsmith@mail.com", "john00@mail.com"],
["Mary", "mary@mail.com"],
["John", "johnnybravo@mail.com"],
]);
assert(JSON.stringify(out) === JSON.stringify([
["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
["John", "johnnybravo@mail.com"],
["Mary", "mary@mail.com"],
]), "merge");
assert(JSON.stringify(accountsMerge([["A", "a@m.com"], ["A", "a@m.com"]])) ===
JSON.stringify([["A", "a@m.com"]]), "identical"); // edge
console.log("সব JS test pass!");
```
> **JS টীকা:** bucket করতে অবশ্যই `dsu.find(i)` ব্যবহার করো, `this.parent[i]` নয় — tree flat না হলে parent ≠ representative (classic bug)। merged email রাখতে `Set` (duplicate এড়াতে), তারপর `[...emails].sort()` দিয়ে sorted array। JS-এ array-of-arrays sort করতে default comparator string-coerce করে যা এখানে কাজ করে, তবু স্পষ্টতার জন্য explicit `(a,b)=>...` দেওয়া; ফল মেলাতে `JSON.stringify`।
### TypeScript ও test cases {#26-typescript-solution-with-test-cases}
```typescript
class DSU {
private parent: number[];
private size: number[];
constructor(n: number) {
this.parent = Array.from({ length: n }, (_, i) => i);
this.size = new Array(n).fill(1);
}
find(x: number): number {
while (this.parent[x] !== x) { this.parent[x] = this.parent[this.parent[x]]; x = this.parent[x]; }
return x;
}
union(x: number, y: number): boolean {
let rx = this.find(x), ry = this.find(y);
if (rx === ry) return false;
if (this.size[rx] < this.size[ry]) [rx, ry] = [ry, rx];
this.parent[ry] = rx; this.size[rx] += this.size[ry];
return true;
}
}
function accountsMerge(accounts: string[][]): string[][] {
const dsu = new DSU(accounts.length);
const emailToAcc: Map