Insert Delete GetRandom O(1) with Duplicates

▶

Steps

setup

Initialize empty data structure

Create an empty list 'nums' and empty maps 'idx_map' and 'node_map'. No values or nodes exist yet.

💡 Starting with empty structures is essential to see how insertions build the data structure incrementally.

Line:

self.nums = []
self.idx_map = {}
self.node_map = {}

💡 The data structure starts empty, ready to store values and their index nodes.

insert

Insert first 1: add value and create linked list

Insert value 1. Since 1 is not in idx_map, create a new doubly linked list for 1. Append 1 to nums at index 0. Append index 0 node to 1's linked list.

💡 This step shows how a new value initializes its own linked list of indices and how the main list grows.

Line:

if val not in self.idx_map:
    self.idx_map[val] = DoublyLinkedList()
self.nums.append(val)
node = self.idx_map[val].append(len(self.nums) - 1)

💡 Each value has a dedicated doubly linked list tracking all indices where it appears in nums.

insert

Insert second 1: append index to existing linked list

Insert value 1 again. Since 1 exists, do not create a new linked list. Append 1 to nums at index 1. Append index 1 node to 1's linked list.

💡 This step shows how duplicates share the same linked list, tracking multiple indices.

Line:

self.nums.append(val)
node = self.idx_map[val].append(len(self.nums) - 1)

💡 The linked list for 1 now contains two nodes, representing two indices in nums.

insert

Insert 2: create new linked list and append

Insert value 2. Since 2 is new, create a linked list for 2. Append 2 to nums at index 2. Append index 2 node to 2's linked list.

💡 This step shows how a new value gets its own linked list, separate from 1's list.

Line:

if val not in self.idx_map:
    self.idx_map[val] = DoublyLinkedList()
self.nums.append(val)
node = self.idx_map[val].append(len(self.nums) - 1)

💡 Multiple linked lists coexist, each tracking indices of a distinct value.

getRandom

getRandom(): pick random index from nums

Randomly select an index from nums (0 to 2). Return the value at that index (1 or 2).

💡 This step shows how getRandom uses the main list to return a random element in O(1).

Line:

rand_idx = random.randint(0, len(self.nums) - 1)
return self.nums[rand_idx]

💡 Random access is efficient because nums stores all values contiguously.

remove

Remove one occurrence of 1: locate index to remove

Locate the first node in 1's linked list, which holds index 0. This index will be removed from nums.

💡 This step shows how removal targets a specific index from the linked list of duplicates.

Line:

node = self.idx_map[val].head.next
remove_idx = node.val

💡 Linked list nodes allow quick access to indices for removal.

remove

Remove node from 1's linked list

Remove the node at index 0 from 1's linked list, detaching it from the chain.

💡 This step updates the linked list to reflect the removal of one occurrence of 1.

Line:

self.idx_map[val].remove(node)

💡 Removing the node updates the linked list to no longer track index 0 for 1.

remove

Swap last element with removed index in nums

Swap the last element (index 2, value 2) into the removed index 0 position in nums to keep array compact.

💡 This step maintains O(1) removal by swapping with the last element instead of shifting.

Line:

last_val = self.nums[-1]
self.nums[remove_idx] = last_val

💡 Swapping avoids costly array shifts and keeps indices consistent.

remove

Update linked list for swapped value 2

Update 2's linked list to replace old index 2 node with new index 0 node, reflecting the swap.

💡 This step keeps the index tracking accurate after the swap.

Line:

node_to_update = self.node_map[len(self.nums) - 1]
node_to_update.val = remove_idx
self.node_map[remove_idx] = node_to_update
self.node_map.pop(len(self.nums) - 1)

💡 Linked lists track indices, so updating nodes is crucial after swaps.

remove

Remove last element from nums

Remove the last element from nums since it was swapped forward, shrinking the list size.

💡 This step finalizes the removal by shrinking the main list.

Line:

self.nums.pop()

💡 Shrinking the list keeps the data structure compact and consistent.

getRandom

getRandom(): pick random index from updated nums

Randomly select an index from nums (0 or 1). Return the value at that index (2 or 1).

💡 This step shows getRandom reflecting the updated collection after removal.

Line:

rand_idx = random.randint(0, len(self.nums) - 1)
return self.nums[rand_idx]

💡 getRandom always returns a value present in the current collection.

import random

class Node:
    def __init__(self, val):
        self.val = val  # index in nums
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = Node(None)  # STEP 1
        self.tail = Node(None)  # STEP 1
        self.head.next = self.tail
        self.tail.prev = self.head

    def append(self, val):
        node = Node(val)  # STEP 2
        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  # STEP 7
        node.next.prev = node.prev

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

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

    def insert(self, val: int) -> bool:
        if val not in self.idx_map:  # STEP 2,4
            self.idx_map[val] = DoublyLinkedList()
        self.nums.append(val)  # STEP 2,3,4
        node = self.idx_map[val].append(len(self.nums) - 1)
        self.node_map[len(self.nums) - 1] = node
        return self.idx_map[val].head.next == node and node.next == self.idx_map[val].tail

    def remove(self, val: int) -> bool:
        if val not in self.idx_map or self.idx_map[val].is_empty():  # STEP 6
            return False
        node = self.idx_map[val].head.next  # STEP 6
        remove_idx = node.val
        self.idx_map[val].remove(node)  # STEP 7

        last_val = self.nums[-1]  # STEP 8
        self.nums[remove_idx] = last_val

        node_to_update = self.node_map[len(self.nums) - 1]  # STEP 9
        node_to_update.val = remove_idx
        self.node_map[remove_idx] = node_to_update
        del self.node_map[len(self.nums) - 1]

        self.nums.pop()  # STEP 10
        return True

    def getRandom(self) -> int:
        rand_idx = random.randint(0, len(self.nums) - 1)  # STEP 5,11
        return self.nums[rand_idx]

