visual walkthrough
Insert Delete GetRandom O(1)
Combining two structures to get O(1) for everything; a top design question.
The idea
A hash map gives O(1) insert and delete but can't pick a random element; an array can pick a random element but is slow to delete from the middle. Keep both.
To delete in O(1), copy the last element over the one being removed, update its index in the map, and pop the end. Order doesn't matter, so nothing needs shifting.
Complexity
| approach | time | space |
|---|---|---|
| Array only | O(n) remove | O(n) |
| Array + map | O(1) each | O(n) |