Questions
54 of 59
How do you design a Data Structure that supports insert, delete, search, and getRandom in O(1)?
Difficulty: 5/10
O(1) Randomized Set
Use a dynamic array plus a hash map from value to its array index. The array provides O(1) random access and random selection. The hash map provides O(1) average lookup. For deletion, swap the element to remove with the last array element, update its index in the map, and remove the last slot.
javascript
- 1
Search: O(1) average.
- 2
Insert: O(1) amortized.
- 3
Delete: O(1) average.
- 4
getRandom: O(1).
- 5
Random selection is uniform when selecting uniformly from array indices.
Follow-up Questions
- Why can't we delete directly from the middle of an array?
- How would you support duplicates?