304 North Cardinal St.
Dorchester Center, MA 02124

# Insert Delete GetRandom O(1) LeetCode Solution

## Problem – 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.

### Insert Delete GetRandom O(1) LeetCode Solution in Java

``````public class RandomizedSet {
ArrayList<Integer> nums;
HashMap<Integer, Integer> locs;
java.util.Random rand = new java.util.Random();
/** Initialize your data structure here. */
public RandomizedSet() {
nums = new ArrayList<Integer>();
locs = new HashMap<Integer, Integer>();
}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
boolean contain = locs.containsKey(val);
if ( contain ) return false;
locs.put( val, nums.size());
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
boolean contain = locs.containsKey(val);
if ( ! contain ) return false;
int loc = locs.get(val);
if (loc < nums.size() - 1 ) { // not the last one than swap the last one with this val
int lastone = nums.get(nums.size() - 1 );
nums.set( loc , lastone );
locs.put(lastone, loc);
}
locs.remove(val);
nums.remove(nums.size() - 1);
return true;
}

/** Get a random element from the set. */
public int getRandom() {
return nums.get( rand.nextInt(nums.size()) );
}
}
``````

### Insert Delete GetRandom O(1) LeetCode Solution in C++

``````class RandomizedSet {
public:
/** Initialize your data structure here. */
RandomizedSet() {

}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
if (m.find(val) != m.end()) return false;
nums.emplace_back(val);
m[val] = nums.size() - 1;
return true;
}

/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
if (m.find(val) == m.end()) return false;
int last = nums.back();
m[last] = m[val];
nums[m[val]] = last;
nums.pop_back();
m.erase(val);
return true;
}

/** Get a random element from the set. */
int getRandom() {
return nums[rand() % nums.size()];
}
private:
vector<int> nums;
unordered_map<int, int> m;
};

``````

### Insert Delete GetRandom O(1) LeetCode Solution in Python

``````import random

class RandomizedSet(object):

def __init__(self):
self.nums, self.pos = [], {}

def insert(self, val):
if val not in self.pos:
self.nums.append(val)
self.pos[val] = len(self.nums) - 1
return True
return False

def remove(self, val):
if val in self.pos:
idx, last = self.pos[val], self.nums[-1]
self.nums[idx], self.pos[last] = last, idx
self.nums.pop(); self.pos.pop(val, 0)
return True
return False

def getRandom(self):
return self.nums[random.randint(0, len(self.nums) - 1)]
``````
##### Insert Delete GetRandom O(1) LeetCode Solution Review:

In our experience, we suggest you solve this Insert Delete GetRandom O(1) LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Insert Delete GetRandom O(1) LeetCode Solution

Find on LeetCode

##### Conclusion:

I hope this Insert Delete GetRandom O(1) LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions