Insert Delete GetRandom O(1) - Practice Coding Problems

Insert Delete GetRandom O(1) - Problem

Design a data structure that supports all following operations in average O(1) time.

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Input & Output

Example 1 — Basic Operations

$ Input: ["RandomizedSet","insert","remove","insert","getRandom","remove","insert","getRandom"] [[], [1], [2], [2], [], [1], [2], []]

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

💡 Note: RandomizedSet() initializes empty set. insert(1) adds 1, returns true. remove(2) tries to remove non-existent 2, returns false. insert(2) adds 2, returns true. getRandom() returns 2 (only element). remove(1) removes 1, returns true. insert(2) tries to add existing 2, returns false. getRandom() returns 2.

Example 2 — Multiple Elements

$ Input: ["RandomizedSet","insert","insert","insert","getRandom","getRandom"] [[], [1], [2], [3], [], []]

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

💡 Note: Insert three elements [1,2,3]. Each getRandom() call returns one of these elements with equal probability.

Example 3 — Edge Case Single Element

$ Input: ["RandomizedSet","insert","getRandom","remove"] [[], [5], [], [5]]

› Output: [null, true, 5, true]

💡 Note: Insert single element 5. getRandom() must return 5 (only choice). Remove 5 successfully.

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

Requirements

Need O(1) insert, remove, and getRandom operations

Challenge

Array good for random, HashMap good for insert/remove

Solution

Combine both: Array + HashMap with swap technique

Key Takeaway

🎯 Key Insight: Combine array's O(1) random access with HashMap's O(1) lookup using swap-with-last removal technique

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The optimal solution combines an array for O(1) random access with a hashmap for O(1) insert/remove operations. The key insight is using the swap-with-last technique to maintain array compactness during removal. Time: O(1) average for all operations, Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Only	O(n)	O(n)	Use hash set for O(1) insert/remove but getRandom becomes O(n)
Array Only (Brute Force)	O(n)	O(n)	Use a simple array and search linearly for insert/remove operations
Array + HashMap (Optimal)	O(1)	O(n)	Combine array for O(1) random access with hashmap for O(1) insert/remove

Hash Set Only — Algorithm Steps

Insert: Add to hash set O(1)
Remove: Remove from hash set O(1)
GetRandom: Convert set to list and pick random element O(n)

Visualization

Tap to expand

Step-by-Step Walkthrough

Hash Set

O(1) insert/remove operations

Convert

Convert set to array for random access

Random

Pick random element from array

Code -

solution.c — C

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

#define HASH_SIZE 10007

typedef struct Node {
    int val;
    struct Node* next;
} Node;

typedef struct {
    Node* buckets[HASH_SIZE];
} RandomizedSet;

int hash(int val) {
    return abs(val) % HASH_SIZE;
}

RandomizedSet* randomizedSetCreate() {
    RandomizedSet* obj = (RandomizedSet*)malloc(sizeof(RandomizedSet));
    for (int i = 0; i < HASH_SIZE; i++) {
        obj->buckets[i] = NULL;
    }
    srand(time(NULL));
    return obj;
}

int randomizedSetInsert(RandomizedSet* obj, int val) {
    int idx = hash(val);
    Node* curr = obj->buckets[idx];
    while (curr) {
        if (curr->val == val) return 0;
        curr = curr->next;
    }
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = obj->buckets[idx];
    obj->buckets[idx] = newNode;
    return 1;
}

int randomizedSetRemove(RandomizedSet* obj, int val) {
    int idx = hash(val);
    Node* curr = obj->buckets[idx];
    Node* prev = NULL;
    while (curr) {
        if (curr->val == val) {
            if (prev) {
                prev->next = curr->next;
            } else {
                obj->buckets[idx] = curr->next;
            }
            free(curr);
            return 1;
        }
        prev = curr;
        curr = curr->next;
    }
    return 0;
}

int randomizedSetGetRandom(RandomizedSet* obj) {
    int count = 0;
    for (int i = 0; i < HASH_SIZE; i++) {
        Node* curr = obj->buckets[i];
        while (curr) {
            count++;
            curr = curr->next;
        }
    }
    int target = rand() % count;
    count = 0;
    for (int i = 0; i < HASH_SIZE; i++) {
        Node* curr = obj->buckets[i];
        while (curr) {
            if (count == target) return curr->val;
            count++;
            curr = curr->next;
        }
    }
    return -1;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n)

getRandom requires converting hash set to list

✓ Linear Growth

Space Complexity

O(n)

Hash set stores n elements plus temporary list for getRandom

⚡ Linearithmic Space

89.0K Views

High Frequency

~25 min Avg. Time

2.8K 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 Set Only — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler