009 — Accounts Merge¶

Source¶

Original source: Classic record-merging exercise
Platform: LeetCode — https://leetcode.com/problems/accounts-merge/
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

1. Problem in simple words¶

কতগুলো account দেওয়া; প্রতিটা একটা list — প্রথম element নাম, বাকিগুলো email। দুটো account একই ব্যক্তির যদি তারা অন্তত একটা email শেয়ার করে (নাম মিললেও email না মিললে আলাদা)। তোমাকে account-গুলো merge করতে হবে: প্রতিটা merged account = নাম + তার সব email বর্ণানুক্রমে sorted।

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"]

2. Which basic idea does this inherit from?¶

দুটো ভিত একসাথে: ../../05-hashing/-এর 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 গড়া ছাড়াই।

6. Real-life analogy¶

ভাবো ছড়িয়ে-ছিটিয়ে থাকা contact card, প্রতিটায় একজনের কিছু email। তুমি একই লোকের card-গুলো এক করতে চাও। নিয়ম: দুটো card-এ একটা common email থাকলেই তারা একই লোক — তখন এক card-কে আরেকটার সাথে clip করে দাও (union)। common email-এর শৃঙ্খল ধরে অনেক card একসাথে জুড়ে যায়, যদিও দুই প্রান্তের card-এ হয়তো একটাও common email নেই।

7. Visual explanation¶

প্রতিটা email প্রথমবার দেখলে map-এ owner account রাখো; আবার দেখলে এখনকার account-কে আগের owner-এর সাথে union করো।

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]

8. Example input and output¶

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"]]

9. Brute force thinking¶

সরল চিন্তা: account-গুলোকে node ভাবো; যেকোনো দুই account email শেয়ার করলে তাদের মধ্যে edge। তারপর DFS/BFS দিয়ে connected component বের করো, প্রতিটা component-এর সব email জড়ো করে sort করো।

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 = এক সাঁকো — জোড়া-তুলনা মুছে যায়।

14. Step-by-step dry run¶

Input (সংক্ষেপে): acc0=[John,a,b], acc1=[John,a,c], acc2=[Mary,m], acc3=[John,j]:

acc0: a নতুন → owner[a]=0; b নতুন → owner[b]=0
acc1: a আগে দেখা (owner 0) → union(1,0); c নতুন → owner[c]=1
acc2: m নতুন → owner[m]=2
acc3: j নতুন → owner[j]=3
bucket by root: root 0 → {a,b,c}; root 2 → {m}; root 3 → {j}
ফল: ["John",a,b,c], ["Mary",m], ["John",j] — প্রতিটায় email sorted, list-ও sorted

15. Python solution¶

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)।

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!।

18. Time complexity¶

O(N · α(A) + N log N) ≈ O(N log N) — N মোট email, A account-সংখ্যা; প্রতিটা email একবার দেখা (union/find amortized near-constant), আর শেষে email sort করা dominating।

19. Space complexity¶

O(N) — email_to_acc map, merged bucket-set, আর parent/size array — সবই মোট email-সংখ্যার সমানুপাতিক।

20. Common mistakes¶

email-কে DSU node বানানো (account-এর বদলে) — কাজ করে কিন্তু email-id ↔ index mapping রাখতে হয়; account-কে node ধরাই সহজ ও সরাসরি।
bucket করতে parent[i] ব্যবহার করা find(i)-এর বদলে — tree flat না হলে parent ≠ representative; classic bug।
email sort বা list sort বাদ দেওয়া — তখন output non-deterministic হয়; statement sorted email চায়।
merged email রাখতে list ব্যবহার করা set-এর বদলে — তখন একই email duplicate হতে পারে।

21. Which basic problem this inherits from¶

ভিত্তি দুটো: ../../05-hashing/-এর hash-map bucketing — email → owner lookup; আর এই tracker-এর grouping pattern (Pattern D) — shared key দিয়ে record merge। DFS দিয়েও component বের করা যায়, কিন্তু সেজন্য account-জোড়ার মধ্যে edge গড়তে হয় (O(A²)-ঘেঁষা); DSU + map সেই খরচ এড়িয়ে প্রতি email একবার দেখেই merge সারে।

22. Similar harder problems¶

