Skip to main content

380. Insert Delete GetRandom O(1)

medium

Design a set that supports insert, remove, and random-element retrieval all in O(1). Neither a plain array nor a plain hash table gets you there alone — the moat is combining the two: a list for O(1) random indexing, and a hash map for O(1) lookup-by-value, kept in sync via the swap-with-last trick.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement the RandomizedSet class with these operations: RandomizedSet() initializes the object. bool insert(int val) inserts val into the set if not present, returns true if so, false otherwise. bool remove(int val) removes val from the set if present, returns true if so, false otherwise. int getRandom() returns a random element from the current set (each element must have equal probability of being returned). You must implement the functions of the class such that each function works in average O(1) time complexity.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • At most 2 * 10^5 calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

Examples

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: After inserting 1, removing 2 (not present, returns false), inserting 2, getRandom may return 1 or 2 with equal probability. After removing 1 and inserting 2 (already present), the only element left is 2.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Hash map alone — O(1) insert/remove, but iterating to a random element costs O(n).

Hint 2

Array alone — O(1) getRandom by random index, but remove is O(n) because of the shift.

Hint 3

Combine: array values[] holds the elements, map idx[val] -> position in values. To remove, swap the target with the last element, pop, and update the moved element's map entry. This keeps both structures in sync at O(1).

Solution approach

Reveal approach

Two synchronized structures. values is a dynamic array holding the current elements; idx is a hash map from val -> its index in values. insert: if val in idx return false, else append to values and record idx[val] = len(values) - 1. remove: if val not in idx return false, else (1) look up i = idx[val], (2) swap values[i] with values[-1], (3) update idx[values[i]] = i for the moved element, (4) pop values and del idx[val]. getRandom: pick a uniform random index in [0, len(values)) and return values[index]. The swap-with-last trick is the moat — it avoids the O(n) shift that plain array removal would incur.

Complexity

Time
O(1) average per operation
Space
O(n)

Related patterns

  • hash-map
  • array-design
  • swap-with-last

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • LinkedIn
  • Two Sigma

Practice these live with InterviewChamp.AI

Drill Insert Delete GetRandom O(1) and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →