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.

Recognition Cues

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

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