Copy List with Random Pointer

🎯

Copy List with Random Pointer

mediumDESIGNAmazonMicrosoftGoogle

Imagine you have a complex linked list where each node not only points to the next node but also to any random node in the list. You want to create a completely independent copy of this structure without mixing the original and the copy.

💡 This problem is about creating a deep copy of a complex linked list where each node has an additional random pointer. Beginners often struggle because the random pointers can point anywhere, making a simple traversal insufficient. Understanding how to preserve these arbitrary connections is key.

📋

Problem Statement

Given a linked list where each node contains an additional random pointer which could point to any node in the list or null, return a deep copy of the list. The deep copy should have exactly the same structure and values, but all nodes should be new instances.

1 ≤ n ≤ 10^5Node values can be any integerRandom pointer can be null or point to any node in the list

💡

Example

Input"head = [[7,null],[13,0],[11,4],[10,2],[1,0]]"

Output[[7,null],[13,0],[11,4],[10,2],[1,0]]

The list has 5 nodes. Each node's random pointer points to the index given (or null). The output is a deep copy with the same structure and random pointers.

• Empty list → return null
• List with one node, random pointer points to itself → copy should replicate this
• Random pointers all null → copy should have all random pointers null
• Random pointers forming cycles → copy should replicate cycles without infinite loops

⚠️

Common Mistakes

Not handling null random pointers

Leads to null pointer exceptions or incorrect assignments

✅ Always check if random pointer is null before accessing

Mixing original and copied nodes after weaving

Original list structure is corrupted or copied list is incorrect

✅ Carefully restore original list's next pointers when separating lists

Not using memoization in recursive approach

Infinite recursion or duplicate nodes created

✅ Use a map to cache copied nodes and avoid repeated work

Returning original head instead of copied head

Output is the original list, not the copy

✅ Return the copied head node stored or created during copying

🧠

Brute Force (Using Hash Map for Node Mapping)

💡 This approach uses extra space to map original nodes to their copies. It is straightforward and helps beginners understand the problem by separating node creation and pointer assignment.

Intuition

Create a new node for each original node and store the mapping. Then assign next and random pointers for the copied nodes using this map.

Algorithm

1. Traverse the original list and create a copy of each node, storing the mapping from original to copy in a hash map.
2. Traverse the original list again to assign next and random pointers for each copied node using the hash map.
3. Return the copied node corresponding to the original head.

💡 Separating node creation and pointer assignment makes it easier to understand and debug.

</>

Code

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    if not head:
        return None
    old_to_new = {}
    curr = head
    while curr:
        old_to_new[curr] = Node(curr.val)
        curr = curr.next
    curr = head
    while curr:
        old_to_new[curr].next = old_to_new.get(curr.next)
        old_to_new[curr].random = old_to_new.get(curr.random)
        curr = curr.next
    return old_to_new[head]

# Driver code to test
if __name__ == '__main__':
    # Create list: 7->13->11->10->1 with random pointers
    nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
    nodes[0].next = nodes[1]
    nodes[1].next = nodes[2]
    nodes[2].next = nodes[3]
    nodes[3].next = nodes[4]
    nodes[1].random = nodes[0]
    nodes[2].random = nodes[4]
    nodes[3].random = nodes[2]
    nodes[4].random = nodes[0]
    copied_head = copyRandomList(nodes[0])
    print(copied_head.val)  # Should print 7

Line Notes

class Node:Defines the node structure with val, next, and random pointers

old_to_new = {}Creates a dictionary to map original nodes to their copies

while curr:First pass to create all new nodes without setting pointers

old_to_new[curr] = Node(curr.val)Creates a new node for each original node

old_to_new[curr].next = old_to_new.get(curr.next)Assigns the next pointer for the copied node using the map

old_to_new[curr].random = old_to_new.get(curr.random)Assigns the random pointer for the copied node using the map

return old_to_new[head]Returns the head of the copied list

import java.util.HashMap;
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        HashMap<Node, Node> map = new HashMap<>();
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }
        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }

    // Driver code
    public static void main(String[] args) {
        Node[] nodes = new Node[5];
        nodes[0] = new Node(7);
        nodes[1] = new Node(13);
        nodes[2] = new Node(11);
        nodes[3] = new Node(10);
        nodes[4] = new Node(1);
        nodes[0].next = nodes[1];
        nodes[1].next = nodes[2];
        nodes[2].next = nodes[3];
        nodes[3].next = nodes[4];
        nodes[1].random = nodes[0];
        nodes[2].random = nodes[4];
        nodes[3].random = nodes[2];
        nodes[4].random = nodes[0];
        Solution sol = new Solution();
        Node copiedHead = sol.copyRandomList(nodes[0]);
        System.out.println(copiedHead.val); // Should print 7
    }
}

Line Notes

import java.util.HashMap;Imports HashMap for mapping original to copied nodes

HashMap<Node, Node> map = new HashMap<>();Stores mapping from original to copied nodes

while (curr != null)First pass to create new nodes

map.put(curr, new Node(curr.val));Creates a copy of the current node

map.get(curr).next = map.get(curr.next);Assigns next pointer for copied node

map.get(curr).random = map.get(curr.random);Assigns random pointer for copied node

return map.get(head);Returns the copied list's head

#include <iostream>
#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        unordered_map<Node*, Node*> map;
        Node* curr = head;
        while (curr) {
            map[curr] = new Node(curr->val);
            curr = curr->next;
        }
        curr = head;
        while (curr) {
            map[curr]->next = map[curr->next];
            map[curr]->random = map[curr->random];
            curr = curr->next;
        }
        return map[head];
    }
};

// Driver code
int main() {
    Node* nodes[5] = {new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)};
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];
    nodes[1]->random = nodes[0];
    nodes[2]->random = nodes[4];
    nodes[3]->random = nodes[2];
    nodes[4]->random = nodes[0];
    Solution sol;
    Node* copiedHead = sol.copyRandomList(nodes[0]);
    cout << copiedHead->val << endl; // Should print 7
    return 0;
}

Line Notes

#include <unordered_map>Includes unordered_map for mapping original to copied nodes

unordered_map<Node*, Node*> map;Maps original nodes to their copies

