Copy List with Random Pointer

▶

Steps

setup

Start copying from head node (val=7)

The algorithm begins by calling dfs on the head node with value 7 to start the deep copy process.

💡 Starting at the head is essential because the entire list is reachable from here.

Line:

return dfs(head)

💡 The recursion will traverse all nodes reachable from head.

compare

Check if current node (val=7) is null

The algorithm checks if the current node is null to handle the base case of recursion.

💡 This base case prevents infinite recursion and signals when to stop.

Line:

if not node:
    return None

💡 Non-null nodes must be copied; null nodes return None.

compare

Check if node (val=7) already copied

The algorithm checks if the current node has already been copied by looking it up in the memoization map.

💡 Memoization prevents duplicate copies and infinite loops with random pointers.

Line:

if node in old_to_new:
    return old_to_new[node]

💡 Memoization map tracks nodes already copied.

insert

Create copy of node (val=7)

A new node with value 7 is created as a copy of the current node and stored in the memoization map.

💡 Creating a copy node is the core of the deep copy process.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Each original node maps to exactly one copied node.

traverse

Recursively copy next pointer of node (val=7)

The algorithm calls dfs on the next node (val=13) to copy the next pointer of the copied node.

💡 Recursively copying next pointers builds the copied list structure.

Line:

copy.next = dfs(node.next)

💡 Next pointers are copied by recursive calls.

insert

Create copy of node (val=13)

A new node with value 13 is created as a copy of the current node and stored in the memoization map.

💡 Each node encountered is copied once and memoized.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Memoization map grows as new nodes are copied.

traverse

Recursively copy next pointer of node (val=13)

The algorithm calls dfs on the next node (val=11) to copy the next pointer of the copied node 13.

💡 Recursion continues down the next pointers to copy the entire list.

Line:

copy.next = dfs(node.next)

💡 Next pointers form a chain of recursive calls.

insert

Create copy of node (val=11)

A new node with value 11 is created and stored in the memoization map.

💡 Each node is copied exactly once to maintain structure.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Memoization map ensures unique copies.

traverse

Recursively copy next pointer of node (val=11)

The algorithm calls dfs on the next node (val=10) to copy the next pointer of the copied node 11.

💡 Recursion continues to copy the entire next chain.

Line:

copy.next = dfs(node.next)

💡 Next pointers are copied in order.

insert

Create copy of node (val=10)

A new node with value 10 is created and stored in the memoization map.

💡 Copying continues for each node in the list.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Each node is uniquely copied and memoized.

traverse

Recursively copy next pointer of node (val=10)

The algorithm calls dfs on the next node (val=1) to copy the next pointer of the copied node 10.

💡 Recursion continues until the end of the list.

Line:

copy.next = dfs(node.next)

💡 Next pointers form a chain of recursive calls until null.

insert

Create copy of node (val=1)

A new node with value 1 is created and stored in the memoization map.

💡 The last node is copied to complete the list.

Line:

copy = Node(node.val)
old_to_new[node] = copy

💡 Memoization map now contains all nodes.

traverse

Recursively copy next pointer of node (val=1)

The algorithm calls dfs on the next pointer of node 1, which is null, to end recursion on next pointers.

💡 Base case reached for next pointer recursion.

Line:

copy.next = dfs(node.next)

💡 Null next pointers terminate recursion.

traverse

Recursively copy random pointer of node (val=1)

The algorithm now copies the random pointer of node 1, which points to node 7 (id=0).

💡 Random pointers can point anywhere; recursion handles this similarly to next pointers.

Line:

copy.random = dfs(node.random)

💡 Random pointers are copied by recursive calls, possibly revisiting nodes.

prune

Return copy of node (val=7) from memoization

Since node 7 was already copied, the algorithm returns the existing copy from the memoization map to assign as random pointer.

💡 Memoization avoids duplicate copies and infinite recursion.

Line:

if node in old_to_new:
    return old_to_new[node]

💡 Memoization map is key to efficient copying.

connect

Assign random pointer of copied node (val=1) to copied node (val=7)

The random pointer of the copied node 1 is set to the copied node 7, completing the random pointer assignment for node 1.

💡 Assigning random pointers completes the deep copy structure.

Line:

copy.random = dfs(node.random)

💡 Random pointers link copied nodes correctly.

traverse

Recursively copy random pointer of node (val=10)

The algorithm copies the random pointer of node 10, which points to node 11 (id=2).

💡 Random pointers may point forward or backward; recursion handles all cases.

Line:

copy.random = dfs(node.random)

💡 Random pointer recursion may revisit nodes already copied.

