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.

For example:

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.

# RandomizedSet Implementation

## Problem Description

We need to implement a `RandomizedSet` data structure that supports the following operations with an average time complexity of O(1):

*   **insert(val):** Inserts an item `val` into the set if not present. Returns `true` if the item was not present, `false` otherwise.
*   **remove(val):** Removes an item `val` from the set if present. Returns `true` if the item was present, `false` otherwise.
*   **getRandom():** Returns a random element from the current set of elements. Each element must have the same probability of being returned.

## Naive Solution

A naive approach would be to use a standard `Set` data structure. The `insert` and `remove` operations would take O(1) on average. However, `getRandom` would require converting the set to an array, which takes O(n) time, where n is the number of elements in the set.

## Optimal Solution

To achieve O(1) average time complexity for all operations, we can use a combination of a `List` and a `HashMap`.

*   The `List` will store the elements of the set.
*   The `HashMap` will store the value and its index in the `List`.

### Data Structures

*   `ArrayList<Integer> list`: Stores the elements of the set.
*   `HashMap<Integer, Integer> map`: Stores the value and its index in the list.

### Algorithm

*   **insert(val):**
    *   Check if the value is already present in the map.
    *   If present, return `false`.
    *   If not present, add the value to the end of the list and add the value and its index to the map.
    *   Return `true`.
*   **remove(val):**
    *   Check if the value is present in the map.
    *   If not present, return `false`.
    *   If present, get the index of the value from the map.
    *   Get the last element from the list.
    *   Replace the element at the index with the last element.
    *   Update the index of the last element in the map.
    *   Remove the last element from the list and remove the value from the map.
    *   Return `true`.
*   **getRandom():**
    *   Generate a random index between 0 and the size of the list.
    *   Return the element at the random index.

### Code Implementation (Java)

```java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

class RandomizedSet {
    private ArrayList<Integer> list;
    private HashMap<Integer, Integer> map;
    private Random random;

    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false;
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }
        int index = map.get(val);
        int lastElement = list.get(list.size() - 1);
        list.set(index, lastElement);
        map.put(lastElement, index);
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

Big(O) Runtime Analysis

• insert(val): O(1) on average because HashMap.containsKey() and ArrayList.add() take O(1) time on average.
• remove(val): O(1) on average because HashMap.containsKey(), HashMap.get(), ArrayList.set(), HashMap.put(), and ArrayList.remove() take O(1) time on average.
• getRandom(): O(1) because Random.nextInt() and ArrayList.get() take O(1) time.

Big(O) Space Usage Analysis

• O(n) where n is the number of elements in the set. This is because we store the elements in an ArrayList and a HashMap.

Edge Cases

• Inserting the same value multiple times: The insert method handles this case by checking if the value is already present in the map before adding it.
• Removing a value that is not present: The remove method handles this case by checking if the value is present in the map before removing it.
• Calling getRandom on an empty set: The problem statement guarantees that there will be at least one element in the data structure when getRandom is called, so we don't need to handle this case.