Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

133. Clone Graph

Time: $O(|V| + |E|)$

Space: $O(|V| + |E|)$

			


class Solution {
 public:
  Node* cloneGraph(Node* node) {
    if (node == nullptr)
      return nullptr;

    queue<Node*> q{{node}};
    unordered_map<Node*, Node*> map{{node, new Node(node->val)}};

    while (!q.empty()) {
      Node* u = q.front();
      q.pop();
      for (Node* v : u->neighbors) {
        if (!map.count(v)) {
          map[v] = new Node(v->val);
          q.push(v);
        }
        map[u]->neighbors.push_back(map[v]);
      }
    }

    return map[node];
  }
};




			


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

    Queue<Node> q = new ArrayDeque<>(Arrays.asList(node));
    Map<Node, Node> map = new HashMap<>();
    map.put(node, new Node(node.val));

    while (!q.isEmpty()) {
      Node u = q.poll();
      for (Node v : u.neighbors) {
        if (!map.containsKey(v)) {
          map.put(v, new Node(v.val));
          q.offer(v);
        }
        map.get(u).neighbors.add(map.get(v));
      }
    }

    return map.get(node);
  }
}




			


class Solution:
  def cloneGraph(self, node: 'Node') -> 'Node':
    if not node:
      return None

    q = deque([node])
    map = {node: Node(node.val)}

    while q:
      u = q.popleft()
      for v in u.neighbors:
        if v not in map:
          map[v] = Node(v.val)
          q.append(v)
        map[u].neighbors.append(map[v])

    return map[node]