while (curr) {First pass to create new nodes

map[curr] = new Node(curr->val);Creates a new node copy

map[curr]->next = map[curr->next];Assigns next pointer for copied node

map[curr]->random = map[curr->random];Assigns random pointer for copied node

return map[head];Returns the head of the copied list

function Node(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function(head) {
    if (!head) return null;
    const map = new Map();
    let curr = head;
    while (curr) {
        map.set(curr, new Node(curr.val));
        curr = curr.next;
    }
    curr = head;
    while (curr) {
        map.get(curr).next = map.get(curr.next) || null;
        map.get(curr).random = map.get(curr.random) || null;
        curr = curr.next;
    }
    return map.get(head);
};

// Driver code
const nodes = [new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)];
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[1].random = nodes[0];
nodes[2].random = nodes[4];
nodes[3].random = nodes[2];
nodes[4].random = nodes[0];
const copiedHead = copyRandomList(nodes[0]);
console.log(copiedHead.val); // Should print 7

Line Notes

function Node(val, next = null, random = null) {Defines the node structure with val, next, and random pointers

const map = new Map();Stores mapping from original nodes to copied nodes

while (curr) {First pass to create copies of nodes

map.set(curr, new Node(curr.val));Creates a new node copy

map.get(curr).next = map.get(curr.next) || null;Assigns next pointer for copied node

map.get(curr).random = map.get(curr.random) || null;Assigns random pointer for copied node

return map.get(head);Returns the copied list's head

⏱

Complexity

TimeO(n)

SpaceO(n)

We traverse the list twice, each O(n). The hash map stores n nodes, so O(n) space.

💡 For n=100,000 nodes, this means about 200,000 operations plus memory for 100,000 node mappings.

Interview Verdict: Accepted

This approach is accepted but uses extra space. It is a good starting point to understand the problem.

🧠

Optimal Approach (Weaving Nodes Without Extra Hash Map)

💡 This approach cleverly weaves copied nodes into the original list to avoid extra space. It is more complex but optimal in space, teaching how to manipulate pointers carefully.

Intuition

Insert copied nodes right after original nodes, then assign random pointers by using the next pointers, and finally separate the two lists.

Algorithm

1. Traverse the original list and insert a copied node after each original node.
2. Traverse the new list and assign random pointers for copied nodes using original nodes' random pointers.
3. Separate the original and copied nodes to form two independent lists.
4. Return the head of the copied list.

💡 This approach requires careful pointer manipulation but saves space by avoiding a hash map.

</>

Code

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    if not head:
        return None
    curr = head
    # Step 1: Insert copied nodes
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next
    # Step 3: Separate lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next
    return copy_head

# Driver code
if __name__ == '__main__':
    nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
    nodes[0].next = nodes[1]
    nodes[1].next = nodes[2]
    nodes[2].next = nodes[3]
    nodes[3].next = nodes[4]
    nodes[1].random = nodes[0]
    nodes[2].random = nodes[4]
    nodes[3].random = nodes[2]
    nodes[4].random = nodes[0]
    copied_head = copyRandomList(nodes[0])
    print(copied_head.val)  # Should print 7

Line Notes

while curr:First pass to weave copied nodes after originals

new_node = Node(curr.val, curr.next)Creates a copy node pointing to original's next

curr.next = new_nodeInserts copy node after original

if curr.random:Assigns random pointer for copied node using original's random

curr.next.random = curr.random.nextCopied node's random points to copied random node

curr.next = curr.next.nextRestores original list's next pointers during separation

copy_curr.next = copy_curr.next.nextBuilds copied list's next pointers during separation

class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        Node curr = head;
        // Step 1: Insert copied nodes
        while (curr != null) {
            Node newNode = new Node(curr.val);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }
        // Step 2: Assign random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        // Step 3: Separate lists
        curr = head;
        Node copyHead = head.next;
        Node copyCurr = copyHead;
        while (curr != null) {
            curr.next = curr.next.next;
            if (copyCurr.next != null) {
                copyCurr.next = copyCurr.next.next;
            }
            curr = curr.next;
            copyCurr = copyCurr.next;
        }
        return copyHead;
    }

    // Driver code
    public static void main(String[] args) {
        Node[] nodes = new Node[5];
        nodes[0] = new Node(7);
        nodes[1] = new Node(13);
        nodes[2] = new Node(11);
        nodes[3] = new Node(10);
        nodes[4] = new Node(1);
        nodes[0].next = nodes[1];
        nodes[1].next = nodes[2];
        nodes[2].next = nodes[3];
        nodes[3].next = nodes[4];
        nodes[1].random = nodes[0];
        nodes[2].random = nodes[4];
        nodes[3].random = nodes[2];
        nodes[4].random = nodes[0];
        Solution sol = new Solution();
        Node copiedHead = sol.copyRandomList(nodes[0]);
        System.out.println(copiedHead.val); // Should print 7
    }
}

Line Notes

while (curr != null)First pass to weave copied nodes after originals

Node newNode = new Node(curr.val);Creates a copy node

curr.next = newNode;Inserts copy node after original

if (curr.random != null)Assigns random pointer for copied node

curr.next.random = curr.random.next;Copied node's random points to copied random node

curr.next = curr.next.next;Restores original list's next pointers during separation

copyCurr.next = copyCurr.next.next;Builds copied list's next pointers during separation

#include <iostream>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        Node* curr = head;
        // Step 1: Insert copied nodes
        while (curr) {
            Node* newNode = new Node(curr->val);
            newNode->next = curr->next;
            curr->next = newNode;
            curr = newNode->next;
        }
        // Step 2: Assign random pointers
        curr = head;
        while (curr) {
            if (curr->random) {
                curr->next->random = curr->random->next;
            }
            curr = curr->next->next;
        }
        // Step 3: Separate lists
        curr = head;
        Node* copyHead = head->next;
        Node* copyCurr = copyHead;
        while (curr) {
            curr->next = curr->next->next;
            if (copyCurr->next) {
                copyCurr->next = copyCurr->next->next;
            }
            curr = curr->next;
            copyCurr = copyCurr->next;
        }
        return copyHead;
    }
};

// Driver code
int main() {
    Node* nodes[5] = {new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)};
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];
    nodes[1]->random = nodes[0];
    nodes[2]->random = nodes[4];
    nodes[3]->random = nodes[2];
    nodes[4]->random = nodes[0];
    Solution sol;
    Node* copiedHead = sol.copyRandomList(nodes[0]);
    cout << copiedHead->val << endl; // Should print 7
    return 0;
}

Line Notes

while (curr) {First pass to weave copied nodes after originals

Node* newNode = new Node(curr->val);Creates a copy node

curr->next = newNode;Inserts copy node after original

if (curr->random) {Assigns random pointer for copied node

curr->next->random = curr->random->next;Copied node's random points to copied random node

curr->next = curr->next->next;Restores original list's next pointers during separation

copyCurr->next = copyCurr->next->next;Builds copied list's next pointers during separation

function Node(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function(head) {
    if (!head) return null;
    let curr = head;
    // Step 1: Insert copied nodes
    while (curr) {
        let newNode = new Node(curr.val, curr.next);
        curr.next = newNode;
        curr = newNode.next;
    }
    // Step 2: Assign random pointers
    curr = head;
    while (curr) {
        if (curr.random) {
            curr.next.random = curr.random.next;
        }
        curr = curr.next.next;
    }
    // Step 3: Separate lists
    curr = head;
    let copyHead = head.next;
    let copyCurr = copyHead;
    while (curr) {
        curr.next = curr.next.next;
        if (copyCurr.next) {
            copyCurr.next = copyCurr.next.next;
        }
        curr = curr.next;
        copyCurr = copyCurr.next;
    }
    return copyHead;
};

// Driver code
const nodes = [new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)];
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[1].random = nodes[0];
nodes[2].random = nodes[4];
nodes[3].random = nodes[2];
nodes[4].random = nodes[0];
const copiedHead = copyRandomList(nodes[0]);
console.log(copiedHead.val); // Should print 7

Line Notes

while (curr) {First pass to weave copied nodes after originals

let newNode = new Node(curr.val, curr.next);Creates a copy node

curr.next = newNode;Inserts copy node after original

if (curr.random) {Assigns random pointer for copied node

curr.next.random = curr.random.next;Copied node's random points to copied random node

curr.next = curr.next.next;Restores original list's next pointers during separation

copyCurr.next = copyCurr.next.next;Builds copied list's next pointers during separation

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list three times, each O(n). No extra hash map is used, so space is O(1).

💡 For n=100,000 nodes, this means about 300,000 operations but minimal extra memory usage.

Interview Verdict: Accepted

This is the optimal approach in terms of space and is preferred in interviews once you understand the problem.

🧠

Recursive Approach with Memoization

💡 This approach uses recursion and a hash map to avoid repeated copying of nodes. It helps understand the problem from a top-down perspective and recursion practice.

Intuition

Recursively copy each node and its next and random pointers, using a map to avoid infinite recursion and duplicate copies.

Algorithm

1. If the current node is null, return null.
2. If the current node is already copied (in map), return the copy.
3. Create a copy of the current node and store it in the map.
4. Recursively copy the next and random pointers and assign them to the copied node.
5. Return the copied node.

💡 Memoization prevents infinite recursion and duplicate nodes by caching copies.

</>

Code

class Node:
    def __init__(self, val, next=None, random=None):
        self.val = val
        self.next = next
        self.random = random

def copyRandomList(head):
    old_to_new = {}
    def dfs(node):
        if not node:
            return None
        if node in old_to_new:
            return old_to_new[node]
        copy = Node(node.val)
        old_to_new[node] = copy
        copy.next = dfs(node.next)
        copy.random = dfs(node.random)
        return copy
    return dfs(head)

# Driver code
if __name__ == '__main__':
    nodes = [Node(7), Node(13), Node(11), Node(10), Node(1)]
    nodes[0].next = nodes[1]
    nodes[1].next = nodes[2]
    nodes[2].next = nodes[3]
    nodes[3].next = nodes[4]
    nodes[1].random = nodes[0]
    nodes[2].random = nodes[4]
    nodes[3].random = nodes[2]
    nodes[4].random = nodes[0]
    copied_head = copyRandomList(nodes[0])
    print(copied_head.val)  # Should print 7

Line Notes

old_to_new = {}Memoization dictionary to avoid duplicate copies

def dfs(node):Recursive function to copy nodes

if not node:Base case: null node returns null

if node in old_to_new:Return already copied node to prevent duplicates

copy = Node(node.val)Create a copy of the current node

old_to_new[node] = copyStore copy in memoization map

copy.next = dfs(node.next)Recursively copy next pointer

copy.random = dfs(node.random)Recursively copy random pointer

return copyReturn the copied node

import java.util.HashMap;
class Node {
    int val;
    Node next;
    Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
public class Solution {
    private HashMap<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        if (map.containsKey(head)) return map.get(head);
        Node copy = new Node(head.val);
        map.put(head, copy);
        copy.next = copyRandomList(head.next);
        copy.random = copyRandomList(head.random);
        return copy;
    }

    // Driver code
    public static void main(String[] args) {
        Node[] nodes = new Node[5];
        nodes[0] = new Node(7);
        nodes[1] = new Node(13);
        nodes[2] = new Node(11);
        nodes[3] = new Node(10);
        nodes[4] = new Node(1);
        nodes[0].next = nodes[1];
        nodes[1].next = nodes[2];
        nodes[2].next = nodes[3];
        nodes[3].next = nodes[4];
        nodes[1].random = nodes[0];
        nodes[2].random = nodes[4];
        nodes[3].random = nodes[2];
        nodes[4].random = nodes[0];
        Solution sol = new Solution();
        Node copiedHead = sol.copyRandomList(nodes[0]);
        System.out.println(copiedHead.val); // Should print 7
    }
}

Line Notes

import java.util.HashMap;Imports HashMap for memoization

private HashMap<Node, Node> map = new HashMap<>();Memoization map to avoid duplicate copies

if (map.containsKey(head)) return map.get(head);Return cached copy if exists

Node copy = new Node(head.val);Create copy node

map.put(head, copy);Store copy in map

copy.next = copyRandomList(head.next);Recursively copy next pointer

copy.random = copyRandomList(head.random);Recursively copy random pointer

return copy;Return the copied node

#include <iostream>
#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    Node* next;
    Node* random;
    Node(int _val) {
        val = _val;
        next = nullptr;
        random = nullptr;
    }
};

class Solution {
public:
    unordered_map<Node*, Node*> map;
    Node* copyRandomList(Node* head) {
        if (!head) return nullptr;
        if (map.count(head)) return map[head];
        Node* copy = new Node(head->val);
        map[head] = copy;
        copy->next = copyRandomList(head->next);
        copy->random = copyRandomList(head->random);
        return copy;
    }
};

// Driver code
int main() {
    Node* nodes[5] = {new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)};
    nodes[0]->next = nodes[1];
    nodes[1]->next = nodes[2];
    nodes[2]->next = nodes[3];
    nodes[3]->next = nodes[4];
    nodes[1]->random = nodes[0];
    nodes[2]->random = nodes[4];
    nodes[3]->random = nodes[2];
    nodes[4]->random = nodes[0];
    Solution sol;
    Node* copiedHead = sol.copyRandomList(nodes[0]);
    cout << copiedHead->val << endl; // Should print 7
    return 0;
}

Line Notes

#include <unordered_map>Includes unordered_map for memoization

unordered_map<Node*, Node*> map;Memoization map to avoid duplicate copies

if (map.count(head)) return map[head];Return cached copy if exists

Node* copy = new Node(head->val);Create copy node

map[head] = copy;Store copy in map

copy->next = copyRandomList(head->next);Recursively copy next pointer

copy->random = copyRandomList(head->random);Recursively copy random pointer

return copy;Return the copied node

function Node(val, next = null, random = null) {
    this.val = val;
    this.next = next;
    this.random = random;
}

var copyRandomList = function(head) {
    const map = new Map();
    function dfs(node) {
        if (!node) return null;
        if (map.has(node)) return map.get(node);
        const copy = new Node(node.val);
        map.set(node, copy);
        copy.next = dfs(node.next);
        copy.random = dfs(node.random);
        return copy;
    }
    return dfs(head);
};

// Driver code
const nodes = [new Node(7), new Node(13), new Node(11), new Node(10), new Node(1)];
nodes[0].next = nodes[1];
nodes[1].next = nodes[2];
nodes[2].next = nodes[3];
nodes[3].next = nodes[4];
nodes[1].random = nodes[0];
nodes[2].random = nodes[4];
nodes[3].random = nodes[2];
nodes[4].random = nodes[0];
const copiedHead = copyRandomList(nodes[0]);
console.log(copiedHead.val); // Should print 7

Line Notes

const map = new Map();Memoization map to avoid duplicate copies

function dfs(node) {Recursive function to copy nodes

if (!node) return null;Base case: null node returns null

if (map.has(node)) return map.get(node);Return cached copy if exists

const copy = new Node(node.val);Create copy node

map.set(node, copy);Store copy in map

copy.next = dfs(node.next);Recursively copy next pointer

copy.random = dfs(node.random);Recursively copy random pointer

return copy;Return the copied node

⏱

Complexity

TimeO(n)

SpaceO(n)

Each node is copied once, but recursion stack and map use O(n) space.

💡 For n=100,000 nodes, recursion depth and map size can be large, so watch for stack overflow.

Interview Verdict: Accepted

This approach is elegant and accepted but may risk stack overflow on very large lists.

📊

All Approaches - One-Glance Tradeoffs

💡 The hash map approach is easiest to implement and understand, but uses extra space. The weaving approach is optimal in space but more complex. Recursive memoization is elegant but risks stack overflow.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Hash Map)	O(n)	O(n)	No	Yes	Good to mention and implement if allowed extra space
2. Optimal (Weaving Nodes)	O(n)	O(1)	No	Yes	Preferred approach to code in interviews for optimal space
3. Recursive with Memoization	O(n)	O(n)	Yes (deep recursion)	Yes	Good to mention; implement if recursion is preferred

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start with the brute force approach to build intuition, then learn the optimal weaving technique. Practice coding and explaining each step clearly.

How to Present

Clarify the problem and ask about constraints.Explain the brute force approach using a hash map for clarity.Discuss the space-optimized weaving approach as the optimal solution.Mention the recursive memoization approach if recursion is preferred.Write clean code and test edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of deep copy, pointer manipulation, and handling arbitrary random pointers without mixing original and copied nodes.

Common Follow-ups

• What if random pointers can form cycles? → Your approach handles cycles naturally with memoization or weaving.
• Can you do it without extra space? → Yes, the weaving approach achieves O(1) space.

💡 These follow-ups test your grasp of edge cases and space optimization, common in interviews.

🔍

Pattern Recognition

When to Use

1) You need to copy a complex linked structure, 2) Nodes have arbitrary pointers, 3) Deep copy is required, 4) Avoid mixing original and copy nodes.