prune

Return copy of node (val=11) from memoization for random pointer

Node 11 is already copied, so the algorithm returns the existing copy to assign as random pointer of node 10's copy.

💡 Memoization prevents duplicate copies and infinite recursion.

Line:

if node in old_to_new:
    return old_to_new[node]

💡 Memoization map is reused for random pointers.

connect

Assign random pointer of copied node (val=10) to copied node (val=11)

The random pointer of the copied node 10 is set to the copied node 11, completing this random pointer assignment.

💡 Random pointers link copied nodes correctly to replicate original structure.

Line:

copy.random = dfs(node.random)

💡 Random pointers are assigned after next pointers.

reconstruct

Return copied head node

The recursion completes and returns the copied head node representing the deep copied list.

💡 Returning the copied head gives access to the entire copied list.

Line:

return dfs(head)

💡 The copied list is fully constructed with correct next and random pointers.

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):
        # STEP 2: Check if node is null
        if not node:
            return None
        # STEP 3 & 15: Check memoization
        if node in old_to_new:
            return old_to_new[node]
        # STEP 4,6,8,10,12: Create copy
        copy = Node(node.val)
        old_to_new[node] = copy
        # STEP 5,7,9,11,13: Copy next pointer recursively
        copy.next = dfs(node.next)
        # STEP 14,17,19: Copy random pointer recursively
        copy.random = dfs(node.random)
        return copy
    # STEP 1 & 20: Start recursion and return copied head
    return dfs(head)

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

📊

Copy List with Random Pointer - Watch the Algorithm Execute, Step by Step

Watching each recursive call and memoization step reveals how the algorithm avoids infinite loops and ensures a deep copy with correct random pointers.

advance

7

→

13

→

11

→

10

→

1

compare

7

→

13

→

11

→

10

→

1

compare

7

→

13

→

11

→

10

→

1

insert

7

→

13

→

11

→

10

→

1

→

7

advance

7

→

13

→

11

→

10

→

1

→

7

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

insert

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

compare

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

advance

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

prune

7

→

13

→

11

→

10

→

1

→

7

→

13

→

11

→

10

→

1

connect

7

→

13

→

11

→

10

→

1

advance

10

→

11

→

7

→

13

→

11

→

10

→

1

prune

11

→

10

connect

7

→

13

→

11

→

10

→

1

reconstruct

7

→

13

→

11

→

10

→

1

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

Key Takeaways

✓ Memoization is critical to avoid infinite recursion and duplicate copies when copying random pointers.

Without memoization, the algorithm would endlessly recurse on cycles formed by random pointers.

✓ The algorithm copies next pointers first, then random pointers, ensuring the copied list structure is built before linking random pointers.

This order clarifies how the recursion builds the list step-by-step.

✓ Each recursive call corresponds to copying one node, and the visualization shows how the recursion stack grows and shrinks.

Seeing each call separately helps understand recursion depth and flow.

Practice

1. Consider the following Python code snippet for the MedianFinder class using two heaps. After adding the numbers 1, 5, and 3 in that order, what is the value of the median returned by findMedian()?

easy

A. 1.0

B. 3.0

C. 5.0

D. 2.0

Solution

1. Step 1: Insert 1

   Low heap empty, push -1 to low; low_size=1, high_size=0.

2. Step 2: Insert 5

   5 > -low[0] (which is 1), push 5 to high; low_size=1, high_size=1; heaps balanced.

3. Step 3: Insert 3

   3 <= 5 but > 1, push 3 to high; high_size=2, low_size=1; balance heaps by moving smallest from high (3) to low (-3); low_size=2, high_size=1.

4. Step 4: Find median

   low_size > high_size, median is -low[0] = 3.0.

5. Step 5: Re-examine median calculation

   After balancing, low heap has [-3, -1], high heap has [5]. Median is top of low heap = 3.0, but the question asks for median after adding 1,5,3 in order, so median is 3.0.

6. Final Answer:

   Option B -> Option B

7. Quick Check:

   Median after [1,5,3] is 3.0 [OK]

Hint: Median is top of larger heap after balancing [OK]

Common Mistakes:

• Forgetting to balance heaps after insertion
• Returning wrong heap top for median

2. You are given a doubly linked list where some nodes have a child pointer to another doubly linked list. The child lists can themselves have children, and so on. Which approach best guarantees an in-place flattening of this multilevel list into a single-level doubly linked list without using extra space?

easy

A. Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.

B. Use a recursive depth-first traversal that returns the tail of each flattened child list to connect nodes.

