Design data structure | Insert Delete GetRandom O(1) | Leetcode #380

This video explains a very important design based programming interview problem which is to design a data structure where INSERT, DELETE and GET-RANDOM can be performed in just O(1) average time.The implemented data structure will be just like a SET where we can't have duplicates.I have explained 3 intuitive data structures which can be chosen to solve thisproblem.The most intuitive data structure is array or vector but DELETE operation is O(N) for array.The next intuitive data structure is SET but GET RANDOM is O(N) for it.The third intuitive data structure is a doubly linked list where DELETE and GET-RANDOM operations are both O(N). The problem is to access elements by value in just O(1). Array has O(1) random access by index but not by value.The idea for this is to store the address or index of every element in a MAP where key is element itself and value is the index where the element is located.This problem can be solved by using ARRAY+MAP or Doubly Linked List + MAP but array implementation is easier and so i have shown that implementation using example.At the end of the video,i have shown the code walk through.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

=================================================================
=================================================================

SIMILAR PROBLEMs:-

[ishaankalia]

this question can also be done using just only unordered_map<int, bool> the extra functionality to generate the random number would be using an srand(time(NULL)) function within your class contructor

[shalsteven]

10:53 why we need to remove the last element? Just to clear the storage?

[aruneshsrivastava]

If you use an arraylist, in place of normal list, i think that can internally take care of shifting the elements
when you call arraylist.remove()

[haidarmohammad]

Sir, Why you are not inserting 3 twice in the array because in the problem structure it is given that we can insert dublicate numbers. Please

[ashutoshtiwari]

Thank You !! The question was simple only the way it was portrayed was confusing 😅😅

[kunalsoni]

Helpful video too much 😇😊.
Thank you so much sir

[ShreyaSingh-vrqi]

Nice solution !!
I think there is no use of auto it : map.find(), we can simply do like this :-

bool remove(int val) {

if(!mp.count(val))
return false;

mp[v.back()]=mp[val];
swap(v.back(), v[mp[val]]);

v.pop_back();
mp.erase(val);

return true;
}

[sudhanshukumar]

In python I used a dictionary to insert and delete values, for get random I used randint() to get a random number and returned the list(keys of dict)[random number]

Insert and delete are O(1), not sure if get random is O(1) or not. Thanks for sharing your solutions for this one 👍

[jaybibodi]

In 2nd approach (Using set), why can't we return the first element everytime for getRandom()? Definition of getRandom in the problem is "Returns a random element from current set of elements. Each element must have the same probability of being returned." So ideally it is not necessary we use Random library to generate random number. What if we consider 1st element in the set as the random element and extract using set.iterator.next() ??

[Yash-ukib]

why do we need update the index incase of deletion, we are not interested for its index right?

[PankajGupta-ghcm]

can we use ArrayList instead of the array so that we don't need to copy the last element instead we directly remove from the map and also from ArrayList since after removing element its size decreases so there will be no problem for generating the random elements

[ASocial]

You were from Metallurgy. So, which books did you read for Programming C++ that you knew it so well.

[mehulvarshney]

Design an efficient Data Structure for the following operations.

1) findMin() :
2) findMax() :
3) deleteMin() :
4) deleteMax() :
5) Insert() :
6) Delete() :

kindly help in this question, I heard map over some heap solution but couldn't find it

[sagargupta]

Using array and hashmap we can als search item in o( 1) only

[shyamprakashm]

To check into the map whether the key is present or not .it does take o(n) time doesn't it?

[jnaneswarreddy]

good can i know how to implement if dupilcates are allowed

[АлишерХасен-кю]

The 1st method by using vector insertion will not be O(1) because you should know if you already have this number or not

[yjj]

my python implementation. I used dict and list both. Dict maps value of item to index of item in the list. To get random item, i just used random.choice() on list.
class RandomizedSet:

def __init__(self):
"""
Initialize your data structure here.
"""
self.data_key = {}
self.data = []


def insert(self, val: int) -> bool:
"""
Inserts a value to the set. Returns true if the set did not already contain the specified element.
"""
if val in self.data_key:
return False
self.data.append(val)
self.data_key[val] = len(self.data) - 1
return True



def remove(self, val: int) -> bool:
"""
Removes a value from the set. Returns true if the set contained the specified element.
"""
if val not in self.data_key:
return False
ind = self.data_key[val]
self.data_key[self.data[-1]] = self.data_key[val]
del self.data_key[val]
self.data[ind] = self.data[-1]
self.data.pop()
return True


def getRandom(self) -> int:
"""
Get a random element from the set.
"""
return random.choice(self.data)

[amitavamozumder]

why do we need an array or vector, the map it self can hold the value, we do insert, delete, find everything in the map itself, right? all are O(1)

[rohithkumartangudu]

I got idea and solved using hashset in java and the solution is also accepted. Is there any problem with this solution??Even though I know getrandom function takes o(n) time.