Smallest String With Swaps (group বানিয়ে ভেতরে sort) — https://leetcode.com/problems/smallest-string-with-swaps/ (এই tracker-এর #8)
Satisfiability of Equality Equations (equivalence class) — https://leetcode.com/problems/satisfiability-of-equality-equations/ (#7)
Most Stones Removed (row/col-কে union key) — https://leetcode.com/problems/most-stones-removed-with-same-row-or-column/ (#11)

23. Pattern learned¶

Merging records by shared keys: record-কে node ধরো, shared attribute (এখানে email)-কে union করার সাঁকো; একটা key → owner map দিয়ে প্রতি key একবার দেখেই merge করো, শেষে root অনুযায়ী bucket। "merge accounts / dedupe entities / group by any shared field" শুনলে এই combo সরাসরি খাটে।

24. Final summary¶

ভবিষ্যতের আমাকে: "shared field দিয়ে record merge করো" দেখলে জোড়া-তুলনা ছাড়ো — record-কে DSU node বানাও, প্রতিটা key প্রথমবার এক owner দাবি করুক, আবার দেখলে দুই record union করো; শেষে root অনুযায়ী জড়ো করো। key = সাঁকো — এটাই record-merging-এর সবচেয়ে পরিষ্কার রূপ।

25. JavaScript solution (with test cases)¶

account = node; email = সাঁকো; email → owner Map দিয়ে union, তারপর root অনুযায়ী bucket + sort।

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।

26. TypeScript solution (with test cases)¶

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<string, number> = new Map();
  accounts.forEach((acc, i) => {
    for (let k = 1; k < acc.length; k++) {
      const email = acc[k];
      if (emailToAcc.has(email)) dsu.union(i, emailToAcc.get(email) as number);
      else emailToAcc.set(email, i);
    }
  });
  const merged: Map<number, Set<string>> = new Map();
  for (const [email, i] of emailToAcc) {
    const root = dsu.find(i);
    if (!merged.has(root)) merged.set(root, new Set());
    (merged.get(root) as Set<string>).add(email);
  }
  const res: string[][] = [];
  for (const [root, emails] of merged) {
    res.push([accounts[root][0], ...[...emails].sort()]);
  }
  res.sort((a, b) => (a < b ? -1 : a > b ? 1 : 0));
  return res;
}
function expectArr(actual: string[][], exp: string[][], msg = ""): void {
  if (JSON.stringify(actual) !== JSON.stringify(exp)) throw new Error(`FAIL ${msg}`);
}
expectArr(accountsMerge([
  ["John", "johnsmith@mail.com", "john_newyork@mail.com"],
  ["John", "johnsmith@mail.com", "john00@mail.com"],
  ["Mary", "mary@mail.com"],
  ["John", "johnnybravo@mail.com"],
]), [
  ["John", "john00@mail.com", "john_newyork@mail.com", "johnsmith@mail.com"],
  ["John", "johnnybravo@mail.com"],
  ["Mary", "mary@mail.com"],
], "merge");
expectArr(accountsMerge([["A", "a@m.com"], ["A", "a@m.com"]]), [["A", "a@m.com"]], "identical");
console.log("সব TS test pass!");

TS টীকা: string[][] (accounts ও output) আর Map<string, number> (email→owner), Map<number, Set<string>> (root→emails) — প্রতিটা গঠন আলাদা type-এ locked, তাই email-id আর account-index দুর্ঘটনাবশত মেশানো যায় না; strict mode-এ Map.get-এর undefined as দিয়ে narrow করতে বাধ্য করে, যা missing-key bug ধরায়।

27. কোথায় কাজে লাগে (real-world use)¶

Identity / entity resolution: ছড়ানো record (contact, customer profile) shared key (email/phone) দিয়ে এক ব্যক্তিতে merge করা।
De-duplication: ডেটাবেসে একই entity-র একাধিক entry transitively জুড়ে একটা canonical record বানানো।
Account linking: একাধিক login/account একই user-এর কিনা shared attribute দিয়ে নির্ধারণ।
Graph clustering by shared attribute: যেকোনো "একটা common field শেয়ার করলে এক দল" সম্পর্ক — transitive group বানানো।
Fraud / network analysis: shared device/card/IP দিয়ে সম্পর্কিত account-গুলো এক cluster-এ আনা।

মূল pattern: record = node, shared field = union করার সাঁকো; key → owner map দিয়ে প্রতি key একবার দেখে merge, শেষে root অনুযায়ী bucket।

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