LeetCode 133 · Graphs

Clone Graph, explained with a picture

Photocopying a city map junction by junction.

MediumGraphs
▶ Watch it step by step

The problem

Given one node of a connected undirected graph, return a deep copy of the whole graph: new nodes with the same values and the same connections.

Input:  4 junctions: 1–2, 2–3, 3–4, 4–1
Output: an identical new graph

Picture it

Picture photocopying a city map, one junction at a time. We walk the map with a queue and keep a table “original junction → its copy”. When we meet a neighbour we haven’t copied yet, we copy it and add it to the queue; either way we connect the copies.

How to recognise it

  • You must build a copy of a linked structure whose nodes point to each other, not just read it.
  • The structure is a graph: nodes can be reached by more than one path, and cycles are possible (an undirected edge is already a two-node cycle).
  • Copies must keep the same connections: if two nodes shared a neighbour, their copies must share the copy of that neighbour.
  • You are handed one node, and the problem says the graph is connected, so one traversal reaches everything.

Start with brute force

The obvious plan is a recursive copy: make a new node, then copy each neighbour and attach it. On a graph with a cycle this never stops, because node A copies B, B copies A, and so on. A safe brute force first collects all nodes in a list, then builds the copies and wires them up by looking each neighbour up in the list.

def clone_brute(node):
    if not node:
        return None
    olds, i = [node], 0
    while i < len(olds):
        for nb in olds[i].neighbors:
            if nb not in olds:                 # list scan: O(V)
                olds.append(nb)
        i += 1
    news = [Node(o.val) for o in olds]
    for o, n in zip(olds, news):
        for nb in o.neighbors:
            n.neighbors.append(news[olds.index(nb)])   # O(V) again
    return news[0]

Every edge costs a list scan of up to V entries, so time is O(V·E), which is O(V²) up to a quadratic number of edges. The list stores every node once, so space is O(V). LeetCode caps the graph at 100 nodes, so this would pass there, but with 10^5 nodes it would take around 10^10 steps or more.

From brute force to the idea

  1. Find the waste. nb not in olds and olds.index(nb) both search a list to answer "have I met this node before, and where is its copy?"
  2. One map answers both questions. A dictionary from each original node to its copy tells you whether a node was already copied (it is a key) and gives you the copy directly (the value). Nodes are hashed by identity, so two different nodes with the same value stay separate.
  3. Create on first sight. Start a queue with the given node. When you pop cur and meet a neighbour nb not yet in copies, create its copy and queue it.
  4. Wire every edge. Whether the neighbour is new or old, append its copy to copies[cur].neighbors. Because this line runs for every neighbour of every node, edges back to old nodes are kept.

The key idea: an old-to-new dictionary is both the visited set and the way to find the copy.

The key idea

BFS/DFS with an old→new dictionary so each node is copied once and cycles don’t loop forever. O(V + E).

Python solution

def clone_graph(node):
    if not node:
        return None
    copies = {node: Node(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                q.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(V·E): a list scan for each edgeO(V): the lists of old and new nodes
Dictionary BFS (shown code)O(V + E): each node is created and queued once, each edge is handled onceO(V): the dictionary and queue (the copy itself is also O(V + E))

Edge cases

  • None (empty graph): returns None.
  • One node with no neighbours: returns a new node with an empty list.
  • Self-loop (a node lists itself): the copy lists itself, not the original.
  • Parallel entries (a node lists the same neighbour twice): both entries are copied, and both point to the same copy.
  • Cycles: handled, because a node already in copies is never queued again.
  • Missing class: the shown code assumes Node(val) with a neighbors list and from collections import deque. It uses a queue, so a long chain of nodes causes no recursion error.

Common mistakes

  • Appending the neighbour's copy only inside the if nb not in copies block, which loses every edge that leads back to an already-copied node.
  • Copying neighbours recursively without a map, which loops forever on cycles.
  • Storing copies by value (val -> copy) when values might repeat; the problem has unique values, but identity is the safer key.
  • Returning a node of the original graph by mistake, so the "copy" shares nodes with the input.
Your turn: weighted edges

Each node now has edges, a list of (neighbour, weight) pairs instead of neighbors. Clone the graph so the copy keeps every weight. Describe what changes, then write it if you like.

Compare with our answer

The traversal and the dictionary stay the same. Only the pair unpacking changes, and the weight is copied as is, because a number needs no cloning.

def clone_weighted(node):
    if not node:
        return None
    copies = {node: WNode(node.val)}
    q = deque([node])
    while q:
        cur = q.popleft()
        for nb, w in cur.edges:
            if nb not in copies:
                copies[nb] = WNode(nb.val)
                q.append(nb)
            copies[cur].edges.append((copies[nb], w))
    return copies[node]

Time O(V + E), space O(V) for the map and queue.

A strong answer mentions: reusing the old-to-new dictionary, copying the weight alongside the copied neighbour, and appending the edge for every neighbour, not only new ones.

Check what stuck

1. A linked list has a next pointer and a random pointer that may point to any node in the list, or to None. You must build a deep copy. Which approach fits best?

2. Why does Clone Graph need the dictionary even though a BFS already has a queue?

3. A learner moves copies[cur].neighbors.append(copies[nb]) inside the if nb not in copies: block. Which input is now copied wrongly?

Score 60% or more and the lesson is marked complete.