Insert Delete GetRandom O(1)

Solution Approach

Was this helpful?

Medium•data-structure•Expected: O(1) time, O(n) space

hash-map

Problem

Design a data structure that supports insert, delete, and getRandom operations, each in average O(1) time.

Example 1:

Input: ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
       [[], [1], [2], [2], [], [1], [2], []]
Output: [null, true, false, true, 2, true, false, 2]
Explanation: insert(1) -> true, remove(2) -> false (not found),
             insert(2) -> true, getRandom() -> 1 or 2, remove(1) -> true,
             insert(2) -> false (exists), getRandom() -> 2.

Reference solution unlocks after your first submission

Language: