This is our solution and implementation to problem #380: Insert Delete GetRandom O(1) on LeetCode.
Our code is written in Java. If you want to code your solution in a different language, no worries, as the core concepts will carry over from language to language. This page includes our analysis of the problem, our implementation strategy a breakdown on the space and time complexity, and the full code implementation.
If you would like to view the original problem and solve it, please visit: Insert Delete GetRandom O(1) on LeetCode.
Problem Analysis
We need to create a custom set implementation that supports insertion, removal (retrieval), and random access, all in constant average time complexity. Commonly, a hash set or hash map is implemented using an array of linked lists, combined with a hashing function, to store elements in an array using the linked lists to handle the case that a hash function causes collisions (i.e. two elements hash to the same index). However, that approach will not allow us to access randomly in O(1) time because the lists will vary in size, so we won't be able to access truly randomly without iterating over thoses lists.
Instead, we can use extra space to record values and their positions in the array. When inserting and deleting, we can update the list and the mapped values, and upon random access, simply return a random number from 0 to the size of the array.
Implementation Strategy
We'll start off by creating variables items and valuesMap to store the actual values inserted into the set and the mapping between values and their indices in items. We'll use size to track the number of elements in our set. When we have too many items, we will resize our items array. When we insert, if the item doesn't exist in the map:
- We'll add an entry item -> size in the map.
- Set items[size] = item
- Increment size++.
When we remove items, if it exists in the set,:
- We'll get the index of the value we're trying to remove from valuesMap and store in index.
- Get the value of the last item in the array items[size-1] and store in lastItem.
- Update the map so lastItem -> index.
- Remove the deleted value from the valuesMap.
- Set items[index] = lastItem.
- Decrement size--.
With this, we have a flat array of all items, so we can call Math.random() * size to get a random element in constant time.
Space and Time Complexity
The time complexity is O(1) since each operation is done in constant time, without the need to iterate over our arrays or maps. The space complexity is O(n) since we must store every element that is added.
Additional Resources
The links below outline some of the points discussed above in more detail.
Full Code
Our solution is given in the Java code below:
All of our solutions are hosted on GitHub. The code on this page was pulled from the repo.