013 — Clone Graph

Source

• Original source: Classic graph deep-copy exercise
• Platform: LeetCode — https://leetcode.com/problems/clone-graph/
• Topic: graphs
• Difficulty: Medium
• Pattern: traversal + copy map (deep copy of a graph)
• Basic idea inherited from: hash maps (../../05-hashing/); DFS/BFS traversal (../dfs.md, ../bfs.md)

1. Problem in simple words

তোমাকে একটা connected undirected graph-এর একটা node দেওয়া আছে (reference হিসেবে)। প্রতিটা node-এ একটা val আর একটা neighbors list আছে। তোমাকে পুরো graph-টার একটা deep copy বানাতে হবে — মানে প্রতিটা node-এর জন্য একটা সম্পূর্ণ নতুন object, আর copy-graph-এর connection-গুলো হুবহু original-এর মতো, কিন্তু কোনো node share করা যাবে না। নতুন graph-এর starting node ফেরত দাও।

original:  1 -- 2        copy:  1' -- 2'
           |    |               |     |
           4 -- 3              4' -- 3'
(সব node নতুন object, structure এক)

2. Which basic idea does this inherit from?

মূল ভিত দুটো: hash map (../../05-hashing/) আর graph traversal (../dfs.md, ../bfs.md)। Traversal দিয়ে প্রতিটা node একবার করে ছুঁই; আর একটা hash map (old node -> new node) দিয়ে মনে রাখি কাকে আগেই copy করেছি। এই map-টাই দুটো কাজ একসাথে করে — visited-marker, আর "এই original-এর copy কোনটা" সেটার lookup। নতুন algorithm নয়, চেনা traversal-এর পাশে একটা mapping বইয়ে নেওয়া।

3. What is the hidden math or logic?

লুকানো logic: graph-এ cycle আছে, তাই naive recursion অসীম loop করবে — 1 -> 2 -> 1 -> 2 ...। চাবি হলো প্রতিটা node-কে প্রথমবার দেখলেই তার copy বানিয়ে map-এ রেখে দেওয়া, তারপর neighbors-এ নামা। তাই যখন পরে আবার একই original-এ পৌঁছাই, map-এ তার copy পেয়ে যাই আর সেটাই reuse করি — নতুন করে বানাই না। এই "create-then-recurse, map first" order-টাই cycle সামলায় আর প্রতিটা node ঠিক একবার copy নিশ্চিত করে।

4. Which data structure is needed?

• hash map old -> new — প্রতিটা original node-এর copy কোনটা; visited-marker-ও বটে।
• DFS recursion বা BFS collections.deque — পুরো graph traverse করতে।
• node objects — প্রতিটা copy-তে val ও neighbors list।

5. Why this data structure fits

hash map fit করে কারণ মূল প্রশ্ন "এই original node-এর copy আগে বানিয়েছি কি, বানিয়ে থাকলে কোনটা?" — দুটোই O(1) lookup, ঠিক যা map দেয়; আর map-এ থাকা মানেই visited, তাই আলাদা visited set লাগে না। DFS/BFS দুটোই fit করে কারণ deep-copy-র জন্য শুধু প্রতিটা node ও edge একবার ছোঁয়া দরকার — order বা distance এখানে অপ্রাসঙ্গিক, যেকোনো traversal চলে। node object fit করে কারণ আমরা সত্যিকারের নতুন structure বানাচ্ছি, value নয়।

6. Real-life analogy

একটা বন্ধুদের network-এর হুবহু নকল তালিকা বানানো ভাবো। প্রতিটা আসল ব্যক্তির জন্য একটা নতুন কার্ড লেখো, আর একটা খাতায় টুকে রাখো "আসল-X → নতুন-কার্ড-X"। এখন আসল-X-এর প্রতিটা বন্ধুর জন্য: খাতায় দেখো তার নতুন কার্ড আছে কিনা — থাকলে সেটাই X-এর কার্ডে বন্ধু হিসেবে জোড়ো; না থাকলে আগে তার কার্ড বানাও। খাতা (map) ছাড়া তুমি একই ব্যক্তির বারবার কার্ড বানাতে, আর বন্ধুত্বের চক্রে চিরকাল ঘুরতে থাকতে।

