133. Clone graph

133_solution1_recursive.c

#include <stdlib.h>

#include "node.h"

#define MAX_VAL 100 // node values are unique and in [1, 100]

static struct Node *dfs(struct Node *node, struct Node **clones) {
  if (!clones[node->val]) {
    struct Node *copy = malloc(sizeof *copy);
    copy->val = node->val;
    copy->numNeighbors = node->numNeighbors;
    copy->neighbors = malloc(node->numNeighbors * sizeof(struct Node *));
    clones[node->val] = copy; // register before recursing to break cycles
    for (int i = 0; i < node->numNeighbors; i++)
      copy->neighbors[i] = dfs(node->neighbors[i], clones);
  }

  return clones[node->val];
}

struct Node *cloneGraph(struct Node *s) {
  if (!s)
    return NULL;

  struct Node *clones[MAX_VAL + 1] = {0};
  return dfs(s, clones);
}

133_solution2_stack.c

#include <stdlib.h>

#include "node.h"

#define MAX_VAL 100 // node values are unique and in [1, 100]

static struct Node *newNode(const struct Node *src) {
  struct Node *copy = malloc(sizeof *copy);
  copy->val = src->val;
  copy->numNeighbors = src->numNeighbors;
  copy->neighbors = malloc(src->numNeighbors * sizeof(struct Node *));
  return copy;
}

struct Node *cloneGraph(struct Node *s) {
  if (!s)
    return NULL;

  struct Node *clones[MAX_VAL + 1] = {0};
  struct Node *pending[MAX_VAL]; // each node is pushed once
  int top = 0;
  clones[s->val] = newNode(s);
  pending[top++] = s;

  while (top > 0) {
    struct Node *cur = pending[--top];
    for (int i = 0; i < cur->numNeighbors; i++) {
      struct Node *nb = cur->neighbors[i];
      if (!clones[nb->val]) {
        clones[nb->val] = newNode(nb);
        pending[top++] = nb;
      }
      clones[cur->val]->neighbors[i] = clones[nb->val];
    }
  }
  return clones[s->val];
}

133_solution3_queue.c

#include <stdlib.h>

#include "node.h"

#define MAX_VAL 100 // node values are unique and in [1, 100]

static struct Node *newNode(const struct Node *src) {
  struct Node *copy = malloc(sizeof *copy);
  copy->val = src->val;
  copy->numNeighbors = src->numNeighbors;
  copy->neighbors = malloc(src->numNeighbors * sizeof(struct Node *));
  return copy;
}

struct Node *cloneGraph(struct Node *s) {
  if (!s)
    return NULL;

  struct Node *clones[MAX_VAL + 1] = {0};
  struct Node *pending[MAX_VAL]; // each node is enqueued once
  int head = 0, tail = 0;
  clones[s->val] = newNode(s);
  pending[tail++] = s;

  while (head < tail) {
    struct Node *cur = pending[head++];
    for (int i = 0; i < cur->numNeighbors; i++) {
      struct Node *nb = cur->neighbors[i];
      if (!clones[nb->val]) {
        clones[nb->val] = newNode(nb);
        pending[tail++] = nb;
      }
      clones[cur->val]->neighbors[i] = clones[nb->val];
    }
  }
  return clones[s->val];
}

node.h

#pragma once

#include <stddef.h>

// Definition for a Node.
struct Node {
  int val;
  int numNeighbors;
  struct Node **neighbors;
};

133_solution1_recursive.cpp

#include <unordered_map>

#include "node.h"

using namespace std;

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

class Solution {
private:
  unordered_map<Node *, Node *> clones;

public:
  Node *cloneGraph(Node *node) {
    if (!node)
      return nullptr;

    if (!clones.count(node)) {
      clones[node] = new Node(node->val);
      for (auto cur : node->neighbors) {
        clones[node]->neighbors.push_back(cloneGraph(cur));
      }
    }

    return clones[node];
  }
};

133_solution2_stack.cpp

#include <stack>
#include <unordered_map>

#include "node.h"

