# Insert Delete GetRandom O(1)

## Solving Leetocode 380 in JavaScript

Photo by Jacob Van Blarcom on Unsplash

When it comes to designing data structures, one often seeks optimal solutions that offer efficient operations. In this article, we will explore the approach to tackling this problem using JavaScript.

### Problem Statement:

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.

**Approach:**

For this problem, we need to make `insert`

, `remove`

, and `getRandom`

all to O(1) time complexity, so it's straightforward to think about using a map. With a map, we could implement the `insert`

and `remove`

easily with O(1) time complexity. But how about `getRandom`

?

Let’s take a look at what operations do we need for the `getRandom`

method:

Get a random number.

Get the real value according to that random number.

Looks like it’s pretty easy, right? We could get a random number by `Math.random`

, and use an array to store index-based values.

But when we try to finish the code, we may find the `remove`

method could not be easy, since if we use something like `splice`

to remove the value in an array, it could be not O(1) depends on the implementation, and all the indexes after this element need to be updated.

So, here comes the final key point for this problem, how do we make it O(1) with steady indexes? Let’s list some clues:

If we want steady indexes, then we can’t remove this element from the list. We must put a value here.

If we wanna remove a value with O(1) in a list, it’s straightforward to think about removing the last value.

Combined with these clues, it is not difficult for us to find out that we could swap the target value and the last value, then remove it. This could meet our two needs at the same time.

At this moment, the whole strategy is clear, so the next step is just coding:

```
// ES6 Arrow Function
class RandomizedSet {
constructor() {
this.map = new Map();
this.list = [];
}
insert(val) {
if (this.map.has(val)) return false;
this.map.set(val, this.list.length);
this.list.push(val);
return true;
}
remove(val) {
if (!this.map.has(val)) return false;
const idx = this.map.get(val);
this._swap(idx, this.list.length - 1);
this.list.pop();
this.map.set(this.list[idx], idx);
this.map.delete(val);
return true;
}
getRandom() {
return this.list[Math.floor(Math.random() * this.list.length)];
}
_swap(a, b) {
const tmp = this.list[a];
this.list[a] = this.list[b];
this.list[b] = tmp;
}
}
```

#### Time Complexity:

Insertion: O(1)

Deletion: O(1)

Get Random: O(1)

#### Space Complexity: O(N)

N is the number of elements stored in the data structure. The array `this.list`

stores the elements, and the hash map `this.map`

stores the mapping of elements to their indices.

**Note:** The credit for this solution goes to **PoppinL****.** Her detailed answer on leetcode helped me understand this problem better.

I hope this article has provided you with valuable insights and helped you better understand the approach to solve this problem. Happy coding!

Problem - Leetcode 380