The problem in question

I'm given a node that is part of a closed graph - so it ultimately loops back around to the starting node - and I'm tasked with creating a copy of the full graph. So I need to recreate each node and piece them back together in the same orientation.

This one is interesting. I spent a decent amount of time trying to figure out how to even begin, as I'm not not used using classes in TypeScript, and console logging in the Leetcode playground didn't yeild much clarity. If I received this problem in an interview setting, I have no doubt my interviewer would be able to help me over this hump and onto the meat of the problem.

So I start by making a copy of the original node. Then I create a hash to map the original node id to the new node. From there, I can do the same with the neighbors. I'll do a depth first search, meaning I'll start with the first neighbor in the array and perform this mapping and get its neighbors and continue along this process until the first neighbor is a node I've already found. Since each node has 2 neighbors, once I've moved off of the initial node, each node will by default have a neighbor I've already visited - the one I just came from.

Coding the Solution -

While the following solution technically worked, it's in the 16th percentile for runtime and 6th percentile for space complexity on leetcode, so I've got quite the opportunity for enhancement.

/**
 * Definition for _Node.
 * class _Node {
 *     val: number
 *     neighbors: _Node[]
 * 
 *     constructor(val?: number, neighbors?: _Node[]) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.neighbors = (neighbors===undefined ? [] : neighbors)
 *     }
 * }
 * 
 */


function cloneGraph(node: _Node | null): _Node | null {
    if(!node?.val){
        return null
    }

    const foundNodes : Record<number, {old: _Node, new: _Node}> = {};
    foundNodes[node.val] = { new: new _Node(node.val), old: node };

    const stack : _Node[] = [...node.neighbors];

    while(stack.length && stack[0]?.val){
        const {val, neighbors} = stack[0];
        const newNode = new _Node(val);
        foundNodes[val] = {new: new _Node(val), old: stack[0]};
        neighbors.forEach(neighbor => {
            if(!foundNodes[neighbor.val]){
                stack.push(neighbor)
            }
        })
        stack.shift();
    }

    const result : _Node[] = []

    Object.keys(foundNodes).forEach(nodeId => {
        const oldAndNewNode = foundNodes[nodeId];
        const newNeighbors = oldAndNewNode.old?.neighbors.map(neighbor => foundNodes[neighbor.val]?.new).filter(neighbor => !!neighbor);

        const newNode = oldAndNewNode.new;
        newNode.neighbors = newNeighbors
    })

    return foundNodes[node.val].new
};

I passed my algorithm to Claude 4.5 Sonnet, and here's what it said -

• Incorrect null check: if(!node?.val) will fail for a valid node with value 0. Should be if(!node) or if(node === null).

• Missing connection logic: You're not connecting the starting node's neighbors properly during the traversal phase.

• Redundant node creation: You create newNode twice for each node - once in the while loop and once when initializing foundNodes[val].

I think the main issue with time complexity is the second bullet, and the main issue with space complexity is the third. My algorithm creates all the nodes and then goes back through them to wire up the new neighbors.

The following Claude generated algorithm solves my problems, and is in the 96% for runtime.

Outside of being generally cleaner, the biggest difference in runtime is that it progressively adds neighbors as it's cloning the nodes, instead of going back through for a second time, giving it an O(N) runtime.

function cloneGraph(node: _Node | null): _Node | null {
    if (!node) {
        return null;
    }

    const clonedNodes: Record<number, _Node> = {};
    const queue: _Node[] = [node];
    
    // Create the first cloned node
    clonedNodes[node.val] = new _Node(node.val);

    while (queue.length > 0) {
        const current = queue.shift()!;
        
        // Process each neighbor
        for (const neighbor of current.neighbors) {
            // If we haven't cloned this neighbor yet, create it and add to queue
            if (!clonedNodes[neighbor.val]) {
                clonedNodes[neighbor.val] = new _Node(neighbor.val);
                queue.push(neighbor);
            }
            
            // Add the cloned neighbor to the current cloned node's neighbors
            clonedNodes[current.val].neighbors.push(clonedNodes[neighbor.val]);
        }
    }

    return clonedNodes[node.val];
}

Final thoughts

• Node traversal is definitely a muscle I need to work more. I expected this to be easier than it was. This problem almost got me break down at pay for Leetcode pro so I could use the debugger, as much of my problems would have been solved through initial visibility.

• My solution was a breadth-first-search solution. Depth-first search would have also worked, which would have used recursion.