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 data structure that supports incrementing and decrementing string keys, and retrieving a key with the maximum or minimum count, all in constant time. Which approach best guarantees O(1) time complexity for all these operations?

easy

A. Using a balanced binary search tree keyed by counts to maintain order of keys

B. Using a hash map to store counts and scanning all keys to find max/min when requested

C. Maintaining a doubly linked list of buckets, each bucket holding keys with the same count, plus hash maps for quick access

D. Using a priority queue to track max and min keys with lazy updates

Solution

1. Step 1: Understand operation requirements

   Increment, decrement, getMaxKey, and getMinKey must all be O(1).

2. Step 2: Evaluate approaches

   Hash map + linear scan (B) is O(n) for max/min. Balanced BST (C) and priority queue (D) have O(log n) operations. Doubly linked list with buckets and hash maps (A) supports O(1) updates and retrievals.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bucket list + hash maps enable O(1) increments, decrements, and max/min retrievals [OK]

Hint: Bucket list + hash maps enable O(1) max/min updates [OK]

Common Mistakes:

• Thinking balanced BST or priority queue can achieve O(1) for all operations

2. Consider the following Python code implementing an LRU Cache with capacity 2. After executing the sequence of operations below, what is the return value of cache.get(1)?

cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
cache.get(1)
cache.put(3, 3)
cache.get(2)
cache.put(4, 4)
cache.get(1)
cache.get(3)
cache.get(4)

easy

A. 1

B. 3

C. -1

D. 4

Solution

1. Step 1: Trace cache state after each operation

   After put(1,1) and put(2,2), cache has keys [2 (MRU), 1 (LRU)]. get(1) moves key 1 to MRU, order: [1,2]. put(3,3) evicts LRU key 2, cache: [3,1]. get(2) returns -1 (evicted). put(4,4) evicts LRU key 1, cache: [4,3].

2. Step 2: Evaluate get(1) after put(4,4)

   Key 1 was evicted, so get(1) returns -1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Key 1 evicted after put(4,4), so get(1) -> -1 [OK]

Hint: Remember to update usage order on get and evict LRU on put [OK]

Common Mistakes:

• Forgetting to move accessed node to front
• Evicting wrong node
• Returning wrong value after eviction

3. You need to design a data structure that supports setting values at indices, taking snapshots of the entire array state, and retrieving values at any snapshot efficiently. Which approach best balances time and space complexity for frequent set and get operations?

easy

A. Store full copies of the array on every snapshot to allow O(1) get operations.

B. Maintain a hash map per index storing (snap_id, value) pairs and use binary search to retrieve values for get operations.

C. Use a single global hash map keyed by (index, snap_id) and perform linear search for get operations.

D. Use a segment tree to store snapshots and query values at any snapshot.

Solution

1. Step 1: Understand problem requirements

   The data structure must efficiently support set, snap, and get operations with many snapshots and updates.

2. Step 2: Evaluate approaches

   Storing full snapshots (B) uses too much space and is slow for many snaps. A global hash map with linear search (C) makes get operations slow. Segment trees (D) are complex and not optimal here. Using a hash map per index with binary search (A) allows O(1) amortized set and snap, and O(log m) get, balancing time and space efficiently.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Binary search per index enables fast retrieval [OK]

Hint: Binary search per index enables fast retrieval [OK]

Common Mistakes:

• Thinking full snapshots are efficient for many snaps
• Using linear search for get causes slow queries

4. Consider the following buggy implementation of SnapshotArray. Which line contains the subtle bug that can cause incorrect get results when multiple sets occur before a snap on the same index?

import bisect

class SnapshotArray:
    def __init__(self, length: int):
        self.snap_id = 0
        self.data = [[(-1, 0)] for _ in range(length)]

    def set(self, index: int, val: int) -> None:
        # Bug here
        self.data[index].append((self.snap_id, val))

    def snap(self) -> int:
        self.snap_id += 1
        return self.snap_id - 1

    def get(self, index: int, snap_id: int) -> int:
        arr = self.data[index]
        i = bisect.bisect_right(arr, (snap_id, float('inf'))) - 1
        return arr[i][1]

medium

A. Line in snap(): incrementing snap_id before returning

B. Line in __init__(): initializing with (-1, 0) instead of (0, 0)

C. Line in set(): always appending without checking if last snap_id matches

D. Line in get(): using bisect_right instead of bisect_left

Solution

1. Step 1: Analyze set() method

   The set method always appends (snap_id, val) without checking if the last entry has the same snap_id, causing duplicate entries for the same snap_id.

2. Step 2: Consequence on get()

   Duplicate entries for the same snap_id break binary search assumptions and can cause get to return incorrect values.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Correct code replaces last entry if snap_id matches [OK]

Hint: Check if last snap_id matches before appending in set() [OK]

Common Mistakes:

• Appending blindly causes duplicates
• Misunderstanding initialization defaults

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