Insert Delete GetRandom O(1)

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Design a set of integers with three operations, each in O(1) average time: insert(val) adds val and returns true if it was not already present; remove(val) deletes val and returns true if it was present; getRandom() returns a uniformly random element of the current set. getRandom is only called when the set is non-empty.

    A favorite "combine two structures" design question: each obvious structure gives you two of the three operations, and the trick is a small swap that gets you the third. Original problem: LeetCode 380.

    Example

    Inserting 20 a second time fails; after removing 10, getRandom must return 20 or 30 with equal chance.
    Inserting 20 a second time fails; after removing 10, getRandom must return 20 or 30 with equal chance.
    insert(10) -> true
    insert(20) -> true
    insert(30) -> true
    insert(20) -> false       # already there
    remove(10) -> true
    getRandom() -> 20 or 30, each with probability 1/2

    Constraints (assumed)

    • Up to 2 × 10⁵ calls; values fit in a 32-bit integer.

    What this question tests

    • Knowing what each structure gives: a hash map finds a value, an array allows random access by index.
    • The swap-with-last trick that removes from the middle of an array in O(1).
    • Keeping two structures consistent, including the edge case where they overlap.

    Questions to ask first

    1. Are duplicates allowed? (Here: no, it is a set. With duplicates it becomes the follow-up.)
    2. Must getRandom be exactly uniform? (Here: yes.)
    3. Does the order of elements matter? (No, which is what makes the swap legal.)
    4. Is "O(1)" average or worst case? (Average; hash maps are O(1) on average.)