using namespace std;

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

    unordered_map<Node *, Node *> clones;
    stack<Node *> st;
    clones[node] = new Node(node->val);
    st.push(node);

    while (!st.empty()) {
      Node *cur = st.top();
      st.pop();
      for (Node *neighbor : cur->neighbors) {
        if (!clones.count(neighbor)) {
          clones[neighbor] = new Node(neighbor->val);
          st.push(neighbor);
        }
        clones[cur]->neighbors.push_back(clones[neighbor]);
      }
    }
    return clones[node];
  }
};

133_solution3_queue.cpp

#include <queue>
#include <unordered_map>

#include "node.h"

using namespace std;

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

    unordered_map<Node *, Node *> clones;
    queue<Node *> q;
    clones[node] = new Node(node->val);
    q.push(node);

    while (!q.empty()) {
      Node *cur = q.front();
      q.pop();
      for (Node *neighbor : cur->neighbors) {
        if (!clones.count(neighbor)) {
          clones[neighbor] = new Node(neighbor->val);
          q.push(neighbor);
        }
        clones[cur]->neighbors.push_back(clones[neighbor]);
      }
    }
    return clones[node];
  }
};

node.h

#pragma once

#include <vector>

using namespace std;

// Definition for a Node.
class Node {
public:
  int val;
  vector<Node *> neighbors;
  Node() : val(0) {}
  Node(int _val) : val(_val) {}
  Node(int _val, vector<Node *> _neighbors)
      : val(_val), neighbors(_neighbors) {}
};

133_solution1_recursive.go

package graphs

func cloneGraph(node *Node) *Node {
    clones := map[*Node]*Node{}

    var clone func(node *Node) *Node
    clone = func(node *Node) *Node {
        if node == nil {
            return nil
        }

        if _, ok := clones[node]; !ok {
            clones[node] = &Node{Val: node.Val}
            for _, cur := range node.Neighbors {
                clones[node].Neighbors = append(clones[node].Neighbors, clone(cur))
            }
        }

        return clones[node]
    }

    return clone(node)
}

133_solution2_stack.go

package graphs

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    clones := map[*Node]*Node{node: {Val: node.Val}}
    st := []*Node{node}

    for len(st) > 0 {
        cur := st[len(st)-1]
        st = st[:len(st)-1]
        for _, neighbor := range cur.Neighbors {
            if _, ok := clones[neighbor]; !ok {
                clones[neighbor] = &Node{Val: neighbor.Val}
                st = append(st, neighbor)
            }
            clones[cur].Neighbors = append(clones[cur].Neighbors, clones[neighbor])
        }
    }
    return clones[node]
}

133_solution3_queue.go

package graphs

func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    clones := map[*Node]*Node{node: {Val: node.Val}}
    q := []*Node{node}

    for len(q) > 0 {
        cur := q[0]
        q = q[1:]
        for _, neighbor := range cur.Neighbors {
            if _, ok := clones[neighbor]; !ok {
                clones[neighbor] = &Node{Val: neighbor.Val}
                q = append(q, neighbor)
            }
            clones[cur].Neighbors = append(clones[cur].Neighbors, clones[neighbor])
        }
    }
    return clones[node]
}

node.go

package graphs

// Definition for a Node.
type Node struct {
    Val       int
    Neighbors []*Node
}

133_solution1_recursive.java

import java.util.HashMap;
import java.util.Map;

class Solution {
    private final Map<Node, Node> clones = new HashMap<>();

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

        if (!clones.containsKey(node)) {
            clones.put(node, new Node(node.val));
            for (Node cur : node.neighbors) {
                clones.get(node).neighbors.add(cloneGraph(cur));
            }
        }

        return clones.get(node);
    }
}