Signature Phrases

random pointerdeep copycopy list with arbitrary pointer

NOT This Pattern When

Shallow copy problems or simple linked list copy without random pointers

Similar Problems

Clone Graph - similar deep copy with arbitrary connectionsCopy Binary Tree with Random Pointer - tree variant of this problem

Practice

1. You need to design a system that supports posting tweets and retrieving the 10 most recent tweets from a user's timeline, including tweets from users they follow. Which approach best balances efficient posting and retrieving the top recent tweets in real-time?

easy

A. Store all tweets in a global list and scan it entirely each time to find the top 10 recent tweets.

B. Maintain a linked list of tweets per user, a hashmap for followees, and use a max heap to merge the most recent tweets from followees efficiently.

C. Use a dynamic programming approach to precompute the top tweets for each user after every post.

D. Use a simple array per user and sort all tweets from followees every time the feed is requested.

Solution

1. Step 1: Understand the problem constraints

   The system must support fast posting and retrieving the top 10 recent tweets from a user's followees including themselves.

2. Step 2: Evaluate approaches

   Brute force scanning or sorting all tweets each time is inefficient. DP is not applicable here. Using linked lists per user and a max heap for merging recent tweets achieves O(1) posting and O(k log F) retrieval, where F is followees count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linked list + hashmap + heap is the optimal pattern for this problem [OK]

