What is the time complexity of Clone Graph?

The optimal solution has a time complexity of O(V+E).

What data structures are used to solve Clone Graph?

This problem uses Hash Table, Depth-First Search, Breadth-First Search, Graph. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Clone Graph?

Insight 1: We need to avoid infinite loops. Since the graph is undirected, simply traversing the graph will lead to revisiting nodes. We must keep track of the nodes we have already visited. Insight 2: A HashMap (or similar data structure) is crucial to map each original node to its corresponding cloned node. This allows us to efficiently check if a node has already been copied.

Which companies ask LeetCode 133. Clone Graph in interviews?

This problem is frequently asked at Docusign, Flexport, Google, Grammarly, Nutanix and 6 more companies.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Clone Graph - LeetCode 133 Solution

Clone Graph - Complete Solution Guide

Clone Graph is LeetCode problem 133, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 ( List[Node] ) of its neighbors. class Node { public int val; public List<Node> neighbors; } Test case format: For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1 , the second node with val == 2 , and so on. The graph is represented in the test case using an adjacency l

Detailed Explanation

The problem asks us to create a deep copy of a given undirected graph. A deep copy means creating a completely new graph with the same structure and values as the original, such that modifying the copy doesn't affect the original and vice versa. The input is a reference to a node in the original graph (specifically, the node with value 1). Each node has a value and a list of neighbors. The output should be a reference to the corresponding node in the newly created cloned graph. The graph is guaranteed to be connected.

Solution Approach

The provided solution uses Depth-First Search (DFS) to traverse the original graph and create a clone. It uses a HashMap (`old_to_new` in Python, `oldToNew` in Java/C++, `oldToNew` array in C) to store the mapping between the original nodes and their corresponding cloned nodes. The DFS function recursively explores the graph, creating a new node for each original node encountered and adding it to the HashMap. For each neighbor of a node, the DFS function is recursively called to clone the neighbor. The cloned neighbor is then added to the neighbor list of the cloned node.

Step-by-Step Algorithm

Step 1: Check if the input node is null. If so, return null (handles the case of an empty graph).
Step 2: Initialize a HashMap (or array in C) to store the mapping between original nodes and their cloned nodes.
Step 3: Define a recursive DFS function that takes an original node as input.
Step 4: Inside the DFS function, check if the original node is already present in the HashMap. If so, it means we have already created a clone for this node; return the cloned node from the HashMap.
Step 5: If the original node is not in the HashMap, create a new node with the same value as the original node.
Step 6: Add the original node and its newly created clone to the HashMap.
Step 7: Iterate through the neighbors of the original node.
Step 8: For each neighbor, recursively call the DFS function to get the cloned neighbor.
Step 9: Add the cloned neighbor to the neighbor list of the cloned node.
Step 10: Return the cloned node.

Key Insights

Insight 1: We need to avoid infinite loops. Since the graph is undirected, simply traversing the graph will lead to revisiting nodes. We must keep track of the nodes we have already visited.
Insight 2: A HashMap (or similar data structure) is crucial to map each original node to its corresponding cloned node. This allows us to efficiently check if a node has already been copied.
Insight 3: We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and create the clone.

Complexity Analysis

Time Complexity: O(V+E)

Space Complexity: O(V)

Topics

This problem involves: Hash Table, Depth-First Search, Breadth-First Search, Graph.

Companies

Asked at: Docusign, Flexport, Google, Grammarly, Nutanix, Pocket Gems, ThousandEyes, TikTok, Uber, Wix, Yahoo.

Clone Graph | LeetCode 133

Medium

Hash Table Depth-First Search Breadth-First Search Graph

Time: O(V+E)Space: O(V)

Solution Code

Available in:

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