7. Visual explanation

1 -- 2, 1 -- 4, 2 -- 3, 3 -- 4 (4-চক্র) দিয়ে DFS clone:

original:        DFS(1):
  1 -- 2           map = {1:1'}
  |    |           DFS(2): map={1:1',2:2'}
  4 -- 3             DFS(1)? map-এ আছে -> 1' reuse (cycle থামল)
                     DFS(3): map={...,3:3'}
                       DFS(2)? map-এ আছে -> 2' reuse
                       DFS(4): map={...,4:4'}
                         DFS(1)? map-এ আছে -> 1'
                         DFS(3)? map-এ আছে -> 3'
ফল: 1'--2', 1'--4', 2'--3', 3'--4'  (সব নতুন object)

8. Example input and output

Input : adjacency = [[2,4],[1,3],[2,4],[1,3]]   (node i+1-এর প্রতিবেশী)
Output: একটা নতুন graph, structure হুবহু এক, কিন্তু সব node আলাদা object

Input : adjacency = [[]]                          (একটা node, প্রতিবেশী নেই)
Output: একটাই নতুন node, val 1, খালি neighbors

Edge case (খালি graph): node = None -> None

9. Brute force thinking

প্রথম (ভুল) সরল চিন্তা: কোনো map ছাড়া recursively প্রতিটা node-এর copy বানিয়ে neighbors-এ নামা।

1) clone(node): একটা new node বানাও
2) node-এর প্রতিটা প্রতিবেশীর জন্য clone(প্রতিবেশী) ডাকো আর new node-এ জোড়ো
3) (কিন্তু কোনো "আগে দেখেছি" নেই)

10. Why brute force is slow

map ছাড়া এটা শুধু ধীর নয়, সম্পূর্ণ ভুল: graph-এ cycle থাকায় 1 -> 2 -> 1 -> 2 -> ... অসীম recursion-এ stack overflow করে। আর cycle না থাকলেও একই node একাধিক path দিয়ে পৌঁছানো যায়, ফলে duplicate copies তৈরি হয় আর structure ভেঙে যায়। map যোগ করলে প্রতিটা node ঠিক একবার copy হয়, repeated visit O(1)-এ থেমে যায় — পুরোটা O(V + E)। তাই map বাড়তি optimization নয়, correctness-এর শর্ত।

11. Key observation

মূল observation: node-টা create করো আর map-এ রাখো recurse করার আগে। তাহলে একটা node তার নিজের cycle দিয়ে ফিরে এলে map-এ ইতিমধ্যেই তার copy আছে — অসীম loop থামে, আর কোনো node দুবার copy হয় না। এই একটাই order-নিয়ম পুরো problem-টাকে নিরাপদ করে।

12. Optimized intuition

একটা map old -> new রাখো। clone(node): যদি node map-এ থাকে, তার copy ফেরত দাও (base case, cycle থামায়)। নাহলে একটা নতুন node বানাও, সঙ্গে সঙ্গে map[node] = new বসাও, তারপর node-এর প্রতিটা প্রতিবেশীর জন্য clone(প্রতিবেশী) ডেকে new.neighbors-এ জোড়ো। শেষে new ফেরত। প্রতিটা node ও edge একবার → O(V + E)। BFS version-এ একই map, deque দিয়ে level-by-level।

13. Thinking tweak

মোচড়: "শুধু recurse করে copy বানাব" না ভেবে ভাবো "প্রতিটা original-এর copy কোথায়, সেটা একটা map-এ মনে রাখব — আর copy-টা বানাব recurse করার আগেই, যাতে cycle ফিরে এলে map-ই তাকে থামায়।" Traversal-এর পাশে একটা lookup-table বইয়ে নেওয়াই এখানে আসল কৌশল।

