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

[@ishaankalia8049]

this question can also be done using just only unordered_map 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?

[@haidarmohammad8510]

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 explain...........

[@aruneshsrivastava7154]

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()

[@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() ??

[@techdose4u]

I don't think this will work because SET is maintained in a self balanced BST without caring about ordering (unordered_set) and so, you can get any orientation of set when you insert a new element which will minimize time. If have not gone through how the indexing is done in unordered_set but I think that will not be random. I have to check it otherwise you can create million random entries and pick the 1st element in a predefined unordered_set and see the distribution graph.

[@shobhitmittal77]

Solution starts at 8.30

[@sudhanshukumar1558]

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 👍

[@techdose4u]

You can read about implementation of conversion to list. It's avg time must be greater than O(1).

[@ShreyaSingh-vr9qi]

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; }

[@techdose4u]

👍

[@ashutoshtiwari4719]

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

[@agileprogramming7463]

Awesome as always!

[@techdose4u]

Thanx :)

[@kunalsoni7681]

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

[@techdose4u]

Welcome

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

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

[@techdose4u]

It is O(1) on avg. Worst case is O(logN) because we are storing numbers encountered in map. Question says about avg and not worst case :)

[@mehulvarshney3389]

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

[@akshataggarwal3277]

Stack

[@eshaanpandey7353]

Nice Explanation

[@HimanshuSingh-ob9qo]

Nice explanation

[@techdose4u]

Thanks :)

[@PankajGupta-gh9cm]

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

[@awwsumkush8581]

In java arraylist is implemented as array so under the hood the left shift will happen

[@techdose4u]

If this is true then you can't just use array list. Simply use a combination of array and map as I shown.

[@Yash-uk8ib]

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

[@amitavamozumder73]

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)

[@ASocial093]

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

[@techdose4u]

No book.

[@MohitBhagwani94]

@@techdose4u Then how your concepts are so solid? what did you do?

[@techdose4u]

I just search and study on internet as I had no time to go through books. Everything is already available on the Net. Keep searching as you wish.

[@topcoder3812]

@@techdose4u Sir ,App kaha se preparation kiye the coding interview ke liye . Aap ka concept is very well. Please Sir..

[@shyamprakashm6325]

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

[@techdose4u]

No. Maximum logN time.

[@shyamprakashm6325]

@@techdose4u 🙄🙄 how does it take log n time.could you explain it me? Please

[@techdose4u]

Elements are stored in balanced binary search tree. In a BST, you can search KEY in just O(logN) when it is balanced.

[@shyamprakashm6325]

Thanks

[@techdose4u]

Welcome :)

[@yjj410]

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)

[@yash_renaissance_athlete]

this is a great approach. the same one came to my mind too

[@sagargupta1615]

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

[@RCVISHNUVardhan]

I have implemented the same thing with only dictionary( C# ) or insertion and deletion will be O(1) but for getting random number i am using like dictionary.keys.ToArray(). Converting dictionary keys to array Is this fine!!!! Or the code for getting random is not correct!!!

[@techdose4u]

It won't be correct because get Random is O(N) here. You need O(1) avg for all operations.

[@RCVISHNUVardhan]

@@techdose4u Ok , Thank you.

[@rohithkumartangudu4664]

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.

[@techdose4u]

Ummm....you should have tried to implement everything in O(1) avg. If you take one operation to be O(1) then the problem will not be challenging at all 😅

[@rohithkumartangudu4664]

@@techdose4u Yes I also agree. But I did not observed the time clearly.Thats why I implemented like that.

[@hritiksharma7154]

Sir from where should I c++ could you recommend me any course

[@techdose4u]

Ummm....You can pick any CPP book and read but I never read any book so can't really recommend 😅 You can do what I did. Just search the net whenever you are not able to understand something. This way you will learn. Books won't cover everything and I find it very boring too 😅

[@thadpadvines5212]

Which software u used in video editing, can u please tell..

[@jnaneswarreddy8125]

good explanation..... can i know how to implement if dupilcates are allowed

[@manthankhorwal1477]

That will be a different question ... Here we need probability to get every number should be same

[@techdose4u]

You can take map of vector and maintain same element index in ASC order. You can apply binary search to search for index or linear search to access them all.

[@AA-rg1mv]

Thanks a lot sir!

[@techdose4u]

Welcome :)

[@lovleshbhatt7797]

You didn't clear the map and vector then how you set AC, I got WA if I am not using clear commands for both vec and map

[@techdose4u]

If you declared variables inside class then for different objects, the space allocated is totally different. So, it doesn't matter whether you clear it or not. I wrote thinking this and it got accepted. If you make variables global then you will have to clear it everytime an object is created.

[@PUNEETRAIPURIA]

sir can you explain Red-Black tree in future video? thank you in advance

[@techdose4u]

Obviously YES. But it will take long time before I reach there. I am first planning on finishing the basic concepts. I want to maintain order. Teaching from here and there won't be useful in the long run.

[@ashutoshbhadauriya7423]

Can't we use unordered set?

[@AyushGupta-mm4jg]

getRandom would be O(n)

[@kushagrajain2407]

Hey , I followed your approach and wrote my code in Kotlin and passed the Sample test case but getting an index out of Bound error on submission. I can't seem to figure out the Error in my code. Can anyone have a look at it and let me know. Thanks in advance :) Error: Line 26: Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3358, Size: 2141 Code: import kotlin.random.Random class RandomizedSet() { /** Initialize your data structure here. */ var map = hashMapOf() val elements: MutableList = mutableListOf() var count = 0 /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */ fun insert(`val`: Int): Boolean { if(`val` in map.keys){ return false } else{ elements.add(`val`) map[`val`] = elements.size-1 return true } } /** Removes a value from the set. Returns true if the set contained the specified element. */ fun remove(`val`: Int): Boolean { if(`val` in map.keys){ if(elements.size >1){ var index = map[`val`] var key = elements[elements.size-1] elements[index!!] = key //Error in this line elements.removeAt(elements.size-1) map.remove(`val`) map[key] = index!! } else{ var index = map[`val`] elements.removeAt(index!!) map.remove(`val`) } return true } else{ return false } } /** Get a random element from the set. */ fun getRandom(): Int { return(elements.random()) } }

[@MrArpit1234]

you have not added bounds to random function return rand()%size()

[@HimanshuSingh-ob9qo]

👍

[@techdose4u]

👍

[@HimanshuSharma-tm2ms]

please add "find median of two sorted arrays of different sizes" to your list:)

[@kavyap7113]

too many ads , hard to follow

[@sonuagarwal7679]

Code will crash when we will have only one element and we need to remove that..

[@arpit5506]

noise