How to Solve Insert Delete GetRandom O(1)

To solve Insert Delete GetRandom O(1), maintain a dynamic array for element storage and a hash map for index tracking. Insertions and deletions update both structures in constant time. Random access is efficient by picking a random index from the array, ensuring average O(1) complexity for all operations.

Problem Statement

Design a RandomizedSet data structure that supports insertion, deletion, and random retrieval of elements. Implement insert(val) to add val if not present, remove(val) to delete val if present, and getRandom() to return a random element from the set.

All functions must operate in average O(1) time. Ensure that getRandom() returns each existing element with equal probability. Input values will be in the range [-231, 231 - 1], and the structure may receive up to 2 * 105 function calls.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2]

Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2.

Constraints

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

Solution Approach

Use Array with Hash Map for Index Tracking

Store elements in an array for random access and maintain a hash map that maps each value to its index in the array. This allows quick lookup to find elements for deletion.

Insert Operation in O(1)

For insert(val), check if val exists in the hash map. If not, append val to the array and store its index in the hash map. Return true if inserted, false if already present.

Remove and getRandom Efficiently

To remove(val), swap it with the last array element, update the moved element's index in the hash map, pop the last element, and delete val from the map. For getRandom(), return a random array element using its index.

Complexity Analysis

Time complexity for insert, remove, and getRandom is average O(1) because array access and hash map operations are constant. Space complexity is O(n) for storing elements and indices.

What Interviewers Usually Probe

• Looking for true O(1) operations on all functions, not amortized linear time.
• Expect awareness of hash map collisions and edge cases during deletion.
• Interested in random selection correctness and uniform probability in getRandom.

Common Pitfalls or Variants

Common pitfalls

• Swapping incorrectly during remove can break index mapping and cause wrong deletions.
• Forgetting to update the hash map when moving the last element leads to inconsistent state.
• Using only a hash set without an array prevents O(1) random access.

Follow-up variants

• Randomized collection allowing duplicates with getRandom weighted by occurrence.
• Implementing similar O(1) operations for a fixed-size window or sliding set.
• Extending to support getRandomSubset(k) efficiently from the current set.

How GhostInterview Helps

• Highlights array and hash map coordination to achieve constant-time operations.
• Provides step-by-step swap and index update patterns specific to this problem.
• Ensures your getRandom implementation maintains uniform probability and avoids hidden O(n) costs.

Topic Pages

• Array
• Hash Table
• Math
• Design
• Randomized

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

Why use both an array and a hash map in Insert Delete GetRandom O(1)?

The array allows O(1) random access for getRandom(), while the hash map provides O(1) lookup for insert and remove operations.

Can getRandom fail if the set is empty?

Yes, getRandom assumes at least one element exists; calling it on an empty set is invalid according to the constraints.

What is the main failure mode in this problem?

The main failure mode is incorrectly updating indices during removal, which breaks both O(1) deletion and correct random selection.

Are duplicate values allowed in RandomizedSet?

No, RandomizedSet only allows unique values. Attempting to insert a duplicate returns false.

How does swapping with the last element help remove in O(1)?

Swapping avoids shifting all array elements, letting you remove the target in constant time and maintain valid indices in the hash map.