LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed Solution in Python – A Step-by-Step Guide

Imagine you’re building a data structure that needs to insert, delete, and randomly select elements—all in constant time, O(1)—but now it must handle duplicate values, unlike its predecessor. That’s the challenge of LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed, a medium-level problem that extends LeetCode 380 by allowing duplicates. Using Python, we’ll explore two solutions: the Best Solution—a list and dictionary with sets for O(1) efficiency—and an Alternative Solution—a simpler list-based approach with O(n) removal. With examples, clear code breakdowns, and a friendly vibe, this guide will help you manage that random set. Let’s get started!

What Is LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed?

LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed asks you to implement a RandomizedCollection class that supports inserting, deleting, and randomly selecting elements in O(1) average time, with the added complexity of allowing duplicate values. Each element should have an equal probability of being returned by getRandom. It’s a design problem that tests your ability to adapt fast operations to handle multiplicity!

Problem Statement

Class: RandomizedCollection

Methods:

__init__(): Initialize an empty collection.
insert(val): Insert val, return True if not present, False if already present.
remove(val): Remove one instance of val, return True if present, False otherwise.
getRandom(): Return a random element with equal probability.

Rules:

All operations must be O(1) average time.
Duplicates are allowed; getRandom must account for frequency.

Constraints

-2³¹ <= val <= 2³¹ - 1
At most 2 * 10⁵ calls to insert, remove, and getRandom.
At least one element exists when getRandom is called.

Examples

Input: ["RandomizedCollection","insert","insert","insert","getRandom","remove","getRandom"], [[],[1],[1],[2],[],[1],[]]

Output: [null,true,false,true,1 or 2,true,1 or 2]

Init: [].
insert(1): [1], True.
insert(1): [1,1], False (duplicate).
insert(2): [1,1,2], True.
getRandom(): 1 or 2 (1 has 2/3 chance, 2 has 1/3).
remove(1): [1,2], True.
getRandom(): 1 or 2 (1/2 chance each).

Input: ["RandomizedCollection","insert","remove","insert"], [[],[1],[1],[1]]

Output: [null,true,true,true]

Init: [], insert(1): [1], remove(1): [], insert(1): [1].

These show the duplicate twist—let’s solve it!

Understanding the Problem: O(1) with Duplicates

To tackle LeetCode 381 in Python, we need a class that: 1. Inserts values (duplicates allowed) in O(1). 2. Removes one instance of a value in O(1). 3. Returns a random element in O(1) with probability proportional to frequency.

A set alone won’t work with duplicates or O(1) random access. We’ll use:

Best Solution: List and dictionary with sets—O(1) average time, O(n) space—fast and robust.
Alternative Solution: List with linear removal—O(n) remove, O(1) others—simpler but slower.

Let’s optimize with the best solution!

Best Solution: List and Dictionary with Sets

Why This Is the Best Solution

The list and dictionary with sets approach achieves O(1) average time for all operations by:

Using a list to store elements (enabling O(1) random access).
Using a dictionary mapping values to sets of indices (enabling O(1) lookup and removal).

It’s the most efficient—handling duplicates and ensuring uniform randomness with minimal overhead!

How It Works

Think of it like a phone book with multiple entries:

List: Stores all values in insertion order.
Dictionary: Maps each value to a set of its indices in the list.
Init: Empty list and dictionary.
Insert: Append to list, add index to value’s set.
Remove: Swap with last element, update sets, pop last.
GetRandom: Pick random index from list.

It’s like tracking duplicates with a fast lookup!

Step-by-Step Example

For calls: insert(1), insert(1), insert(2), getRandom(), remove(1), getRandom():

Init: List = [], Dict = {}.
insert(1):

List = [1], Dict = {1: {0}}, return True.

insert(1):

List = [1, 1], Dict = {1: {0, 1}}, return False.

insert(2):

List = [1, 1, 2], Dict = {1: {0, 1}, 2: {2}}, return True.

getRandom():

List = [1, 1, 2], random index → 1 (2/3 chance) or 2 (1/3 chance).

remove(1):

Dict[1] = {0, 1}, pick 1, last = 2 (index 2).
Swap: List = [1, 2, 1], Dict = {1: {0}, 2: {1}}.
Pop: List = [1, 2], Dict = {1: {0}, 2: {1}}, return True.

getRandom():

List = [1, 2], 1 or 2 (1/2 chance each).

For insert(0), insert(0), remove(0):

Init: List = [0], Dict = {0: {0}}.
insert(0): List = [0, 0], Dict = {0: {0, 1}}.
remove(0): Swap 0 (index 1) with 0 (index 1), pop: List = [0], Dict = {0: {0}}.

Code with Explanation