class Solution {
    private HashMap<Node, Node> oldToNew = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        return dfs(node);
    }

    private Node dfs(Node originalNode) {
        if (oldToNew.containsKey(originalNode)) {
            return oldToNew.get(originalNode);
        }

        Node copy = new Node(originalNode.val);
        oldToNew.put(originalNode, copy);
        
        List<Node> neighbors = originalNode.neighbors;
        for (Node neighbor : neighbors) {
            copy.neighbors.add(dfs(neighbor));
        }
        return copy;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 133: Clone Graph - Detailed explanation and solution approaches.

Topics

Hash Table Depth-First Search Breadth-First Search Graph

Companies

DocusignFlexportGoogleGrammarlyNutanixPocket GemsThousandEyesTikTok

Stats

Difficulty:Medium

Languages:4

Companies:11

Problem #:133

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Check if the input node is null. If so, return null (handles the case of an empty graph).
2
Step 2: Initialize a HashMap (or array in C) to store the mapping between original nodes and their cloned nodes.
3
Step 3: Define a recursive DFS function that takes an original node as input.
4
Step 4: Inside the DFS function, check if the original node is already present in the HashMap. If so, it means we have already created a clone for this node; return the cloned node from the HashMap.
5
Step 5: If the original node is not in the HashMap, create a new node with the same value as the original node.
6
Step 6: Add the original node and its newly created clone to the HashMap.
7
Step 7: Iterate through the neighbors of the original node.
8
Step 8: For each neighbor, recursively call the DFS function to get the cloned neighbor.
9
Step 9: Add the cloned neighbor to the neighbor list of the cloned node.
10
Step 10: Return the cloned node.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(V+E)

💾

Space Complexity

O(V)

📝

Why?

The time complexity is O(V+E) as we visit each node and each edge once. The space complexity is O(V) as the HashMap stores the cloned node for each original node and the maximum depth of the recursion call stack can go upto V in worst case, where V is the number of vertices in the graph.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Breadth-First Search (BFS)

Instead of DFS, BFS can also be used to traverse the graph. We can use a queue to store the nodes to be visited. Similar to DFS, we use a HashMap to store the mapping between original and cloned nodes. We start by cloning the input node and adding it to the queue. Then, while the queue is not empty, we dequeue a node, iterate through its neighbors, and clone them if they haven't been cloned yet. Add the cloned neighbor to the queue for further processing.

Time: O(V+E)Space: O(V)

Trade-offs: BFS and DFS have similar time and space complexities. BFS may use more space in some cases if the graph is wide. DFS can lead to stack overflow issues for large graphs, but is usually slightly faster in practice due to the more efficient cache utilization patterns.

✨

Key Insights

1Insight 1: We need to avoid infinite loops. Since the graph is undirected, simply traversing the graph will lead to revisiting nodes. We must keep track of the nodes we have already visited.
2Insight 2: A HashMap (or similar data structure) is crucial to map each original node to its corresponding cloned node. This allows us to efficiently check if a node has already been copied.
3Insight 3: We can use either Depth-First Search (DFS) or Breadth-First Search (BFS) to traverse the graph and create the clone.

📚

Key Terms Explained

For Students

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Graph

Nodes connected by edges. Like a social network or city map!

Edge Cases

Edge case 1: Empty graph (input node is null). The solution handles this case by checking for a null input and returning null immediately.
Edge case 2: Graph with a single node and no neighbors. The solution correctly creates a new node with the same value and an empty neighbor list.
Edge case 3: A graph with self-loops. This is disallowed by the problem constraints (no self-loops).
Edge case 4: A graph with multiple components. This is disallowed by the problem constraints (graph is connected).

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not creating a deep copy. Simply copying the references of the neighbors instead of creating new neighbor nodes results in a shallow copy, where changes to the cloned graph affect the original graph.

✗Common mistake 2: Infinite loop. Forgetting to keep track of visited nodes can lead to infinite loops in undirected graphs, as you'll keep revisiting already processed nodes.

✗Common mistake 3: Not handling the case of an empty graph (null input node).

✗Common mistake 4: Incorrect memory management (especially in C). Failing to allocate memory for the cloned nodes and their neighbors properly.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Social Networks. Cloning a user's network for testing purposes or for creating isolated environments.

🏦Real-world scenario 2: Version Control Systems. Cloning a branch in a version control system to experiment with new features without affecting the main branch.

🎮Real-world scenario 3: Game Development. Cloning game objects or entire game states for saving progress or creating multiple instances of an object.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Hash tables trade space for time. Before using one, consider if the problem constraints allow the extra memory. In interviews, always mention this trade-off.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Don't forget to handle key collisions and null/undefined keys. Consider what happens with duplicate values.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 12, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Clone Graph"?

For this medium-level Hash Table problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?