Clone Graph

📋

Problem

Imagine you have a social network graph representing friendships, and you want to create an exact copy of this network to simulate new features without affecting the original.

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a value (int) and a list of its neighbors. The graph is represented using adjacency lists. The cloned graph should have the same structure and node values as the original graph.

The number of nodes in the graph is in the range [0, 100].1 <= Node.val <= 100Node.val is unique for each node.The graph is connected and undirected.

Edge cases: Empty graph (null input) → return nullGraph with a single node and no neighbors → clone node with empty neighbors listGraph with a cycle → cloned graph must preserve cycle without infinite loop

</>

IDE

def cloneGraph(node: 'Node') -> 'Node':public Node cloneGraph(Node node)Node* cloneGraph(Node* node)function cloneGraph(node)

def cloneGraph(node):
    # Write your solution here
    pass

class Solution {
    public Node cloneGraph(Node node) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

Node* cloneGraph(Node* node) {
    // Write your solution here
    return nullptr;
}

function cloneGraph(node) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Stack overflow or infinite recursionMissing visited map causing infinite recursion on cyclic graphs.✅ Add a hash map to store cloned nodes and check before recursive calls to avoid revisiting.

Wrong: Incorrect neighbor lists or missing neighborsNeighbors not assigned correctly from cloned nodes, or neighbors list not copied properly.✅ Assign neighbors by looking up clones in the visited map instead of creating new nodes each time.

Wrong: Returns non-null for null inputNo base case for null input node.✅ Add base case: if input node is null, return null immediately.

Wrong: Duplicates in neighbors lostUsing sets or filtering neighbors during cloning.✅ Clone neighbors list exactly as given without removing duplicates.

Wrong: Clones nodes outside reachable componentAssuming input graph is disconnected and cloning all nodes instead of reachable ones.✅ Clone only nodes reachable from input node using BFS/DFS traversal.

✓

Test Cases

Handle base cases like empty graph and single node before tackling cycles.

Use memoization to handle cycles and avoid infinite recursion.

Optimize your solution to linear time complexity using BFS or DFS with a visited map.

t1_01basic

Input{"adjList":[[2,4],[1,3],[2,4],[1,3]]}

Expected[[2,4],[1,3],[2,4],[1,3]]

⏱ Performance - must finish in 2000ms

The graph has 4 nodes. Node 1 is connected to nodes 2 and 4, node 2 to nodes 1 and 3, and so on. The output is a deep copy with the same adjacency structure.

💡 Think about traversing the graph to copy nodes and edges.

💡 Use DFS or BFS with a hash map to track visited nodes and avoid cycles.

💡 Create a new node for each original node and link neighbors using the map.

Why it failed: Failed to clone graph correctly: likely missing visited map causing infinite recursion or incorrect neighbor links. Fix by using a hash map to store cloned nodes and reuse them.

✓ Correctly cloned the graph preserving structure and node values.

t1_02basic

Input{"adjList":[[2],[1,3,4],[2,4],[2,3]]}

Expected[[2],[1,3,4],[2,4],[2,3]]

⏱ Performance - must finish in 2000ms

Graph with 4 nodes: node 1 connected to 2; node 2 connected to 1,3,4; node 3 connected to 2,4; node 4 connected to 2,3. Output is a deep copy with identical adjacency.

💡 Traverse all nodes starting from the given node to clone.

💡 Maintain a map from original nodes to cloned nodes to avoid duplicates.

💡 Assign neighbors by looking up clones in the map instead of creating new nodes.

Why it failed: Incorrect neighbor assignment or missing visited map causing duplicate nodes or infinite recursion. Fix by storing clones in a map and reusing them for neighbors.

✓ Successfully cloned graph with correct neighbor references.

t2_01edge

Input{"adjList":[]}

Expectednull

⏱ Performance - must finish in 2000ms

Empty graph input (null) should return null as there is no node to clone.

💡 Check if the input node is null before processing.

💡 Return null immediately if input is null to handle empty graph.

💡 Add a base case: if node is None, return None.

Why it failed: Function crashes or returns non-null on null input. Fix by adding a base case to return null if input node is null.

✓ Correctly returns null for empty graph input.

t2_02edge

Input{"adjList":[[]]}

Expected[[]]

⏱ Performance - must finish in 2000ms

Graph with a single node and no neighbors should clone node with empty neighbors list.

💡 Handle single node graphs by cloning the node and assigning empty neighbors.

💡 Ensure neighbors list is copied as empty, not null or undefined.

💡 Return a new node with the same value and empty neighbors list.

Why it failed: Neighbors list missing or incorrectly assigned for single node. Fix by initializing neighbors as empty list for nodes with no neighbors.

✓ Successfully cloned single node graph with empty neighbors.

t2_03edge

Input{"adjList":[[2],[1]]}

Expected[[2],[1]]

⏱ Performance - must finish in 2000ms

Graph with two nodes connected to each other (cycle of length 2). Clone must preserve cycle without infinite recursion.

💡 Detect cycles by tracking visited nodes during traversal.

💡 Use a hash map to avoid revisiting and recloning nodes.

💡 Return existing clone from map if node already cloned to prevent infinite recursion.

Why it failed: Infinite recursion or stack overflow due to missing visited map for cycle detection. Fix by using a map to track cloned nodes and return existing clones.

✓ Correctly cloned graph with cycle preserving structure without infinite recursion.

t3_01corner

Input{"adjList":[[2,3],[1,3],[1,2]]}

Expected[[2,3],[1,3],[1,2]]

⏱ Performance - must finish in 2000ms

Triangle cycle graph with 3 nodes all connected to each other. Tests if cloning handles cycles correctly without infinite loops.

💡 Check if your visited map is used before recursive calls to avoid infinite loops.

💡 Ensure that neighbors are assigned from the map of cloned nodes, not recreated each time.

💡 Use memoization to return existing clones when revisiting nodes in cycles.

Why it failed: Infinite recursion or duplicated nodes due to missing or incorrect memoization of cloned nodes. Fix by checking visited map before cloning neighbors.

✓ Correctly clones cyclic graph with proper memoization.

t3_02corner

Input{"adjList":[[2],[1],[4],[3]]}

Expected[[2],[1],[4],[3]]

⏱ Performance - must finish in 2000ms

Graph with two disconnected components (1-2 and 3-4). Although problem states connected graph, test ensures function handles multiple components if input given.

💡 Verify that traversal covers all reachable nodes from input node.

💡 If input node is in one component, only clone that component.

💡 Ensure no assumptions that all nodes are reachable from input node.

Why it failed: Function attempts to clone unreachable nodes or crashes on disconnected input. Fix by cloning only reachable nodes from input node using BFS/DFS.

✓ Correctly clones only reachable component from input node.

t3_03corner

Input{"adjList":[[2,2],[1]]}

Expected[[2,2],[1]]

⏱ Performance - must finish in 2000ms

Graph with duplicate neighbors in adjacency list (node 1 connected twice to node 2). Clone must preserve duplicates exactly.

💡 Do not remove duplicates when cloning neighbors; preserve adjacency list as is.

💡 Clone neighbors list by iterating original neighbors without filtering.

💡 Ensure cloned neighbors list length matches original neighbors list length.

Why it failed: Duplicates in neighbors lost due to using sets or filtering. Fix by cloning neighbors list exactly as given without removing duplicates.

✓ Successfully cloned graph preserving duplicate neighbors.

t4_01performance

Input{"_description":"n=100 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Graph with 100 nodes at constraint boundary. Algorithm must run in O(V+E) time to complete within 2 seconds.

💡 Use DFS or BFS with a hash map to avoid revisiting nodes.

💡 Avoid exponential recursion by memoizing cloned nodes.

💡 Ensure linear time complexity O(V+E) by visiting each node and edge once.

Why it failed: TLE due to exponential recursion without memoization or visited map. Fix by using a hash map to track cloned nodes and avoid revisiting.

✓ Algorithm runs in O(V+E) time and completes within time limit.

Practice

1. Consider the following Python code for checking if a graph is a valid tree. What is the return value when calling valid_tree(4, [[0,1],[1,2],[2,3]])?

easy

A. true

B. false

C. Raises an exception

D. Returns null

Solution

1. Step 1: Check edge count

   Edges count is 3, nodes count is 4, so edges == n-1 condition passes.

2. Step 2: BFS traversal and cycle detection

   Starting from node 0, BFS visits nodes 0,1,2,3 without revisiting any node or detecting cycles. All nodes are visited.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Graph is connected and acyclic, so valid tree [OK]

Hint: Edges must be n-1 and BFS visits all nodes [OK]

Common Mistakes:

• Confusing cycle detection with revisiting parent
• Forgetting to check all nodes visited

2. You are given an undirected graph and need to determine if its vertices can be divided into two groups such that no edge connects vertices within the same group. Which algorithmic approach guarantees an efficient and correct solution for this problem?

easy

A. Greedy algorithm that assigns groups based on vertex degree

B. Dynamic Programming on subsets of vertices to find valid partitions

C. Depth-First Search (DFS) to find cycles and count their lengths

D. Breadth-First Search (BFS) coloring to assign two colors and check for conflicts

Solution

1. Step 1: Understand the problem as a 2-coloring challenge

   The problem requires checking if the graph is bipartite, which means it can be colored using two colors such that no adjacent vertices share the same color.

2. Step 2: Identify BFS coloring as the optimal approach

   BFS coloring systematically assigns colors level by level and detects conflicts efficiently, guaranteeing correctness and linear time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   BFS coloring is the standard method for bipartite checking [OK]

Hint: BFS coloring detects bipartite conflicts efficiently [OK]

Common Mistakes:

• Assuming greedy degree-based grouping works
• Confusing cycle detection with bipartite check

3. The following code attempts to count connected components using BFS. Which line contains a subtle bug that can cause incorrect results or infinite loops?

medium

A. Line 5: graph[u].append(v)

B. Line 11: visited.add(i)

C. Line 15: queue.append(neighbor)

D. Line 6: # graph[v].append(u) # missing reverse edge

Solution

1. Step 1: Identify graph construction lines

   Line 5 adds edge u->v, but line 6 (reverse edge) is commented out, making graph directed.

2. Step 2: Understand impact of missing reverse edge

   Without reverse edges, BFS misses connections, causing undercount or infinite loops if graph is assumed undirected.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Undirected graph requires edges both ways [OK]

Hint: Undirected graphs need edges in both directions [OK]

Common Mistakes:

• Forgetting to add reverse edges
• Marking visited too late causing duplicates

4. Suppose the 01 Matrix problem is modified so that cells can have negative values, and the distance to the nearest zero must consider only paths through non-negative cells. Which approach correctly adapts to this constraint?

hard

A. Use the original two-pass DP ignoring negative values since distances depend only on zeros.

B. Apply DFS from each 1 to find nearest zero avoiding negative cells, as BFS cannot handle constraints.

C. Use brute force checking all paths from each 1 to zero, filtering out negative cells.

D. Run a multi-source BFS starting from zeros but skip neighbors with negative values during traversal.

Solution

1. Step 1: Understand the constraint

   Paths must avoid negative cells, so traversal must skip them.

2. Step 2: Choose correct algorithm

   Multi-source BFS can be adapted to skip negative neighbors, ensuring shortest valid paths.

3. Step 3: Why others fail

   Two-pass DP assumes uniform movement cost and no obstacles; DFS does not guarantee shortest path; brute force is inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Modified BFS handles constraints and shortest paths correctly [OK]

Hint: BFS can be adapted to skip invalid neighbors for constrained shortest paths [OK]

Common Mistakes:

• Assuming DP works with obstacles
• Using DFS for shortest path
• Brute force is too slow

5. Suppose the problem is modified so that water can flow uphill by at most 1 unit of height difference (i.e., from a cell to a neighbor if neighbor's height ≥ current height - 1). Which modification to the BFS approach correctly handles this variant?

hard

A. Change the BFS condition to allow neighbor heights >= current height - 1 and keep the rest unchanged.

B. No change needed; original BFS condition already covers uphill flow.

C. Run BFS from each cell individually to check uphill flow possibility.

D. Use a priority queue BFS (Dijkstra) to handle varying height constraints efficiently.

Solution

1. Step 1: Understand uphill flow constraint

   Allowing uphill flow by 1 unit means edges have weights or costs, not uniform.

2. Step 2: BFS is insufficient

   Standard BFS assumes uniform edge cost; to handle varying constraints, Dijkstra's algorithm with a priority queue is needed.

3. Step 3: Modify algorithm

   Use priority queue BFS (Dijkstra) to explore cells with minimal cost respecting height difference constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Uphill flow requires weighted graph traversal -> Dijkstra [OK]

Hint: Uphill flow needs weighted BFS -> Dijkstra [OK]

Common Mistakes:

• Trying to fix with simple BFS condition change
• Running BFS from every cell causes TLE