Hint: Linked list + heap merges recent tweets efficiently [OK]

Common Mistakes:

• Thinking sorting all tweets each time is efficient
• Trying DP for a streaming feed problem

2. Given the following addRange method snippet from the optimal RangeModule implementation, what is the value of self.starts after calling addRange(2, 6) on an initially empty RangeModule?

def addRange(self, left: int, right: int) -> None:
    i = bisect_left(self.starts, left)
    j = bisect_right(self.starts, right)

    if i != 0 and self.intervals[self.starts[i-1]] >= left:
        i -= 1
        left = min(left, self.starts[i])
    if j != 0:
        right = max(right, self.intervals[self.starts[j-1]])

    for k in self.starts[i:j]:
        del self.intervals[k]
    self.starts[i:j] = [left]
    self.intervals[left] = right

easy

A. [2, 6, 7]

B. [2, 6]

C. [2]

D. [6]

Solution

1. Step 1: Trace bisect indices on empty starts list

   Initially, self.starts = []. Calling bisect_left([], 2) returns 0, and bisect_right([], 6) returns 0.

2. Step 2: Update intervals and starts

   Since i == 0, the first if condition is skipped. Also, j == 0, so second if is skipped. No intervals to delete. Insert left=2 at self.starts[0:0], so self.starts = [2]. Interval stored as {2:6}.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starts list after first addRange is [2] [OK]

