[Java] Leetcode 380. Insert Delete GetRandom O(1) [Design #2]

[@arrabbi1105]

wow nice this viedo ❣️ Thanks for sharing ❣️❣️

[@eleanor8967]

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

[@EricProgramming]

That's a great tip

[@sahmbtw]

great explanation. very easy to understand. keep it up man

[@SHSelect]

easy to understand Thank you Eric

[@Joseph45758]

Insertion in map and deletion from map will also take time then how it become in O(1) time complexity?

[@EricProgramming]

O(1) on average.

[@Mathilda822]

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

[@EricProgramming]

For sure!

[@LaytoyaThomas23]

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

[@EricProgramming]

No, it takes O(1) on average. The worst care is O(n).

[@ozanservet]

Thank you for your video. Because of different getRandom values, I have a problem with this code :S This question is not make sense. private HashMap map = new HashMap(); // key = value, value = list index private List list = new ArrayList(); Random random = new Random(); public RandomizedSet() { } public boolean insert(int val) { if(map.get(val) != null) { return false; } map.put(val, list.size()); list.add(val); return true; } public boolean remove(int val) { if(map.get(val) == null) { return false; } // Move list end to be removed int listRemoveIndex = map.get(val); int listOldEndValue = list.get(list.size() - 1); list.set(listRemoveIndex, listOldEndValue); // delete list end // only deletion of last element is O(1) in ArrayList() list.remove(list.size() - 1); // update map list index map.put(listOldEndValue, listRemoveIndex); // delete from map map.remove(val); return true; } public int getRandom() { if(list.size() - 1 == 0) { return list.get(0); } return list.get(random.nextInt(0, list.size() - 1)); }