Leetcode Study Day 7

Insert Delete GetRandom O(1)

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.

Example 1:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

Explanation
RandomizedSet randomizedSet = new RandomizedSet();
randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomizedSet.remove(2); // Returns false as 2 does not exist in the set.
randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2].
randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly.
randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2].
randomizedSet.insert(2); // 2 was already in the set, so return false.
randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.
 

Constraints:

-231 <= val <= 231 - 1
At most 2 * 105 calls will be made to insert, remove, and getRandom.
There will be at least one element in the data structure when getRandom is called.

Use a combination of data structures

Create data structures

We use two data structures in this question, one is unordered_map, the other is vector.

private:
    unordered_map<int, int> elementToIndex;  // Map to store elements and their indices
    vector<int> elements;  // Vector to store the elements

Initialise the class

RandomizedSet() {
    // Initialize the class
    elementToIndex.clear();
    elements.clear();
}

Insert

For unordered_map, it has a function called find (value). This function returns an iterator pointing to the found element or an iterator equal to the end() of the map if the element is not found. So we use this function to make sure that the value is not in the vector. If the vlaue is already in the vector, we return false. Otherwise, we push the value to the end of the vector, and record the index of it in unordered_map.

bool insert(int val) {
    // Check if the element is already in the map, if not, add it to the vector
    if (elementToIndex.find(val) != elementToIndex.end())
        return false;
    // Return true if the element was inserted, false otherwise
    elements.push_back(val);
    elementToIndex[val] = elements.size() - 1;
    return true;
}

Remove

Similarly, we first check if the value is in the vector. If it is not, we return false.
Then we swap the element of the target value with the end element. After that, we update the index of the end element in the map. Finally, we pop the end element from the vector and erase the target element in the map and return true.

bool remove(int val) {
    // Check if the element is in the map, if not, return false
    if (elementToIndex.find(val) == elementToIndex.end())
        return false;
    // Swap the element with the last element in the vector to remove it
    int cache;
    int index = elementToIndex[val];
    cache = elements[index];
    elements[index] = elements[elements.size() - 1];
    elements[elements.size() - 1] = cache;
    // Update the map with the new index for the swapped element
    elementToIndex[elements[index]] = index;
    elementToIndex.erase(val);
    // Pop the last element from the vector
    elements.pop_back();
    // Return true
    return true;
}

Random return a value in the array

To return a value in the array randomly, we use rand() function to generate a random number between 0 and the size of the vector. Then we return the element at the index of the random number.

int getRandom() {
    // Generate a random index within the size of the vector
    if( elements.size() == 0)
        return 0;
    int randomIndex = rand() % elements.size(); 
    // Return the element at that index
    return elements[randomIndex];
}

Full code

class RandomizedSet {
public:
    RandomizedSet() {
        // Initialize the class
        elementToIndex.clear();
        elements.clear();
    }

    bool insert(int val) {
        // Check if the element is already in the map, if not, add it to the vector
        if (elementToIndex.find(val) != elementToIndex.end())
            return false;
        // Return true if the element was inserted, false otherwise
        elements.push_back(val);
        elementToIndex[val] = elements.size() - 1;
        return true;
    }

    bool remove(int val) {
        // Check if the element is in the map, if not, return false
        if (elementToIndex.find(val) == elementToIndex.end())
            return false;
        // Swap the element with the last element in the vector to remove it
        int cache;
        int index = elementToIndex[val];
        cache = elements[index];
        elements[index] = elements[elements.size() - 1];
        elements[elements.size() - 1] = cache;
        // Update the map with the new index for the swapped element
        elementToIndex[elements[index]] = index;
        elementToIndex.erase(val);
        // Pop the last element from the vector
        elements.pop_back();
        // Return true
        return true;
    }

    int getRandom() {
        // Generate a random index within the size of the vector
        if( elements.size() == 0)
            return 0;
        int randomIndex = rand() % elements.size(); 
        // Return the element at that index
        return elements[randomIndex];
    }

private:
    unordered_map<int, int> elementToIndex;  // Map to store elements and their indices
    vector<int> elements;  // Vector to store the elements
};

About Unordered_map

An unordered_map is a container in C++ that provides an associative array (or dictionary) data structure. It allows you to store key-value pairs where keys are unique, and you can quickly retrieve the corresponding values based on the keys. Here are some of the key features of std::unordered_map:

1. Fast Lookup: unordered_map provides fast lookup of values based on their keys. The time complexity for average-case lookups is O(1), which makes it suitable for applications where you need efficient access to data based on keys.

2. Unique Keys: Each key in an unordered_map is unique. This means that you cannot have multiple entries with the same key. If you attempt to insert a key that already exists, the new value will overwrite the old one.

3. Hash-Based: The underlying data structure is based on a hash table, which uses a hash function to map keys to positions in memory. This allows for efficient retrieval and insertion of key-value pairs.

4. Iterating: You can easily iterate through all the key-value pairs in an unordered_map using iterators. This is useful for performing operations on all the elements or searching for specific key-value pairs.

5. No Guaranteed Order: The key-value pairs are not guaranteed to be stored in any specific order. They are organized based on the hash values of the keys, so you may see different orderings when iterating through the map.

6. Dynamic Sizing: unordered_map dynamically resizes itself as you insert or erase elements. This ensures that it remains efficient as you add more data.

7. Custom Key Types: You can use custom types as keys as long as you provide a hash function and equality operator for those types.

Here’s a simple example of how to use unordered_map:

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> ages;

    ages["Alice"] = 30;
    ages["Bob"] = 25;
    ages["Charlie"] = 35;

    std::cout << "Alice's age: " << ages["Alice"] << std::endl;

    // Iterating through the map
    for (const auto& pair : ages) {
        std::cout << pair.first << " is " << pair.second << " years old." << std::endl;
    }

    return 0;
}

In this example, we create an unordered_map to store ages based on names. It demonstrates inserting key-value pairs, accessing values using keys, and iterating through the map.