133_solution2_stack.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

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

        Map<Node, Node> clones = new HashMap<>();
        Deque<Node> st = new ArrayDeque<>();
        clones.put(node, new Node(node.val));
        st.push(node);

        while (!st.isEmpty()) {
            Node cur = st.pop();
            for (Node neighbor : cur.neighbors) {
                if (!clones.containsKey(neighbor)) {
                    clones.put(neighbor, new Node(neighbor.val));
                    st.push(neighbor);
                }
                clones.get(cur).neighbors.add(clones.get(neighbor));
            }
        }
        return clones.get(node);
    }
}

133_solution3_queue.java

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.HashMap;
import java.util.Map;

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

        Map<Node, Node> clones = new HashMap<>();
        Queue<Node> q = new ArrayDeque<>();
        clones.put(node, new Node(node.val));
        q.offer(node);

        while (!q.isEmpty()) {
            Node cur = q.poll();
            for (Node neighbor : cur.neighbors) {
                if (!clones.containsKey(neighbor)) {
                    clones.put(neighbor, new Node(neighbor.val));
                    q.offer(neighbor);
                }
                clones.get(cur).neighbors.add(clones.get(neighbor));
            }
        }
        return clones.get(node);
    }
}

Node.java

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

// 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;
    }
}

133_solution1_recursive.js

const _Node = require("./node");

/**
 * @param {_Node} node
 * @return {_Node}
 */
var cloneGraph = function (node) {
  const clones = new Map();

  const clone = (node) => {
    if (!node) return null;

    if (!clones.has(node)) {
      clones.set(node, new _Node(node.val));
      for (const cur of node.neighbors) {
        clones.get(node).neighbors.push(clone(cur));
      }
    }

    return clones.get(node);
  };

  return clone(node);
};

133_solution2_stack.js

const _Node = require("./node");

/**
 * @param {_Node} node
 * @return {_Node}
 */
var cloneGraph = function (node) {
  if (!node) return null;

  const clones = new Map([[node, new _Node(node.val)]]);
  const st = [node];

  while (st.length > 0) {
    const cur = st.pop();
    for (const neighbor of cur.neighbors) {
      if (!clones.has(neighbor)) {
        clones.set(neighbor, new _Node(neighbor.val));
        st.push(neighbor);
      }
      clones.get(cur).neighbors.push(clones.get(neighbor));
    }
  }
  return clones.get(node);
};

133_solution3_queue.js

const _Node = require("./node");

/**
 * @param {_Node} node
 * @return {_Node}
 */
var cloneGraph = function (node) {
  if (!node) return null;

  const clones = new Map([[node, new _Node(node.val)]]);
  // index-based queue: Array.shift() is O(n)
  const q = [node];

  for (let head = 0; head < q.length; head++) {
    const cur = q[head];
    for (const neighbor of cur.neighbors) {
      if (!clones.has(neighbor)) {
        clones.set(neighbor, new _Node(neighbor.val));
        q.push(neighbor);
      }
      clones.get(cur).neighbors.push(clones.get(neighbor));
    }
  }
  return clones.get(node);
};

node.js

// Definition for a Node.
function _Node(val, neighbors) {
  this.val = val === undefined ? 0 : val;
  this.neighbors = neighbors === undefined ? [] : neighbors;
}

module.exports = _Node;

133_solution1_recursive.py

from typing import Dict, Optional

from node import Node


class Solution:
    def __init__(self) -> None:
        self.clones: Dict[Node, Node] = {}

    def cloneGraph(self, node: Optional[Node]) -> Optional[Node]:
        if not node:
            return None

        if node not in self.clones:
            self.clones[node] = Node(node.val)
            for cur in node.neighbors:
                self.clones[node].neighbors.append(self.cloneGraph(cur))

        return self.clones[node]

133_solution2_stack.py

from typing import Optional

from node import Node


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

        clones = {node: Node(node.val)}
        st = [node]

        while st:
            cur = st.pop()
            for neighbor in cur.neighbors:
                if neighbor not in clones:
                    clones[neighbor] = Node(neighbor.val)
                    st.append(neighbor)
                clones[cur].neighbors.append(clones[neighbor])
        return clones[node]

133_solution3_queue.py

from collections import deque
from typing import Optional

from node import Node


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

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

        while q:
            cur = q.popleft()
            for neighbor in cur.neighbors:
                if neighbor not in clones:
                    clones[neighbor] = Node(neighbor.val)
                    q.append(neighbor)
                clones[cur].neighbors.append(clones[neighbor])
        return clones[node]

node.py

# Definition for a Node.
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

133_solution1_recursive.rs

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

use crate::node::Node;

type NodeRef = Rc<RefCell<Node>>;

impl Solution {
    pub fn clone_graph(node: Option<NodeRef>) -> Option<NodeRef> {
        // keyed by address: Rc identity, not value equality
        let mut clones = HashMap::new();
        node.map(|n| Self::clone(&n, &mut clones))
    }

    fn clone(node: &NodeRef, clones: &mut HashMap<*const RefCell<Node>, NodeRef>) -> NodeRef {
        if let Some(copy) = clones.get(&Rc::as_ptr(node)) {
            return copy.clone();
        }

        let copy = Rc::new(RefCell::new(Node::new(node.borrow().val)));
        clones.insert(Rc::as_ptr(node), copy.clone());
        for cur in node.borrow().neighbors.iter() {
            let neighbor = Self::clone(cur, clones);
            copy.borrow_mut().neighbors.push(neighbor);
        }

        copy
    }
}

133_solution2_stack.rs

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

use crate::node::Node;

type NodeRef = Rc<RefCell<Node>>;

impl Solution {
    pub fn clone_graph(node: Option<NodeRef>) -> Option<NodeRef> {
        let node = node?;

        // keyed by address: Rc identity, not value equality
        let mut clones: HashMap<*const RefCell<Node>, NodeRef> = HashMap::new();
        let root = Rc::new(RefCell::new(Node::new(node.borrow().val)));
        clones.insert(Rc::as_ptr(&node), root.clone());
        let mut st = vec![node.clone()];

        while let Some(cur) = st.pop() {
            for neighbor in cur.borrow().neighbors.iter() {
                let key = Rc::as_ptr(neighbor);
                if !clones.contains_key(&key) {
                    let copy = Rc::new(RefCell::new(Node::new(neighbor.borrow().val)));
                    clones.insert(key, copy);
                    st.push(neighbor.clone());
                }
                let copy = clones[&key].clone();
                clones[&Rc::as_ptr(&cur)].borrow_mut().neighbors.push(copy);
            }
        }
        Some(root)
    }
}

133_solution3_queue.rs

use std::cell::RefCell;
use std::collections::HashMap;
use std::collections::VecDeque;
use std::rc::Rc;

use crate::node::Node;

type NodeRef = Rc<RefCell<Node>>;

impl Solution {
    pub fn clone_graph(node: Option<NodeRef>) -> Option<NodeRef> {
        let node = node?;

        // keyed by address: Rc identity, not value equality
        let mut clones: HashMap<*const RefCell<Node>, NodeRef> = HashMap::new();
        let root = Rc::new(RefCell::new(Node::new(node.borrow().val)));
        clones.insert(Rc::as_ptr(&node), root.clone());
        let mut q = VecDeque::from([node.clone()]);

        while let Some(cur) = q.pop_front() {
            for neighbor in cur.borrow().neighbors.iter() {
                let key = Rc::as_ptr(neighbor);
                if !clones.contains_key(&key) {
                    let copy = Rc::new(RefCell::new(Node::new(neighbor.borrow().val)));
                    clones.insert(key, copy);
                    q.push_back(neighbor.clone());
                }
                let copy = clones[&key].clone();
                clones[&Rc::as_ptr(&cur)].borrow_mut().neighbors.push(copy);
            }
        }
        Some(root)
    }
}

node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a Node (LeetCode has no Rust signature for this problem).
#[derive(Debug)]
pub struct Node {
    pub val: i32,
    pub neighbors: Vec<Rc<RefCell<Node>>>,
}

impl Node {
    #[inline]
    pub fn new(val: i32) -> Self {
        Node {
            val,
            neighbors: Vec::new(),
        }
    }
}