133. Clone Graph

At a Glance

Topic: graphs
Pattern: DFS / Backtracking + hash map
Difficulty: Medium
Companies: Meta, Google, Amazon, Microsoft, Apple
Frequency: High
LeetCode: 133

Problem (one-liner)

Deep-copy an undirected connected graph: each Node has val and neighbors list; return clone of given node.

Core Basics

Opening move: classify the object (interval, multiset, trie node, bitmask, overlapping sub-intervals…) and whether the answer lives in an enumeration, ordering, partition, graph walk, DP table, etc.
Contracts: spell what a valid partial solution looks like at each step—the thing you inductively preserve.
Complexity anchors: state the brute upper bound and the structural fact (sorting, monotonicity, optimal substructure, greedy exchange, hashability) that should beat it.

Understanding

Why brute hurts: name the repeated work or state explosion in one sentence.
Why optimal is safe: the invariant / exchange argument / optimal-subproblem story you would tell a staff engineer.

Memory Hooks

One chant / rule: a single memorable handle (acronym, operator trick, or shape) you can recall under time pressure.

Recognition Cues

Cycle handling — map original → copy
DFS or BFS with lazy neighbor wiring

Study Pattern (SDE3+)

0–3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

BFS queue — clone nodes as discovered — O(V+E).
Optimal — DFS memo map — same complexity, natural recursion.

Optimal Solution

Go

type Node struct {
	Val       int
	Neighbors []*Node
}

func cloneGraph(node *Node) *Node {
	if node == nil {
		return nil
	}
	visited := map[*Node]*Node{}

	var dfs func(source *Node) *Node
	dfs = func(source *Node) *Node {
		if copyNode, ok := visited[source]; ok {
			return copyNode
		}
		clone := &Node{Val: source.Val}
		visited[source] = clone
		for _, neighbor := range source.Neighbors {
			clone.Neighbors = append(clone.Neighbors, dfs(neighbor))
		}
		return clone
	}
	return dfs(node)
}

JavaScript

function cloneGraph(node) {
  if (!node) {
    return null;
  }
  const visited = new Map();

  function dfs(source) {
    if (visited.has(source)) {
      return visited.get(source);
    }
    const copy = { val: source.val, neighbors: [] };
    visited.set(source, copy);
    for (const neighbor of source.neighbors) {
      copy.neighbors.push(dfs(neighbor));
    }
    return copy;
  }

  return dfs(node);
}

Walkthrough

First visit creates clone and maps old→new; neighbor recursion completes edges without duplication.

Invariant: Every original node maps to exactly one clone before adjacency lists finalize.

Edge Cases

Single node no neighbors — clone singleton
Dense graph — map size O(V)

Pitfalls

Shallow copy neighbors array — must recurse per neighbor
Infinite loop without visited

Variants

Clone with weights on edges — copy Node + neighbors + cost.
Directed clone — mark visited per clone pass to avoid infinite loops on cycles.

Mind-Map Tags

#graph #clone #hashmap #dfs #bfs #undirected