📊

Insert Delete GetRandom O(1) with Duplicates - Watch the Algorithm Execute, Step by Step

Watching each pointer update and list modification reveals how the algorithm efficiently handles duplicates and maintains index mappings, which is hard to grasp from code alone.

advance

insert

0

Result: [1]

insert

0

→

1

Result: [1, 1]

insert

0

→

1

→

2

Result: [1, 1, 2]

compare

0

→

1

→

2

Result: [1, 1, 2]

delete

0

→

1

→

2

Result: [1, 1, 2]

detach

0

→

1

→

2

Result: [1, 1, 2]

connect

2

→

1

→

2

Result: [2, 1, 2]

advance

0

→

1

Result: [2, 1]

shrink

0

→

1

Result: [2, 1]

compare

0

→

1

Result: [2, 1]

Key Takeaways

✓ Using a doubly linked list per value to track indices allows O(1) removal of any occurrence of duplicates.

This insight is hard to see from code alone because the linked list structure and its role in index tracking are implicit.

✓ Swapping the last element into the removed index keeps the main array compact and enables O(1) getRandom.

Visualizing the swap clarifies why no shifting is needed and how indices must be updated.

✓ getRandom simply picks a random index from the main list, reflecting the current multiset distribution.

Seeing the random pointer move helps understand the probabilistic output.

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. You are given a list of buildings represented as triplets (left, right, height). The goal is to output the skyline formed by these buildings as a list of key points where the height changes. Which algorithmic approach guarantees an optimal solution with time complexity O(n log n)?

easy

A. Divide and conquer approach that recursively merges skylines of building subsets

B. Dynamic programming approach that stores maximum heights for subproblems

C. Greedy approach that iteratively picks the tallest building at each x-coordinate

D. Brute force simulation by iterating over all x-coordinates and tracking max height

Solution

1. Step 1: Understand problem requirements

   The problem requires merging multiple building outlines into a single skyline efficiently.

2. Step 2: Evaluate algorithmic approaches

   Greedy and brute force approaches either fail to guarantee optimal time or are inefficient. Dynamic programming is not a natural fit here. Divide and conquer merges smaller skylines efficiently in O(n log n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Divide and conquer merges sorted skylines efficiently [OK]

Hint: Divide and conquer merges sorted skylines in O(n log n) [OK]

Common Mistakes:

• Thinking greedy or brute force is optimal
• Confusing DP with skyline merging

3. Identify the bug in the following LRU Cache implementation snippet that causes incorrect eviction behavior when capacity is exceeded:

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self._remove(self.cache[key])
    node = Node(key, value)
    self._add(node)
    self.cache[key] = node
    if len(self.cache) > self.capacity:
        lru = self.head.next  # Bug here
        self._remove(lru)
        del self.cache[lru.key]

medium

A. Evicting the node at head.next instead of tail.prev

B. Removing node from cache before adding new node

C. Not updating the cache dictionary after eviction

D. Not checking if capacity is zero before eviction

Solution

1. Step 1: Understand eviction logic

   Eviction must remove the least recently used node, which is at tail.prev, not head.next.

2. Step 2: Identify bug

   Code incorrectly evicts head.next, which is the most recently used node, causing wrong eviction.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Evicting head.next breaks LRU policy, must evict tail.prev [OK]

Hint: LRU node is at tail.prev, not head.next [OK]

Common Mistakes:

• Evicting MRU instead of LRU
• Forgetting to delete from cache dict
• Not handling zero capacity

4. 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

5. Suppose the multilevel doubly linked list can have cycles introduced via child pointers (i.e., a child pointer may point to an ancestor node). Which modification to the flattening algorithm is necessary to handle this safely?

hard

A. Use recursion with a depth limit to prevent stack overflow on cycles.

B. Remove all child pointers before flattening to guarantee acyclic structure.

C. Use a hash set to track visited nodes and skip already visited ones to avoid infinite loops.

D. No modification needed; the existing in-place iterative approach handles cycles naturally.

Solution

1. Step 1: Understand the problem with cycles

   Cycles cause infinite loops during traversal if nodes are revisited.

2. Step 2: Identify safe traversal method

   Tracking visited nodes with a hash set prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Removing child pointers loses structure; recursion depth limit is unreliable; existing code does not detect cycles.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Visited set prevents infinite loops in cyclic graphs [OK]

Hint: Track visited nodes to handle cycles safely [OK]

Common Mistakes:

• Assuming no cycles exist in input
• Relying on recursion depth limits
• Ignoring cycle detection altogether