14. Step-by-step dry run

adjacency = [[2],[1]] (দুই node, 1 -- 2) দিয়ে DFS:

1. clone(1): map খালি, তাই 1' বানাই, map = {1: 1'}।
2. 1-এর প্রতিবেশী 2 → clone(2): map-এ নেই, 2' বানাই, map = {1:1', 2:2'}।
3. 2-এর প্রতিবেশী 1 → clone(1): map-এ আছে → 1' ফেরত (cycle থামল)। 2'.neighbors = [1']।
4. clone(2) শেষ, 2' ফেরত। 1'.neighbors = [2']। clone(1) শেষ, 1' ফেরত। ফল: 1' -- 2', দুটোই নতুন object।

15. Python solution

from collections import deque


class Node:
    def __init__(self, val, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []


def clone_graph_dfs(node):
    if node is None:
        return None
    old_to_new = {}                          # old node -> new node (visited-ও)

    def dfs(cur):
        if cur in old_to_new:                # আগে copy করেছি -> reuse (cycle থামে)
            return old_to_new[cur]
        copy = Node(cur.val)
        old_to_new[cur] = copy               # recurse করার আগেই map-এ রাখি
        for nb in cur.neighbors:
            copy.neighbors.append(dfs(nb))
        return copy

    return dfs(node)


def clone_graph_bfs(node):
    if node is None:
        return None
    old_to_new = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in old_to_new:         # প্রথমবার দেখা -> copy বানাও, enqueue
                old_to_new[nb] = Node(nb.val)
                q.append(nb)
            old_to_new[cur].neighbors.append(old_to_new[nb])
    return old_to_new[node]


def build(adjacency):
    # adjacency[i] = node (i+1)-এর প্রতিবেশীর val list; helper for tests
    if not adjacency:
        return None
    nodes = {i + 1: Node(i + 1) for i in range(len(adjacency))}
    for i, nbrs in enumerate(adjacency):
        nodes[i + 1].neighbors = [nodes[v] for v in nbrs]
    return nodes[1]


def to_adjacency(node):
    # clone যাচাইয়ের জন্য graph -> adjacency list (BFS দিয়ে)
    if node is None:
        return []
    seen = {node.val: node}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb.val not in seen:
                seen[nb.val] = nb
                q.append(nb)
    return [[nb.val for nb in seen[v].neighbors] for v in sorted(seen)]


# ---- tests ----
adj = [[2, 4], [1, 3], [2, 4], [1, 3]]
for cloner in (clone_graph_dfs, clone_graph_bfs):
    original = build(adj)
    copied = cloner(original)
    # structure এক
    assert to_adjacency(copied) == adj
    # কিন্তু object আলাদা (deep copy, share করা নয়)
    assert copied is not original
    assert copied.neighbors[0] is not original.neighbors[0]

assert clone_graph_dfs(None) is None
single = clone_graph_dfs(build([[]]))
assert single.val == 1 and single.neighbors == []
print("সব test pass!")

16. Line-by-line code explanation

• class Node — প্রতিটা node-এ val ও neighbors list, LeetCode-এর signature-এর মতো।
• old_to_new = {} — original node থেকে তার copy-র map; map-এ থাকা মানেই visited।
• if cur in old_to_new: return old_to_new[cur] — DFS base case; আগে-copy-করা node ফিরে এলে reuse, cycle থামে।
• old_to_new[cur] = copy — recurse করার আগে map-এ বসানো, এটাই cycle-safety-র চাবি।
• BFS-এ if nb not in old_to_new: — প্রথমবার দেখা প্রতিবেশীর copy বানিয়ে enqueue; তারপর সবসময় edge জোড়া।
• copy.neighbors.append(dfs(nb)) / old_to_new[cur].neighbors.append(...) — copy-graph-এ edge পুনর্নির্মাণ।

17. Output walkthrough

দুই cloner-এই: build(adj) original graph বানায়, cloner deep copy করে। to_adjacency(copied) == adj দেখায় structure হুবহু এক। copied is not original আর copied.neighbors[0] is not original.neighbors[0] দেখায় object গুলো আলাদা — সত্যিকারের deep copy, কোনো node share করা হয়নি। None graph → None। single node → val 1, খালি neighbors। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(V + E) — প্রতিটা node একবার copy হয় (map base case পুনরাবৃত্তি ঠেকায়), প্রতিটা edge একবার করে copy-graph-এ জোড়া হয়।

19. Space complexity

O(V) — map-এ প্রতিটা node-এর একটা entry, আর DFS recursion stack / BFS queue worst case O(V)। (নতুন graph নিজে output, সাধারণত আলাদা গোনা হয় না, তবে সেটাও O(V + E)।)

20. Common mistakes

• map ছাড়া recurse করা — cycle-এ অসীম loop, stack overflow; সবচেয়ে common ভুল।
• copy-টা map-এ বসানোর আগে neighbors-এ recurse করা — তখন cycle ফিরে এলে map-এ entry নেই, আবার অসীম loop।
• map-এ val -> new রাখা (duplicate val থাকলে ভুল) — key হিসেবে আসল node object ব্যবহার করো, val নয়।
• node is None edge case না সামলানো — খালি graph-এ crash।

21. Which basic problem this inherits from

ভিত্তি: hash map (../../05-hashing/) আর graph traversal (../dfs.md, ../bfs.md)। এটা সেই প্রথম problem যেখানে traversal-এর পাশে একটা side-structure (এখানে old -> new map) বইয়ে নিয়ে কাজ করতে হয় — visited-marking আর result-building দুটোই একসাথে। মূল নতুন শিক্ষা: একটা map দিয়ে cycle থামানো আর "এই জিনিসটা আগে process করেছি কি" মনে রাখা — যে কৌশল পরে অনেক graph + DP problem-এ (memoization) ফিরে আসে। পরের ধাপ: traversal-কে উল্টোদিকে চালানো — border থেকে reverse flood, #14।

22. Similar harder problems

• Copy List with Random Pointer (একই old→new map কৌশল, linked list-এ) — https://leetcode.com/problems/copy-list-with-random-pointer/
• Pacific Atlantic Water Flow (traversal + side-state) — https://leetcode.com/problems/pacific-atlantic-water-flow/ (এই tracker-এর #14)
• Course Schedule (cycle detection, directed) — https://leetcode.com/problems/course-schedule/ (#15)

23. Pattern learned

Traversal + copy map: যখন একটা graph (বা cyclic structure) deep-copy করতে হয় — DFS/BFS চালাও আর একটা old -> new hash map বইয়ে নাও; node-টা create করে map-এ রাখো recurse করার আগে, তাহলে cycle নিরাপদে থামে আর প্রতিটা node ঠিক একবার copy হয়। map-ই একসাথে visited-marker ও copy-lookup।

24. Final summary

ভবিষ্যতের আমাকে: "Clone Graph = traversal + old -> new map; node বানাও আর map-এ রাখো recurse-এর আগে, যাতে cycle থামে; map-এ থাকলে reuse, নাহলে নতুন।" যখনই 'cyclic structure deep-copy / একই জিনিস একাধিকবার পৌঁছাই' দেখবে — একটা map বইয়ে নাও যা visited আর lookup দুটোই সামলায়, আর create-before-recurse order মনে রাখো।

25. JavaScript solution (with test cases)

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };

class GraphNode {
  constructor(val, neighbors = []) { this.val = val; this.neighbors = neighbors; }
}

function cloneGraphDFS(node) {
  if (node === null) return null;
  const oldToNew = new Map();                 // old node -> new node (visited-ও)
  const dfs = (cur) => {
    if (oldToNew.has(cur)) return oldToNew.get(cur);   // আগে copy করেছি → reuse (cycle থামে)
    const copy = new GraphNode(cur.val);
    oldToNew.set(cur, copy);                  // recurse করার আগেই map-এ রাখি
    for (const nb of cur.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

function cloneGraphBFS(node) {
  if (node === null) return null;
  const oldToNew = new Map();
  oldToNew.set(node, new GraphNode(node.val));
  const q = [node]; let head = 0;
  while (head < q.length) {
    const cur = q[head++];
    for (const nb of cur.neighbors) {
      if (!oldToNew.has(nb)) {                 // প্রথমবার দেখা → copy বানাও, enqueue
        oldToNew.set(nb, new GraphNode(nb.val));
        q.push(nb);
      }
      oldToNew.get(cur).neighbors.push(oldToNew.get(nb));
    }
  }
  return oldToNew.get(node);
}

// helper: adjacency[i] = node (i+1)-এর প্রতিবেশীর val list
function build(adjacency) {
  if (!adjacency || adjacency.length === 0) return null;
  const nodes = new Map();
  for (let i = 0; i < adjacency.length; i++) nodes.set(i + 1, new GraphNode(i + 1));
  for (let i = 0; i < adjacency.length; i++) {
    nodes.get(i + 1).neighbors = adjacency[i].map((v) => nodes.get(v));
  }
  return nodes.get(1);
}

// clone যাচাইয়ের জন্য graph -> adjacency list (BFS দিয়ে)
function toAdjacency(node) {
  if (node === null) return [];
  const seen = new Map([[node.val, node]]);
  const q = [node]; let head = 0;
  while (head < q.length) {
    const cur = q[head++];
    for (const nb of cur.neighbors) {
      if (!seen.has(nb.val)) { seen.set(nb.val, nb); q.push(nb); }
    }
  }
  return [...seen.keys()].sort((a, b) => a - b).map((v) => seen.get(v).neighbors.map((nb) => nb.val));
}

const eq = (a, b) => JSON.stringify(a) === JSON.stringify(b);

// ---- test cases ----
const adj = [[2, 4], [1, 3], [2, 4], [1, 3]];
for (const cloner of [cloneGraphDFS, cloneGraphBFS]) {
  const original = build(adj);
  const copied = cloner(original);
  assert(eq(toAdjacency(copied), adj), "structure এক");
  assert(copied !== original, "deep copy, root আলাদা");
  assert(copied.neighbors[0] !== original.neighbors[0], "neighbor আলাদা object");
}
assert(cloneGraphDFS(null) === null, "null graph");
const single = cloneGraphDFS(build([[]]));
assert(single.val === 1 && single.neighbors.length === 0, "একা node");
console.log("সব JS test pass!");

JS টীকা: Python-এর dict-এ node-object key হিসেবে রাখা যায়; JS-এ সাধারণ object key string-এ রূপান্তরিত হয়, তাই Map ব্যবহার করা জরুরি — Map আসল object-reference-কে key হিসেবে রাখে (val নয়), যা duplicate-val graph-এও সঠিক। create-before-recurse order (oldToNew.set আগে, তারপর neighbors loop) cycle থামায়, ঠিক Python version-এর মতো। !== reference-অসমতা যাচাই করে deep copy নিশ্চিত করে।

26. TypeScript solution (with test cases)

class GraphNode {
  val: number;
  neighbors: GraphNode[];
  constructor(val: number, neighbors: GraphNode[] = []) { this.val = val; this.neighbors = neighbors; }
}

function cloneGraphDFS(node: GraphNode | null): GraphNode | null {
  if (node === null) return null;
  const oldToNew = new Map<GraphNode, GraphNode>();
  const dfs = (cur: GraphNode): GraphNode => {
    const existing = oldToNew.get(cur);
    if (existing) return existing;                     // আগে copy করেছি → reuse
    const copy = new GraphNode(cur.val);
    oldToNew.set(cur, copy);                           // recurse করার আগেই map-এ
    for (const nb of cur.neighbors) copy.neighbors.push(dfs(nb));
    return copy;
  };
  return dfs(node);
}

function build(adjacency: number[][]): GraphNode | null {
  if (adjacency.length === 0) return null;
  const nodes = new Map<number, GraphNode>();
  for (let i = 0; i < adjacency.length; i++) nodes.set(i + 1, new GraphNode(i + 1));
  for (let i = 0; i < adjacency.length; i++) {
    nodes.get(i + 1)!.neighbors = adjacency[i].map((v) => nodes.get(v)!);
  }
  return nodes.get(1)!;
}

function toAdjacency(node: GraphNode | null): number[][] {
  if (node === null) return [];
  const seen = new Map<number, GraphNode>([[node.val, node]]);
  const q: GraphNode[] = [node]; let head = 0;
  while (head < q.length) {
    const cur = q[head++];
    for (const nb of cur.neighbors) {
      if (!seen.has(nb.val)) { seen.set(nb.val, nb); q.push(nb); }
    }
  }
  return [...seen.keys()].sort((a, b) => a - b).map((v) => seen.get(v)!.neighbors.map((nb) => nb.val));
}

const expect = (cond: boolean, msg = ""): void => { if (!cond) throw new Error("FAIL " + msg); };
const eq = (a: number[][], b: number[][]): boolean =>
  a.length === b.length && a.every((row, i) => row.length === b[i].length && row.every((v, j) => v === b[i][j]));

const adj: number[][] = [[2, 4], [1, 3], [2, 4], [1, 3]];
const original = build(adj);
const copied = cloneGraphDFS(original);
expect(copied !== null && eq(toAdjacency(copied), adj), "structure");
expect(copied !== original, "root আলাদা");
expect(copied!.neighbors[0] !== original!.neighbors[0], "neighbor আলাদা");
expect(cloneGraphDFS(null) === null, "null");
const single = cloneGraphDFS(build([[]]));
expect(single!.val === 1 && single!.neighbors.length === 0, "একা");
console.log("সব TS test pass!");

TS টীকা: Map<GraphNode, GraphNode> key ও value দুটোই node-object হিসেবে type করে — val (number) দিয়ে map করার ভুল compile-time-এই আটকায়, যা duplicate-val graph-এ bug হতো। oldToNew.get(cur)-এর return GraphNode | undefined, তাই if (existing) দিয়ে narrow করি (non-null assertion-এর চেয়ে নিরাপদ)। GraphNode | null signature মনে করায় খালি-graph edge case সামলাতেই হবে।

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

• Deep copy of object graphs: কোনো interconnected object-structure (যেমন একটা game state, scene graph, বা document model) hub-share ছাড়াই সম্পূর্ণ নকল করা।
• Undo/redo / snapshotting: একটা mutable graph-state-এর স্বাধীন copy রেখে পরে সেই snapshot-এ ফেরা, মূলটাকে স্পর্শ না করে।
• Serialization helpers: cyclic reference সহ structure copy/serialize করতে "old→new map" technique — JSON.stringify যেখানে cycle-এ ব্যর্থ হয়।
• Simulation / sandboxing: একটা network/dependency graph-এর copy-তে "what-if" পরিবর্তন চালানো, আসল graph অক্ষত রেখে।
• Compiler / IR transformation: একটা control-flow বা dependency graph clone করে তার উপর optimization pass চালানো।

মূল সুর: cyclic বা shared structure deep-copy করতে — traversal চালাও আর একটা old→new map বইয়ে নাও (visited + lookup একসাথে), node বানাও map-এ রাখো recurse-এর আগে যাতে cycle নিরাপদে থামে। একই memoization-চিন্তা পরে অনেক graph+DP problem-এ ফেরে।

---

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