C. Apply a greedy approach that always appends child lists at the end of the main list after full traversal.

D. Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.

Solution

1. Step 1: Understand the problem constraints

   The problem requires flattening a multilevel doubly linked list in-place without extra space.

2. Step 2: Identify the approach that guarantees in-place flattening without extra space

   Using a recursive depth-first traversal that returns the tail of each flattened child list allows splicing child lists correctly and efficiently without extra data structures.

3. Step 3: Evaluate other options

   Iterative splicing (Iteratively traverse the list, and whenever a node has a child, splice the child list in place by connecting the child's tail to the node's next, updating pointers accordingly.) can cause repeated tail searches leading to O(n^2) time and is less straightforward. Greedy appending (Apply a greedy approach that always appends child lists at the end of the main list after full traversal.) fails to maintain order. Dynamic programming (Use dynamic programming to store intermediate flattened sublists and merge them bottom-up.) is not applicable.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Recursive DFS approach is standard and efficient for in-place flattening [OK]

Hint: Recursive DFS returns tail to connect lists efficiently [OK]

Common Mistakes:

• Assuming iterative splicing is always best despite complexity
• Appending child lists only at the end
• Using DP which is not applicable here

3. You need to design a data structure that supports inserting elements (including duplicates), removing one occurrence of an element, and retrieving a random element--all in average O(1) time. Which approach best guarantees these time complexities?

easy

A. Use a simple list and perform linear search for removals.

B. Use a balanced binary search tree to maintain elements and their counts.

C. Use a hash map to store element to indices mapping, combined with a list to store elements, updating indices on insert and remove.

D. Use a queue to track insertion order and a hash set for membership checks.

Solution

1. Step 1: Understand the operations required

   Insert, remove (one occurrence), and getRandom must all be average O(1), even with duplicates.

2. Step 2: Evaluate approaches

   A simple list with linear search (A) leads to O(n) removals. Balanced BST (C) has O(log n) operations. Queue and hash set (D) do not support random access efficiently. Hash map + list with index tracking (B) supports O(1) insert, remove, and getRandom by maintaining indices of duplicates.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Hash map + list with index tracking enables O(1) average operations [OK]

Hint: Hash map + list with index tracking enables O(1) ops [OK]

Common Mistakes:

• Assuming balanced BST can do O(1) getRandom
• Using linear search for removal
• Ignoring duplicates in data structure

4. Suppose the Twitter design is extended so that users can post the same tweet multiple times (tweet reuse allowed). Which modification to the optimal approach is necessary to correctly handle this scenario?

hard

A. Allow multiple TweetNode instances with the same tweetId but different timestamps in the linked list and heap.

B. Use a hash set to track unique tweetIds per user to avoid duplicates in the feed.

C. Modify the heap to store tweetIds only once, ignoring repeated posts of the same tweetId.

D. Disallow posting duplicate tweetIds by rejecting posts with existing tweetIds.

Solution

1. Step 1: Understand tweet reuse impact

   Allowing duplicate tweetIds means multiple posts with same id but different times must be treated as distinct tweets.

2. Step 2: Adjust data structures

   Each post creates a new TweetNode with unique timestamp; heap and linked lists handle duplicates naturally by time ordering.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multiple nodes with same tweetId but different times must be stored separately [OK]

Hint: Treat each post as unique by timestamp, even if tweetId repeats [OK]

Common Mistakes:

• Trying to deduplicate tweets in feed incorrectly
• Rejecting duplicate posts unnecessarily

5. Suppose the LFU cache must support a new operation: reuse(key) which resets the frequency of key to 1 without changing its value. Which modification to the optimal LFU cache design correctly supports this operation without breaking O(1) complexity?

hard

A. Simply set the frequency of the key to 1 in the key_val_freq map without moving it between frequency lists

B. Clear the entire cache and reinsert the key with frequency 1

C. Remove the key from its current frequency list and add it to freq=1 list, update min_freq to 1

D. Increment the frequency of the key by 1 and then reset min_freq to 1

Solution

1. Step 1: Understand reuse operation

   Reuse resets frequency to 1, so the key must move from its current frequency list to the freq=1 list.

2. Step 2: Update data structures accordingly

   Remove key from old freq list, add to freq=1 list, and update min_freq to 1 to reflect the new minimum frequency.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Moving key between freq lists and updating min_freq preserves O(1) operations [OK]

Hint: Move key to freq=1 list and update min_freq [OK]

Common Mistakes:

• Not moving key between frequency lists
• Resetting frequency without updating min_freq
• Clearing cache is inefficient and breaks O(1)