Problem Overview

You need to design a data structure that supports the following operations in average O(1) time complexity:

1. insert(val) – Inserts an element val into the set if it is not already present.
2. remove(val) – Removes an element val from the set if it exists.
3. getRandom() – Returns a random element from the current set. Each element must have an equal probability of being returned.

Example:

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); → returns true
• randomizedSet.remove(2); → returns false
• randomizedSet.insert(2); → returns true
• randomizedSet.getRandom(); → returns either 1 or 2
• randomizedSet.remove(1); → returns true
• randomizedSet.insert(2); → returns false (2 already exists)
• randomizedSet.getRandom(); → returns 2

---

Intuition / Approach

We need O(1) time for insert, remove, and getRandom, which rules out typical data structures like plain lists or sets.

We can achieve this by combining:

• A HashMap (for O(1) access and removal by value)
• An ArrayList (for O(1) random access by index)

Key Idea:

• Store elements in an ArrayList.
• Keep a HashMap mapping each element to its index in the list.
• To remove in O(1):
  • Swap the element to be removed with the last element in the list.
  • Update the index of the swapped element in the map.
  • Remove the last element from the list.

This avoids O(n) time removal that a normal list would cause.

---

Step-by-Step Algorithm Explanation

1. Insert(val)
   • If val is already in the map → return false.
   • Otherwise:
     • Add val to the end of the list.
     • Record its index in the map.
     • Return true.
2. Remove(val)
   • If val is not in the map → return false.
   • Otherwise:
     • Retrieve the index of val from the map.
     • Get the last element in the list.
     • Swap the last element with val in the list.
     • Update the index of the last element in the map.
     • Remove the last element from the list.
     • Remove val from the map.
     • Return true.
3. getRandom()
   • Generate a random index between 0 and list.size() - 1.
   • Return the element at that index.

---

Example Walkthrough

Let’s perform the following operations:

RandomizedSet set = new RandomizedSet();
set.insert(10);   // [10]
set.insert(20);   // [10, 20]
set.remove(10);   // swap and remove -> [20]
set.getRandom();  // returns 20

Step-by-step:

• insert(10) → list: [10], map: {10 → 0}
• insert(20) → list: [10, 20], map: {10 → 0, 20 → 1}
• remove(10):
  • index = 0, lastElement = 20
  • swap → list becomes [20, 10]
  • remove last → list = [20]
  • update map: {20 → 0}
• getRandom() → random index 0 → returns 20

---

Java Code Implementation

import java.util.*;

public class RandomizedSet {
    private Map<Integer, Integer> map; // Stores value → index mapping
    private List<Integer> list;        // Stores elements for random access
    private Random rand;               // Random generator

    public RandomizedSet() {
        map = new HashMap<>();
        list = new ArrayList<>();
        rand = new Random();
    }

    public boolean insert(int val) {
        if (map.containsKey(val)) {
            return false; // Already exists
        }
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    public boolean remove(int val) {
        if (!map.containsKey(val)) {
            return false; // Not present
        }
        int index = map.get(val);
        int lastElement = list.get(list.size() - 1);

        // Swap val with last element
        list.set(index, lastElement);
        map.put(lastElement, index);

        // Remove last element
        list.remove(list.size() - 1);
        map.remove(val);
        return true;
    }

    public int getRandom() {
        int randomIndex = rand.nextInt(list.size());
        return list.get(randomIndex);
    }
}

---

Complexity Analysis

1. Time Complexity:
   • insert() → O(1)
   • remove() → O(1)
   • getRandom() → O(1)
2. Space Complexity:
   • O(n) for storing up to n elements in both the list and map.

---

Alternative Approaches

1. Using LinkedHashSet:
   • Allows quick insertion and deletion, but getRandom() is O(n) because random access isn’t supported.
   • Not acceptable for O(1) requirement.
2. Using TreeSet:
   • Maintains sorted order but has O(log n) operations — slower than needed.

Hence, combining HashMap + ArrayList is the only way to achieve true O(1) performance for all operations.