Insert Delete GetRandom O(1)

LeetCode Problem #380 (Medium)

Problem Statement

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

insert(val): Inserts an item val to the set if not already present.

remove(val): Removes an item val from the set if present.

getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Prerequisite Knowledge

O(1) Time Complexity

O(1) time complexity is also referred to as constant time. If an operation is said to be performed in constant time, it means that irrespective of the size of the data set within which the operation is performed, the time taken to accomplish the task will be constant.

To illustrate, let us consider an array of size 5. To find an element in this array, we assume that it takes 1 second. If we double the size of the array to contain 10 elements and if we want to search for an element now, it would take the same 1 second to find the element, if this operation is designed to execute in constant time.

Big-O Complexity Chart

As shown in the chart below, O(1) is the most ideal time complexity that a particular operation could have, since the increase in the number of elements in a data set will not affect the performance of the operation.

Source: https://www.bigocheatsheet.com/

Example

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

Algorithm

Initialize a vector to store all of the elements.

Initialize a map to track the key and value of every element.

Insert

1. Check the array to see if the value to be inserted exists or not.

2. If the value does not exist, using the emplace() method, insert the value and its position in the map only if it is unique.

3. Add the value to the array.

Delete

1. Check the array to see if the value to be removed exists or not.

2. If the value exists, obtain the index of the value from the map and store it in a variable.

3. Move the element to be removed to the back of the array and remove it from the array.

4. Change the index value in the map to the correct value and remove the value from the map.

GetRandom

1. Calculate the index of the element to return by performing taking a random number and performing modulus with the size of the array.(This is to prevent the index from going out of bounds.)

2. Access the element at the calculated index from the vector.

Time Complexity: O(1)

Code

Array and Map Initialization

vector<int> arr;vector<int> arr;
unordered_map<int, int> map;

Insert

bool insert(int val) {
    // The iterator finds the value before reaching the end of the map
    if(map.find(val) != map.end()) {
        return false;
    }
    // Insert a value into the map only if it is unique
    map.emplace(val, arr.size());
    // Insert this value into the array
    arr.push_back(val);
    return true;
}

Delete

bool remove(int val) {
    // The iterator does not find the value before reaching the end of the map
    if(map.find(val) == map.end()) {
        return false;
    }
    // Initialize an index to store the position of the value
    int index = map[val];
    
    // Moving the element to be removed to the back of the array
    arr[index] = arr.back();
    // Removing the last element in the array
    arr.pop_back();
    
    // Change the value in the map to the correct index value
    map[arr[index]] = index;
    // Remove the value
    map.erase(val);
    return true;
}

GetRandom

int getRandom() {
    // Calculate the index of the random element and return it        
    int index = rand() % arr.size();
    return arr[index];
}