# Insert Delete GetRandom O(1)
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/insert-delete-getrandom-o1)
Canonical: https://scaleengineer.com/dsa/problems/insert-delete-getrandom-o(1)
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Design](https://scaleengineer.com/dsa/patterns/design), [Randomized](https://scaleengineer.com/dsa/patterns/randomized)
**Data structures:** Array, Hash Table
**Companies:** [Agoda](https://scaleengineer.com/companies/agoda), [ByteDance](https://scaleengineer.com/companies/bytedance), [Cisco](https://scaleengineer.com/companies/cisco), [Docusign](https://scaleengineer.com/companies/docusign), [DoorDash](https://scaleengineer.com/companies/doordash), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Intuit](https://scaleengineer.com/companies/intuit), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Nvidia](https://scaleengineer.com/companies/nvidia), [Palo Alto Networks](https://scaleengineer.com/companies/palo-alto-networks), [Samsung](https://scaleengineer.com/companies/samsung), [Snowflake](https://scaleengineer.com/companies/snowflake), [SoFi](https://scaleengineer.com/companies/sofi), [Yandex](https://scaleengineer.com/companies/yandex), [Yelp](https://scaleengineer.com/companies/yelp), [MakeMyTrip](https://scaleengineer.com/companies/makemytrip), [Netflix](https://scaleengineer.com/companies/netflix), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Rippling](https://scaleengineer.com/companies/rippling), [Snap](https://scaleengineer.com/companies/snap), [Pure Storage](https://scaleengineer.com/companies/pure-storage), [X](https://scaleengineer.com/companies/x), [Miro](https://scaleengineer.com/companies/miro), [Sprinklr](https://scaleengineer.com/companies/sprinklr), [Axon](https://scaleengineer.com/companies/axon), [Rubrik](https://scaleengineer.com/companies/rubrik), [Grammarly](https://scaleengineer.com/companies/grammarly), [IXL](https://scaleengineer.com/companies/ixl), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [Groupon](https://scaleengineer.com/companies/groupon), [Affirm](https://scaleengineer.com/companies/affirm), [Okta](https://scaleengineer.com/companies/okta), [ThousandEyes](https://scaleengineer.com/companies/thousandeyes), [AppFolio](https://scaleengineer.com/companies/appfolio), [Unity](https://scaleengineer.com/companies/unity), [Peloton](https://scaleengineer.com/companies/peloton), [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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.

# Approaches
## Brute Force using ArrayList
This approach uses a single `ArrayList` (or a dynamic array) to store the elements of the set. While this makes the `getRandom` operation trivial and efficient, the `insert` and `remove` operations suffer from poor performance because they require searching through the list.
**Time:** `insert`: O(N)
`remove`: O(N)
`getRandom`: O(1)

The `insert` and `remove` operations do not meet the problem's requirements for average O(1) time complexity. · **Space:** O(N), where N is the number of elements stored in the set, as we need to store each element in the `ArrayList`.
**Pros:** Simple to understand and implement.; The `getRandom` operation is highly efficient with O(1) time complexity.
**Cons:** The `insert` operation is O(N) due to the linear scan required to check for duplicates.; The `remove` operation is O(N) due to the linear scan to find the element and the subsequent shifting of elements upon removal.; Fails to meet the problem's requirement of average O(1) time complexity for all functions.
### Explanation
In this straightforward but inefficient method, we rely solely on an `ArrayList` to hold the set's elements.

- **`insert(val)`**: To insert a value, we must first ensure it's not already present to maintain the uniqueness property of a set. This involves a linear scan through the `ArrayList` using `list.contains(val)`, which takes O(N) time, where N is the number of elements. If the element isn't found, we append it to the end of the list, an operation that is amortized O(1). However, the overall complexity is dominated by the search, making it O(N).

- **`remove(val)`**: To remove a value, we again need to find its location in the list. The `list.remove(Object)` method conveniently does this, but it performs a linear search (O(N)) and, upon finding the element, may need to shift up to N-1 elements to fill the gap, resulting in an overall O(N) time complexity.

- **`getRandom()`**: This is the one efficient operation in this approach. We can get the current size of the list, generate a random index between 0 and `size - 1`, and return the element at that index. This is a constant time, O(1), operation.

```java
class RandomizedSet {
    List<Integer> list;
    Random rand;

    public RandomizedSet() {
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (list.contains(val)) {
            return false;
        }
        list.add(val);
        return true;
    }

    public boolean remove(int val) {
        // list.remove(Integer.valueOf(val)) searches for the element (O(N))
        // and then removes it (O(N)), for a total of O(N).
        return list.remove(Integer.valueOf(val));
    }

    public int getRandom() {
        int randomIndex = rand.nextInt(list.size());
        return list.get(randomIndex);
    }
}
```
### Algorithm
- Initialize an `ArrayList` `list` to store the elements.
- For `insert(val)`:
  1. Check if `list` already contains `val` by iterating through it. This is an O(N) operation.
  2. If it does, return `false`.
  3. Otherwise, add `val` to the end of `list` (amortized O(1)) and return `true`.
- For `remove(val)`:
  1. Find the element `val` in the list, which takes O(N) time.
  2. If found, remove it. This also takes O(N) time as subsequent elements need to be shifted.
  3. Return `true` if the element was found and removed, `false` otherwise.
- For `getRandom()`:
  1. Generate a random integer `randomIndex` from `0` to `list.size() - 1`.
  2. Return the element at `list.get(randomIndex)`, which is an O(1) operation.

## Optimal Approach using HashMap and ArrayList
This optimal approach cleverly combines a `HashMap` and an `ArrayList` to leverage the strengths of both data structures. The `ArrayList` stores the elements, providing O(1) time for random access (`getRandom`). The `HashMap` maps each element to its index in the `ArrayList`, enabling O(1) average time for lookups, insertions, and deletions.
**Time:** `insert`: O(1) average
`remove`: O(1) average
`getRandom`: O(1)

All operations meet the problem's time complexity requirements. `ArrayList.add` is amortized O(1), and `HashMap` operations are O(1) on average. · **Space:** O(N), where N is the number of elements in the set. We need space to store N elements in the `ArrayList` and N key-value pairs in the `HashMap`.
**Pros:** Achieves the required average O(1) time complexity for `insert`, `remove`, and `getRandom` operations.; Highly efficient and scalable for a large number of calls.
**Cons:** Requires more space than a single data structure, as elements are stored in both the list and the map.; The implementation is more complex, particularly the logic for the `remove` operation.
### Explanation
To achieve O(1) average time for all operations, we use two data structures in tandem:

- **`ArrayList<Integer> list`**: Stores the actual elements. This allows for O(1) time complexity for `getRandom()` by picking a random index.
- **`Map<Integer, Integer> map`**: Maps each element's value to its index in the `list`. This provides O(1) average time complexity for checking existence, which is crucial for `insert` and `remove`.

**Operation Details:**

- **`insert(val)`**: We first check if `val` exists by looking it up in the `map` (O(1)). If it's absent, we append `val` to the `list` and store its new index (`list.size() - 1`) in the `map`. Both steps are O(1) on average.

- **`remove(val)`**: This is the key part of the algorithm. A standard removal from an `ArrayList` index is O(N). To make it O(1), we perform a swap:
  1. Find the index of the element to remove, `indexToRemove`, from the `map` (O(1)).
  2. Take the *last element* in the `list`.
  3. Place this last element at `indexToRemove`.
  4. Update the map with the new index for the moved element.
  5. Now, remove the last element from the `list`. This is an O(1) operation.
  6. Finally, remove the original `val` from the `map`.
This sequence of O(1) operations results in an overall O(1) average time for removal.

- **`getRandom()`**: This is straightforward. We get a random index within the bounds of the current list size and return the element at that index, which is an O(1) operation.

```java
class RandomizedSet {
    private List<Integer> list;
    private Map<Integer, Integer> map;
    private Random rand;

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

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

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false;
        }

        int indexToRemove = map.get(val);
        int lastElement = list.get(list.size() - 1);

        // Move the last element to the place of the element to delete
        list.set(indexToRemove, lastElement);
        map.put(lastElement, indexToRemove);

        // Remove the last element from list and map
        list.remove(list.size() - 1);
        map.remove(val);

        return true;
    }

    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}
```
### Algorithm
- Initialize an `ArrayList` `list`, a `HashMap` `map`, and a `Random` object.
- For `insert(val)`:
  1. If `val` is already a key in `map`, return `false`.
  2. Add `val` to the end of `list`. The new index is `list.size() - 1`.
  3. Put the key-value pair `(val, new_index)` into `map`.
  4. Return `true`.
- For `remove(val)`:
  1. If `val` is not in `map`, return `false`.
  2. Get `indexToRemove` of `val` from `map`.
  3. Get `lastElement` from the end of `list`.
  4. Copy `lastElement` to `list` at `indexToRemove`.
  5. Update the index of `lastElement` in `map` to `indexToRemove`.
  6. Remove the last element from `list` (an O(1) operation).
  7. Remove `val` from `map`.
  8. Return `true`.
- For `getRandom()`:
  1. Generate a random integer `randomIndex` from `0` to `list.size() - 1`.
  2. Return the element at `list.get(randomIndex)`.

# Solutions
### CSharp

```csharp
public class RandomizedSet { private Dictionary < int , int > d = new Dictionary < int , int >(); private List < int > q = new List < int >(); public RandomizedSet () { } public bool Insert ( int val ) { if ( d . ContainsKey ( val )) { return false ; } d . Add ( val , q . Count ); q . Add ( val ); return true ; } public bool Remove ( int val ) { if (! d . ContainsKey ( val )) { return false ; } int i = d [ val ]; d [ q [ q . Count - 1 ]] = i ; q [ i ] = q [ q . Count - 1 ]; q . RemoveAt ( q . Count - 1 ); d . Remove ( val ); return true ; } public int GetRandom () { return q [ new Random (). Next ( 0 , q . Count )]; } } /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet obj = new RandomizedSet(); * bool param_1 = obj.Insert(val); * bool param_2 = obj.Remove(val); * int param_3 = obj.GetRandom(); */
```

### Java

```java
class RandomizedSet { private Map < Integer , Integer > d = new HashMap <>(); private List < Integer > q = new ArrayList <>(); private Random rnd = new Random (); public RandomizedSet () { } public boolean insert ( int val ) { if ( d . containsKey ( val )) { return false ; } d . put ( val , q . size ()); q . add ( val ); return true ; } public boolean remove ( int val ) { if (! d . containsKey ( val )) { return false ; } int i = d . get ( val ); d . put ( q . get ( q . size () - 1 ), i ); q . set ( i , q . get ( q . size () - 1 )); q . remove ( q . size () - 1 ); d . remove ( val ); return true ; } public int getRandom () { return q . get ( rnd . nextInt ( q . size ())); } } /** * 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(); */ ///////// public class Insert_Delete_GetRandom_O_1 { public static void main ( String [] args ) { Insert_Delete_GetRandom_O_1 out = new Insert_Delete_GetRandom_O_1 (); // Init an empty set. RandomizedSet randomSet = out . new RandomizedSet (); System . out . println ( randomSet . remove ( 0 )); System . out . println ( randomSet . remove ( 0 )); System . out . println ( randomSet . insert ( 0 )); System . out . println ( randomSet . insert ( 0 )); System . out . println ( randomSet . insert ( 0 )); System . out . println ( randomSet . getRandom ()); System . out . println ( randomSet . remove ( 0 )); System . out . println ( randomSet . insert ( 0 )); } class RandomizedSet { List < Integer > list ; Map < Integer , Integer > map ; // val => its index in list Random random ; /** Initialize your data structure here. */ public RandomizedSet () { list = new ArrayList <>(); map = new HashMap <>(); random = new Random (); } /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ public boolean insert ( int val ) { if ( map . containsKey ( val )) { return false ; } int pos = list . size (); list . add ( val ); map . put ( val , pos ); return true ; } /** Removes a value from the set. Returns true if the set contained the specified element. */ public boolean remove ( int val ) { if (! map . containsKey ( val )) { return false ; } // swap val to end of list, then remove it int pos = map . get ( val ); int lastVal = list . get ( list . size () - 1 ); list . set ( pos , lastVal ); list . remove ( list . size () - 1 ); map . put ( lastVal , pos ); // @note: missed this line map . remove ( val ); return true ; } /** Get a random element from the set. */ public int getRandom () { int randIndex = random . nextInt ( list . size ()); return list . get ( randIndex ); } } /** * 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(); */ }
```

### CPP

```cpp
class RandomizedSet { public: RandomizedSet () { } bool insert ( int val ) { if ( d . count ( val )) { return false ; } d [ val ] = q . size (); q . push_back ( val ); return true ; } bool remove ( int val ) { if ( ! d . count ( val )) { return false ; } int i = d [ val ]; d [ q . back ()] = i ; q [ i ] = q . back (); q . pop_back (); d . erase ( val ); return true ; } int getRandom () { return q [ rand () % q . size ()]; } private: unordered_map < int , int > d ; vector < int > q ; }; /** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */
```

### Python

```python
''' my_dict.pop('b') # vs del d[k] my_dict = {'a': 1, 'b': 2, 'c': 3} val = my_dict.pop('b') print(my_dict) # {'a': 1, 'c': 3} print(val) # 2 >>> item = my_dict.pop() Traceback (most recent call last): File "<stdin>", line 1, in <module> TypeError: pop expected at least 1 argument, got 0 >>> my_dict = {'a': 1, 'b': 2, 'c': 3} >>> del my_dict['b'] >>> my_dict {'a': 1, 'c': 3} ''' from collections import defaultdict from random import choice class RandomizedSet ( object ): def __init__ ( self ): """ Initialize your data structure here. """ # value (map) -> its index -> value (list) self . d = {} self . a = [] # introduce it purely for random def insert ( self , val ): """ Inserts a value to the set. Returns true if the set did not already contain the specified element. :type val: int :rtype: bool """ if val in self . d : return False self . a . append ( val ) self . d [ val ] = len ( self . a ) - 1 return True def remove ( self , val ): """ Removes a value from the set. Returns true if the set contained the specified element. :type val: int :rtype: bool """ if val not in self . d : return False index = self . d [ val ] # process last index/val self . a [ index ] = self . a [ - 1 ] self . d [ self . a [ - 1 ]] = index # process to be deleted index/val self . a . pop () # delete in list del self . d [ val ] # delete in dict # or, self.d.pop(val) return True def getRandom ( self ): """ Get a random element from the set. :rtype: int """ return self . a [ random . randrange ( 0 , len ( self . a ))] # return random.choice(self.a) ############ # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom() ''' >>> import random >>> random.choice([1,2,3,4,5]) 3 >>> random.choice([1,2,3,4,5]) 4 >>> random.choice([1,2,3,4,5]) 4 ''' class RandomizedSet : def __init__ ( self ): self . m = {} self . l = [] def insert ( self , val : int ) -> bool : if val in self . m : return False self . m [ val ] = len ( self . l ) self . l . append ( val ) return True def remove ( self , val : int ) -> bool : if val not in self . m : return False idx = self . m [ val ] self . l [ idx ] = self . l [ - 1 ] self . m [ self . l [ - 1 ]] = idx self . l . pop () self . m . pop ( val ) return True def getRandom ( self ) -> int : return random . choice ( self . l ) # Your RandomizedSet object will be instantiated and called as such: # obj = RandomizedSet() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()
```