In this guide, you will get 380. Insert Delete GetRandom O(1) LeetCode Solution with the best time and space complexity. The solution to Insert Delete GetRandom O() problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
-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.
Complexity Analysis
Time Complexity: O(1)
Space Complexity: O(n)
380. Insert Delete GetRandom O(1) LeetCode Solution in C++
class RandomizedSet {
public:
bool insert(int val) {
if (valToIndex.contains(val))
return false;
valToIndex[val] = vals.size();
vals.push_back(val);
return true;
}
bool remove(int val) {
if (!valToIndex.contains(val))
return false;
const int index = valToIndex[val];
// The order of the following two lines is important when vals.size() == 1.
valToIndex[vals.back()] = index;
valToIndex.erase(val);
vals[index] = vals.back();
vals.pop_back();
return true;
}
int getRandom() {
const int index = rand() % vals.size();
return vals[index];
}
private:
unordered_map<int, int> valToIndex; // {val: index in vals}
vector<int> vals;
}; /* code provided by PROGIEZ */
380. Insert Delete GetRandom O(1) LeetCode Solution in Java
class RandomizedSet {
public boolean insert(int val) {
if (valToIndex.containsKey(val))
return false;
valToIndex.put(val, vals.size());
vals.add(val);
return true;
}
public boolean remove(int val) {
if (!valToIndex.containsKey(val))
return false;
final int index = valToIndex.get(val);
// The order of the following two lines is important when vals.size() == 1.
valToIndex.put(last(vals), index);
valToIndex.remove(val);
vals.set(index, last(vals));
vals.remove(vals.size() - 1);
return true;
}
public int getRandom() {
final int index = rand.nextInt(vals.size());
return vals.get(index);
}
// {val: index in vals}
private Map<Integer, Integer> valToIndex = new HashMap<>();
private List<Integer> vals = new ArrayList<>();
private Random rand = new Random();
private int last(List<Integer> vals) {
return vals.get(vals.size() - 1);
}
} // code provided by PROGIEZ
380. Insert Delete GetRandom O(1) LeetCode Solution in Python
class RandomizedSet:
def __init__(self):
self.vals = []
self.valToIndex = collections.defaultdict(int) # {val: index in vals}
def insert(self, val: int) -> bool:
if val in self.valToIndex:
return False
self.valToIndex[val] = len(self.vals)
self.vals.append(val)
return True
def remove(self, val: int) -> bool:
if val not in self.valToIndex:
return False
index = self.valToIndex[val]
# The order of the following two lines is important when vals.size() == 1.
self.valToIndex[self.vals[-1]] = index
del self.valToIndex[val]
self.vals[index] = self.vals[-1]
self.vals.pop()
return True
def getRandom(self) -> int:
index = random.randint(0, len(self.vals) - 1)
return self.vals[index] # code by PROGIEZ
