The trick here is to name the state correctly, then let the implementation follow. For 133. Clone Graph, the solution in this repository is mainly a graph traversal solution.
Guide
What?
We want to turn the problem statement into a smaller set of decisions the computer can repeat safely. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: graph traversal.
The notes already sitting in the source point us in the right direction:
- BFS
Guide
When?
This pattern shows up when the brute force version has too many repeated checks, too many possible branches, or too much bookkeeping to do by hand. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The solution is organized around the main LeetCode entry point and a few local helpers.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- A map keeps the lookup side cheap; the code pays a little memory to avoid repeated searching.
- The queue gives the solution a level-by-level or frontier-style traversal.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Read the setup variables first.
- Follow the main loop or recursive helper next.
- Watch where invalid states get skipped.
- Check which value survives to the return statement.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
01//BFS
02//Runtime: 12 ms, faster than 64.56% of C++ online submissions for Clone Graph.
03//Memory Usage: 8.9 MB, less than 98.02% of C++ online submissions for Clone Graph.
04/*
05// Definition for a Node.
06class Node {
07public:
08 int val;
09 vector<Node*> neighbors;
10
11 Node() {
12 val = 0;
13 neighbors = vector<Node*>();
14 }
15
16 Node(int _val) {
17 val = _val;
18 neighbors = vector<Node*>();
19 }
20
21 Node(int _val, vector<Node*> _neighbors) {
22 val = _val;
23 neighbors = _neighbors;
24 }
25};
26*/
27
28class Solution {
29public:
30 Node* cloneGraph(Node* node) {
31 if(!node) return node;
32
33 queue<Node*> q;
34 unordered_map<int, vector<int>> adjList;
35
36 q.push(node);
37 //mark "node" as existing in graph
38 //also mark it as visited!
39 adjList[node->val] = {};
40
41 while(!q.empty()){
42 Node* cur = q.front(); q.pop();
43 // cout << "visit " << cur->val << endl;
44
45 for(Node* nei : cur->neighbors){
46 //here we actually build the graph
47 adjList[cur->val].push_back(nei->val);
48 if(adjList.find(nei->val) != adjList.end()) continue;
49 //mark nei as visited!
50 adjList[nei->val] = {};
51 q.push(nei);
52 }
53 }
54
55 int count = adjList.size();
56
57 // cout << "count: " << count << endl;
58
59 //dummy node
60 vector<Node*> newnodes = {new Node(0)};
61
62 for(int i = 1; i <= count; ++i){
63 newnodes.push_back(new Node(i));
64 }
65
66 for(int i = 1; i <= count; ++i){
67 for(const int& nei : adjList[i]){
68 // cout << i << " -> " << nei << endl;
69 newnodes[i]->neighbors.push_back(newnodes[nei]);
70 }
71 }
72
73 return newnodes[1];
74 }
75};
76
77//BFS, one pass
78//https://leetcode.com/problems/clone-graph/discuss/42313/C%2B%2B-BFSDFS
79//Runtime: 8 ms, faster than 96.13% of C++ online submissions for Clone Graph.
80//Memory Usage: 8.5 MB, less than 98.02% of C++ online submissions for Clone Graph.
81class Solution {
82public:
83 Node* cloneGraph(Node* node) {
84 if(!node) return node;
85
86 unordered_map<Node*, Node*> old2new;
87
88 old2new[node] = new Node(node->val);
89
90 queue<Node*> q;
91
92 //visit the old graph
93 q.push(node);
94
95 while(!q.empty()){
96 Node* cur = q.front(); q.pop();
97
98 for(Node* nei : cur->neighbors){
99 if(old2new.find(nei) != old2new.end()){
100 //create the edge
101 old2new[cur]->neighbors.push_back(old2new[nei]);
102 continue;
103 }
104 old2new[nei] = new Node(nei->val);
105 //visit the old graph
106 q.push(nei);
107 //create the edge
108 old2new[cur]->neighbors.push_back(old2new[nei]);
109 }
110 }
111
112 return old2new[node];
113 }
114};
115
116//DFS
117//https://leetcode.com/problems/clone-graph/discuss/42313/C%2B%2B-BFSDFS
118//Runtime: 8 ms, faster than 96.13% of C++ online submissions for Clone Graph.
119//Memory Usage: 9 MB, less than 98.02% of C++ online submissions for Clone Graph.
120class Solution {
121public:
122 unordered_map<Node*, Node*> old2new;
123
124 Node* cloneGraph(Node* node) {
125 if(!node) return node;
126
127 //this node is already visited
128 if(old2new.find(node) != old2new.end())
129 return old2new[node];
130
131 old2new[node] = new Node(node->val);
132
133 for(Node* nei : node->neighbors){
134 //build new node for "nei" and then connect them together
135 old2new[node]->neighbors.push_back(cloneGraph(nei));
136 }
137
138 return old2new[node];
139 }
140};Cost