# A solution to LeetCode Problem 380. Insert Delete GetRandom O(1) in JavaScript

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.

### Solution

**JavaScript Map object**and an array to implement this data structure. The Map object will allow us to store the values and their indices in the array, and the array will allow us to easily implement the

**.**

*getRandom() function***, we can simply add the value to the end of the array and store its index in the Map object. If the value already exists in the Map, we can return false.**

*insert() function***, we can remove the value from the Map and swap it with the last element in the array. This will allow us to maintain the O(1) time complexity for both insert and remove.**

*remove() function***, we can simply return a random element from the array using the**

*getRandom() function***.**

*Math.random() function***RandomizedSet**class:

```
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 index = this.map.get(val);
this.map.delete(val);
if (index < this.list.length - 1) {
// If the element is not the last element, move the last element to its place
const last = this.list[this.list.length - 1];
this.list[index] = last;
this.map.set(last, index);
}
this.list.pop();
return true;
}
getRandom() {
return this.list[Math.floor(Math.random() * this.list.length)];
}
}
```

The time complexity of the updated solution is still O(1) for all three operations: insert, remove, and ** getRandom()**.

The ** insert()** operation has a time complexity of O(1), because it simply adds a new element to the end of the array and sets a value in the map. Both of these operations have constant time complexity.

The ** remove()** operation has a time complexity of O(1) in the worst case, because it involves deleting a value from the map and replacing an element in the array with the last element in the array. Both of these operations have constant time complexity. In the worst case, the element being removed is not the last element in the array, so the remove operation also involves updating the map and the value of the last element in the array. However, these operations also have constant time complexity, so the overall time complexity of the remove operation remains O(1).

The ** getRandom()** operation has a time complexity of O(1), because it involves generating a random number within the range of the array's indices and then accessing an element at that index. Both of these operations have constant time complexity.

Overall, the updated solution has a time complexity of O(1) for all three operations, which means that the time taken to perform these operations does not depend on the size of the input.

## No comments:

## Post a Comment