Here’s the Python code using a list and dictionary with sets:

import random

class RandomizedCollection:
    def __init__(self):
        # List for values, dict mapping values to set of indices
        self.values = []
        self.val_to_indices = {}

    def insert(self, val: int) -> bool:
        # Insert value, return True if not present before
        self.values.append(val)
        if val not in self.val_to_indices:
            self.val_to_indices[val] = set()
            was_empty = True
        else:
            was_empty = False
        self.val_to_indices[val].add(len(self.values) - 1)
        return was_empty

    def remove(self, val: int) -> bool:
        # Remove one instance of val
        if val not in self.val_to_indices or not self.val_to_indices[val]:
            return False

        # Get index to remove and last value
        remove_idx = self.val_to_indices[val].pop()
        last_val = self.values[-1]

        # Swap with last element if not already last
        if remove_idx != len(self.values) - 1:
            self.values[remove_idx] = last_val
            self.val_to_indices[last_val].remove(len(self.values) - 1)
            self.val_to_indices[last_val].add(remove_idx)

        # Remove last element
        self.values.pop()
        if not self.val_to_indices[val]:
            del self.val_to_indices[val]
        return True

    def getRandom(self) -> int:
        # Return random element from list
        return random.choice(self.values)

Explanation

Lines 5-7: __init__:

values: List for all elements.
val_to_indices: Dict mapping values to sets of indices.

Lines 9-17: insert:

Append val to list, add index to set.
Return True if val wasn’t in dict—O(1).

Lines 19-34: remove:

If val not in dict or set empty, return False.
Pop an index from val’s set, swap with last, update sets, pop—O(1).
Clean up empty set in dict.

Lines 36-38: getRandom:

Random.choice from list—O(1).

Time: O(1) average for all operations.
Space: O(n)—list and dict store n elements.

This is like a duplicate-friendly randomizer—fast and fair!

Alternative Solution: List with Linear Removal

Why an Alternative Approach?

The list-based solution with linear removal offers O(1) insert and getRandom but O(n) remove by scanning for the value to delete. It’s simpler—great for small datasets or understanding a basic approach, though it doesn’t meet the full O(1) requirement!

How It Works

List: Store all values.
Insert: Append value.
Remove: Find and remove first occurrence.
GetRandom: Pick random index.

Step-by-Step Example

For insert(1), insert(1), remove(1):

Init: List = [].
insert(1): List = [1], True.
insert(1): List = [1, 1], True (duplicates allowed).
remove(1): Scan, remove first 1, List = [1], True (O(n)).

Code with Explanation

import random

class RandomizedCollection:
    def __init__(self):
        self.values = []

    def insert(self, val: int) -> bool:
        self.values.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.values:
            return False
        self.values.remove(val)  # Removes first occurrence
        return True

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

Explanation

Line 5: __init__: Empty list.
Lines 7-9: insert: Append val—O(1).
Lines 11-14: remove: Remove first val—O(n).
Lines 16-17: getRandom: Random.choice—O(1).
Time: O(1) insert/getRandom, O(n) remove.
Space: O(n)—list.

It’s a simple randomizer with slow removal!

Comparing the Two Solutions

List and Dict with Sets (Best):

Time: O(1) average—all operations.
Space: O(n)—list and dict.
Pros: True O(1), handles duplicates.
Cons: More complex.

List with Linear Removal (Alternative):

Time: O(1) insert/getRandom, O(n) remove.
Space: O(n)—list.
Pros: Very simple.
Cons: Remove fails O(1) requirement.

List and dict win for full O(1) compliance!

Additional Examples and Edge Cases

Empty: getRandom not called (per constraint).
All duplicates: Best handles frequency, alternative works but slow.
Single element: Both return it.

Best solution is robust, alternative lags on remove.

Complexity Breakdown

List and Dict:

Time: O(1) average.
Space: O(n).

List Linear:

Time: O(1) insert/getRandom, O(n) remove.
Space: O(n).

List and dict excel for all ops.

Key Takeaways

List and Dict: Full O(1)—fast and flexible!
List Linear: Partial O(1)—simple but slow remove!
Randomness: Design balances speed and chance.
Python Tip: Dicts rock—see [Python Basics](/python/basics).

Final Thoughts: Randomize with Duplicates

LeetCode 381: Insert Delete GetRandom O(1) - Duplicates Allowed in Python is a design challenge with a duplicate twist. List and dictionary with sets is the efficiency champ, while list with linear removal offers simplicity at a cost. Want more? Try LeetCode 380: Insert Delete GetRandom O(1) or LeetCode 146: LRU Cache. Ready to juggle? Visit Solve LeetCode 381 on LeetCode and manage those numbers today!