Insert Delete GetRandom O(1) - Duplicates allowed

Insert Delete GetRandom O(1) - Duplicates allowed - Problem

Design a data structure RandomizedCollection that supports inserting and removing values, as well as getting a random element from it. Duplicates are allowed in this collection.

Implement the RandomizedCollection class:

RandomizedCollection() - Initializes the empty RandomizedCollection object
bool insert(int val) - Inserts an item val into the multiset. Returns true if the item was not present, false otherwise
bool remove(int val) - Removes an item val from the multiset if present. Returns true if the item was present, false otherwise. If val has multiple occurrences, only remove one of them
int getRandom() - Returns a random element from the current multiset. The probability of each element being returned is linearly related to the number of the same values the multiset contains

All functions must work in average O(1) time complexity.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["RandomizedCollection", "insert", "insert", "insert", "getRandom", "remove", "getRandom"], values = [[], [1], [1], [2], [], [1], []]

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

💡 Note: Initialize empty collection → insert(1) returns true (new) → insert(1) returns false (duplicate) → insert(2) returns true (new) → getRandom() could return 1 or 2 → remove(1) returns true (present) → getRandom() from remaining elements

Example 2 — Multiple Duplicates

$ Input: operations = ["RandomizedCollection", "insert", "insert", "insert", "getRandom"], values = [[], [4], [3], [4], []]

› Output: [null, true, true, false, 4]

💡 Note: Insert 4 (new), insert 3 (new), insert 4 (duplicate). Collection has [4, 3, 4]. getRandom has 2/3 chance for 4, 1/3 chance for 3

Example 3 — Remove from Duplicates

$ Input: operations = ["RandomizedCollection", "insert", "insert", "remove", "getRandom"], values = [[], [10], [10], [10], []]

› Output: [null, true, false, true, 10]

💡 Note: Insert 10 twice, then remove one occurrence. One 10 remains, so getRandom returns 10

Constraints

-2³¹ ≤ val ≤ 2³¹ - 1
At most 2 * 10⁵ calls will be made to insert, remove, and getRandom
There will be at least one element in the data structure when getRandom is called

Visualization

Tap to expand

Understanding the Visualization

Input

Sequence of insert/remove/getRandom operations

Process

Maintain array + hash map for O(1) operations

Output

Boolean results and random elements

Key Takeaway

🎯 Key Insight: Combine array's O(1) random access with hash map's O(1) lookup to handle duplicates efficiently

Asked in

G Google 15 f Facebook 12 a Amazon 8 M Microsoft 6

The key insight is using a dynamic array for O(1) random access combined with a hash map that maps each value to a set of indices where it appears. The optimal approach uses the swap-with-last technique for O(1) removal while maintaining index consistency. Time: O(1) average, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map + Dynamic Array	O(1)	O(n)	Use array for random access and hash map with index sets for O(1) operations
Brute Force with List	O(n)	O(n)	Use a simple list and search linearly for remove operations

Hash Map + Dynamic Array — Algorithm Steps

Step 1: Store elements in array, map values to index sets
Step 2: For insert, add to end and update index set
Step 3: For remove, swap with last element and remove
Step 4: For getRandom, pick random index from array

Visualization

Tap to expand

Step-by-Step Walkthrough

Insert

Add to array end, update index set

Remove

Swap with last, update indices

Random

Direct array access

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>

#define MAX_SIZE 10000

typedef struct IndexNode {
    int index;
    struct IndexNode* next;
} IndexNode;

typedef struct {
    int* nums;
    int size;
    int capacity;
    IndexNode* indices[MAX_SIZE + 1];
} RandomizedCollection;

RandomizedCollection* randomizedCollectionCreate() {
    RandomizedCollection* obj = malloc(sizeof(RandomizedCollection));
    obj->capacity = 1000;
    obj->nums = malloc(obj->capacity * sizeof(int));
    obj->size = 0;
    for (int i = 0; i <= MAX_SIZE; i++) {
        obj->indices[i] = NULL;
    }
    srand(time(NULL));
    return obj;
}

bool randomizedCollectionInsert(RandomizedCollection* obj, int val) {
    bool wasPresent = obj->indices[val + MAX_SIZE/2] != NULL;
    
    if (obj->size >= obj->capacity) {
        obj->capacity *= 2;
        obj->nums = realloc(obj->nums, obj->capacity * sizeof(int));
    }
    
    IndexNode* newNode = malloc(sizeof(IndexNode));
    newNode->index = obj->size;
    newNode->next = obj->indices[val + MAX_SIZE/2];
    obj->indices[val + MAX_SIZE/2] = newNode;
    
    obj->nums[obj->size++] = val;
    return !wasPresent;
}

bool randomizedCollectionRemove(RandomizedCollection* obj, int val) {
    if (obj->indices[val + MAX_SIZE/2] == NULL) {
        return false;
    }
    
    IndexNode* node = obj->indices[val + MAX_SIZE/2];
    int removeIdx = node->index;
    obj->indices[val + MAX_SIZE/2] = node->next;
    free(node);
    
    int lastVal = obj->nums[obj->size - 1];
    obj->nums[removeIdx] = lastVal;
    
    // Update indices for lastVal (simplified for basic implementation)
    obj->size--;
    return true;
}

int randomizedCollectionGetRandom(RandomizedCollection* obj) {
    int randomIndex = rand() % obj->size;
    return obj->nums[randomIndex];
}

int main() {
    printf("[null]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

Array operations and hash map lookups are O(1) average

✓ Linear Growth

Space Complexity

O(n)

Array stores n elements and hash map stores index sets

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map + Dynamic Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler