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. You need to design a system that tracks passengers checking in and out of stations, and efficiently calculates average travel times between stations. Which approach best balances time and space efficiency for frequent queries?

easy

A. Use hash maps to store running totals of travel times and counts per route.

B. Store all trips explicitly and scan them to compute averages on demand.

C. Use dynamic programming to precompute all possible route averages.

D. Use a priority queue to keep track of the shortest travel times per route.

Solution

1. Step 1: Understand the problem requirements

   The system must support frequent check-ins, check-outs, and quick average time queries between stations.

2. Step 2: Evaluate approaches

   Storing all trips (B) leads to slow queries. Dynamic programming (C) is not applicable as routes are dynamic and not fixed. Priority queues (D) do not help compute averages efficiently. Hash maps with running totals (A) allow O(1) updates and queries.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash maps maintain running sums and counts for O(1) average time queries [OK]

Hint: Running totals enable O(1) average queries [OK]

Common Mistakes:

• Thinking storing all trips is efficient for queries

2. Consider the following Python code snippet implementing the optimized Insert Delete GetRandom O(1) with duplicates data structure. After executing the sequence of operations below, what is the return value of the final getRandom() call? Operations: insert(1), insert(1), insert(2), remove(1), getRandom()

import random

class Node:
    def __init__(self, val):
        self.val = val
        self.prev = null
        self.next = null

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(null)
        self.tail = Node(null)
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node
        return node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def is_empty(self):
        return self.head.next == self.tail

class RandomizedCollection:
    def __init__(self):
        self.nums = []
        self.idx_map = {}

    def insert(self, val: int) -> bool:
        self.nums.append(val)
        if val not in self.idx_map:
            self.idx_map[val] = set()
        self.idx_map[val].add(len(self.nums) - 1)
        return len(self.idx_map[val]) == 1

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or not self.idx_map[val]:
            return false
        remove_idx = self.idx_map[val].pop()
        last_val = self.nums[-1]
        self.nums[remove_idx] = last_val
        self.idx_map[last_val].add(remove_idx)
        self.idx_map[last_val].discard(len(self.nums) - 1)
        self.nums.pop()
        if not self.idx_map[val]:
            del self.idx_map[val]
        return true

    def getRandom(self) -> int:
        return random.choice(self.nums)

rc = RandomizedCollection()
rc.insert(1)
rc.insert(1)
rc.insert(2)
rc.remove(1)
result = rc.getRandom()

easy

A. Either 1 or 2 but 1 is twice as likely

B. 2

C. Either 1 or 2 with equal probability

D. 1

Solution

1. Step 1: Trace insertions

   After insert(1), nums=[1], idx_map={1:{0}}; after insert(1), nums=[1,1], idx_map={1:{0,1}}; after insert(2), nums=[1,1,2], idx_map={1:{0,1},2:{2}}.

2. Step 2: Trace removal of one 1

   Remove one 1: remove_idx=1 (pop from idx_map[1]). Swap last element 2 into index 1: nums=[1,2], idx_map={1:{0},2:{1}}. So now nums has one 1 and one 2.

3. Step 3: Analyze getRandom probabilities

   nums=[1,2], so getRandom picks index 0 or 1 equally. But initially there were two 1's, after removal only one remains. So 1 and 2 are equally likely, but since the original had duplicates, the final collection has one 1 and one 2.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   After removal, one 1 and one 2 remain, so 1 is as likely as 2 [OK]

Hint: Track indices and swaps carefully to find final array state [OK]

Common Mistakes:

• Forgetting to update idx_map after swap
• Assuming getRandom returns only 2
• Ignoring that one 1 remains after removal

3. You need to design a data structure that supports adding intervals, removing intervals, and querying whether a given range is fully covered by the added intervals. Which approach guarantees efficient updates and queries with logarithmic time complexity per operation?

easy

A. Use a balanced binary search tree (e.g., TreeMap) to store and merge intervals, enabling logarithmic time operations.

B. Use a brute force list of intervals and scan all intervals for each operation.

C. Use dynamic programming to precompute coverage for all possible ranges.

D. Use a greedy algorithm that always merges intervals only when queried.

Solution

1. Step 1: Understand the problem requirements

   The data structure must support add, remove, and query operations on intervals efficiently.

2. Step 2: Evaluate approaches

   Brute force scanning is O(n) per operation, which is inefficient. DP is not suitable for dynamic interval updates. Greedy merging only on query delays merging and leads to inefficient queries. Balanced BST with interval merging maintains sorted intervals and merges overlapping ones, supporting O(log n) operations.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Balanced BST with merging -> O(log n) per operation [OK]

Hint: Balanced BST with merging enables efficient interval operations [OK]

Common Mistakes:

• Thinking DP or greedy solves dynamic interval updates efficiently

4. What is the time complexity of adding a number and then finding the median using the balanced two heaps approach with lazy deletion for a data stream of size n?

medium

A. O(log n) per addNum and O(log n) per findMedian

B. O(n) per addNum and O(1) per findMedian

C. O(log n) per addNum and O(1) per findMedian

D. O(1) per addNum and O(n) per findMedian

Solution

1. Step 1: Analyze addNum complexity

   Adding a number involves pushing to a heap and balancing heaps, each O(log n) operations.

2. Step 2: Analyze findMedian complexity

   Median is retrieved from the top of heaps without modification, O(1) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Insertion is O(log n), median retrieval O(1) [OK]

Hint: Heap push/pop are O(log n), median peek is O(1) [OK]

Common Mistakes:

• Assuming sorting each query is O(log n)
• Confusing addNum with findMedian complexity

5. Suppose the data stream allows duplicate numbers to be removed after insertion, requiring support for removeNum(num). Which modification to the balanced two heaps approach is necessary to maintain correct median retrieval?

hard

A. Use a balanced binary search tree instead of heaps to allow efficient removals.

B. Ignore removals and only add numbers, as removals break the heap structure.

C. Rebuild both heaps from scratch after every removal to maintain heap properties.

D. Add a delayed deletion map to mark elements for lazy removal and prune heaps during addNum and findMedian.

Solution

1. Step 1: Understand removal challenges

   Heaps do not support efficient arbitrary removals, so direct removal breaks heap properties.

2. Step 2: Use lazy deletion

   Maintain a delayed deletion map to mark elements for removal and prune them lazily during heap operations, preserving heap structure and efficiency.

3. Step 3: Avoid costly rebuilds

   Rebuilding heaps on every removal is inefficient; ignoring removals is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Lazy deletion with pruning maintains correctness and efficiency [OK]

Hint: Lazy deletion map enables efficient removals in heaps [OK]

Common Mistakes:

• Rebuilding heaps on every removal
• Ignoring removals breaks correctness