Insert Delete GetRandom O(1)

Problem Statement

The RandomizedSet class is a data structure designed to handle a collection of unique integer elements with the ability to perform three primary operations: inserting an integer, removing an integer, and retrieving a random integer. Each of these operations should ideally run in constant average time complexity (O(1)).

• The method RandomizedSet() is used to initialize the RandomizedSet object.
• The method insert(int val) adds an integer val to the set if it is not already present. The return value is true if val was not previously present in the set, and false otherwise.
• The method remove(int val) removes an integer val from the set if it exists, returning true if the integer was present and false if it was not.
• Finally, the getRandom() method returns a random integer from the current elements in the set. Every element should have the same likelihood of being selected, and this selection is guaranteed to be possible only when there is at least one element in the set.

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:

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

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

Approach and Intuition

Insert Operation (insert(int val))

To insert a unique integer in average O(1) time:

1. Use a combination of a hash table and a list (array).
2. Append the new value to the array and store its index in the hash table.
3. Appending and updating the hash table both take constant time.

Remove Operation (remove(int val))

To maintain constant time during removal:

1. Use the hash table to find the index of the value.
2. Swap the value with the last element in the array.
3. Update the hash table and remove the last element.
4. This avoids shifting elements, preserving O(1) performance.

getRandom() Operation

To select a random element:

1. Since all values are stored in an array, choose a random index.
2. This ensures uniform probability and constant time selection.

Example Demonstration

• randomizedSet.insert(1) → Returns true, inserts 1.
• randomizedSet.remove(2) → Returns false, 2 not present.
• randomizedSet.insert(2) → Returns true, adds 2.
• randomizedSet.getRandom() → Returns 1 or 2.
• randomizedSet.remove(1) → Removes 1, returns true.
• randomizedSet.insert(2) → 2 is already present, returns false.
• randomizedSet.getRandom() → Only 2 is present, so returns 2.

The methods provide a concise and efficient solution to dynamically manage a set of unique integers with optimal time complexity.

Solutions

class UniqueSet {
  Map<Integer, Integer> valueMap;
  List<Integer> values;
  Random random = new Random();

  /** Initializes the data structure. */
  public UniqueSet() {
    valueMap = new HashMap<>();
    values = new ArrayList<>();
  }

  /** Adds a value. Returns true if it was not present. */
  public boolean insert(int val) {
    if (valueMap.containsKey(val)) return false;

    valueMap.put(val, values.size());
    values.add(values.size(), val);
    return true;
  }

  /** Removes a value. Returns true if it was present. */
  public boolean remove(int val) {
    if (!valueMap.containsKey(val)) return false;

    // Swap with last item and update the hashmap
    int lastValue = values.get(values.size() - 1);
    int removeIndex = valueMap.get(val);
    values.set(removeIndex, lastValue);
    valueMap.put(lastValue, removeIndex);
    
    // Remove the last item
    values.remove(values.size() - 1);
    valueMap.remove(val);
    return true;
  }

  /** Returns a random element. */
  public int getRandom() {
    return values.get(random.nextInt(values.size()));
  }
}