DSA · Graph · #50
Clone Graph
Module 43 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given a reference to a node in a **connected undirected graph**, return a **deep copy** (clone) of the graph. Each node holds an integer `val` and a list `neighbors` of adjacent nodes: ``` function Node(val, neighbors) { this.val = val; this.neighbors = neighbors || []; } ``` Implement `cloneGraph(node)`. The returned graph must contain entirely new `Node` objects that mirror the structure of the input (same `val`, same neighbor connections) but share no object references with it. If the input `node` is `null`, return `null`. Nodes are 1-indexed; the value of each node equals its 1-based index. The given node is always the node with `val === 1`.
Examples
adjList = [[2,4],[1,3],[2,4],[1,3]]→[[2,4],[1,3],[2,4],[1,3]]— A 4-node graph (a square). Node 1 connects to 2 and 4, node 2 to 1 and 3, etc. The clone has identical adjacency.adjList = [[]]→[[]]— A single node with no neighbors.adjList = []→[]— Empty graph: input node is null, so return null.
Constraints
- · The number of nodes is in the range [0, 100].
- · 1 <= Node.val <= 100 and Node.val is unique.
- · There are no repeated edges and no self-loops.
- · The graph is connected and all nodes can be reached from the given node.
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.