beingsde
Sign In
Back to all DSA patterns
Graph / DFS•Pattern: DFS / HashMap•Medium

Clone a graph

Problem Intuition & Objective

Deep copy an undirected connected graph.

Time ComplexityO(V+E)
Optimal
Space ComplexityO(V)
Memory Bounds
Optimal Algorithmic Approach

DFS + HashMap: map acts as both visited set and clone registry.

Core Invariants & Edge Cases

  • Use a HashMap<Node, Node> mapping original → clone
  • DFS/BFS from the start node, creating clones on first visit
  • For each original neighbor, recursively clone and link
Previous ProblemCourse schedule — detect cycle in directed graphNext Problem Rotting oranges — minimum time for all to rot (BFS)

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.