Hint: Bisect on empty list returns 0, so starts list gets single element [OK]

Common Mistakes:

• Assuming right endpoint is also inserted in starts list

3. What is the average time complexity of the remove operation in the optimized Insert Delete GetRandom O(1) with duplicates data structure that uses a hash map of element to linked list nodes and a list of elements?

medium

A. O(n) because we need to find the element's index in the list before removal.

B. O(log n) due to maintaining the linked list structure during removals.

C. O(1) worst-case because linked list removals and hash map lookups are constant time.

D. O(1) average because the hash map provides direct access to an element's node for removal.

Solution

1. Step 1: Identify data structure operations

   Removal uses hash map to get a node reference in O(1) average time, then removes node from doubly linked list in O(1).

2. Step 2: Clarify average vs worst-case

   Hash map lookups are average O(1), but worst-case can degrade. Linked list removal is always O(1). So overall average is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Hash map + linked list enables average O(1) removals [OK]

Hint: Hash map + linked list enables average O(1) removals [OK]

Common Mistakes:

• Confusing average and worst-case complexities
• Assuming linked list removal is O(log n)
• Thinking index search is needed

4. What is the amortized time complexity of the put operation in the optimal LFU Cache implementation using a frequency map of doubly linked lists and hash maps?

medium

A. O(n), where n is the number of keys in the cache

B. O(f), where f is the number of distinct frequencies

C. O(log n), due to maintaining frequency order

D. O(1), amortized constant time

Solution

1. Step 1: Analyze data structures used

   Hash maps provide O(1) access to keys and frequencies. Doubly linked lists allow O(1) insertion and deletion of keys within frequency groups.

2. Step 2: Consider operations in put

   Eviction and frequency updates involve O(1) operations on hash maps and linked lists. Frequency increments and min frequency updates are also O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal LFU cache achieves O(1) amortized put [OK]

Hint: Hash maps + linked lists enable O(1) put [OK]

Common Mistakes:

• Assuming O(n) due to scanning keys
• Thinking frequency updates cost O(log n)
• Confusing distinct frequencies with n

5. What is the time complexity of performing addRange, removeRange, or queryRange operations in the optimal RangeModule implementation using a balanced BST with interval merging, assuming n intervals stored?

medium

A. O(n) per operation because intervals must be scanned to merge overlaps.

B. O(log n + k) where k is the number of overlapping intervals merged or removed.

C. O(log n) per operation due to balanced BST operations and interval merging.

D. O(1) amortized due to efficient data structure caching.

Solution

1. Step 1: Identify main operations

   Each operation uses binary search (O(log n)) to find affected intervals and merges or removes overlapping intervals.

2. Step 2: Consider merging/removal cost

   The number of intervals merged or removed, k, affects the cost linearly. So total cost is O(log n + k).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Logarithmic search plus linear merging -> O(log n + k) [OK]

Hint: Operations cost depends on search plus number of intervals merged [OK]

Common Mistakes:

• Assuming always O(log n) ignoring merging cost
• Assuming linear scan O(n) always