Insert Delete GetRandom O(1)

Insert delete getrandom o 1 requires a structure supporting insert, remove, and uniform random selection, all in average O(1). No single built-in structure provides all three, which is the whole point. A hash set gives O(1) insert and remove but cannot pick a uniform random element — its storage has no index. An array gives O(1) random access by index but O(n) removal, since deleting from the middle shifts everything after it. Combining them covers both weaknesses: - Keep an array of the values and a map from each value to its index in that array. Random selection then picks a random array index directly. Insertion appends to the array and records the new index in the map. Removal is the operation that makes this work, and it turns on one trick: Swap the element being removed with the last element, then pop the array. Removing from the end is O(1), and the swap moves the doomed element there. The map must then be updated so the moved element points at its new index. The order matters — update the moved element's index in the map, then delete the removed value's entry. Reversing those steps corrupts the map when the removed element is the last one, since the swap is then a no-op and the update would resurrect a deleted key. The array order is destroyed by these swaps, which is acceptable because the problem never requires order — only membership and uniform sampling.

Constant-time membership and deletion suggest hashing, while uniform random selection suggests a dense indexable array. When both are required, store value-to-index mappings and use swap-delete to prevent gaps and shifts.