Insert Delete GetRandom O(1) Solution in Java

Quick Links

Problem Description

Ah, the classic dilemma of wanting to insert, delete, and randomly retrieve elements from a collection in constant time. It’s like trying to find a specific sock in a laundry basket filled with mismatched socks—frustrating, right? You want to toss in a new sock (insert), throw out an old one (delete), and sometimes, just for fun, you want to randomly pull out a sock without looking (getRandom).

In the world of LeetCode, this problem is known as Insert Delete GetRandom O(1). The challenge is to design a data structure that supports these three operations efficiently. Imagine you’re at a party, and you want to keep track of who’s coming and going while also being able to randomly select someone to dance with. Sounds easy, but in the coding world, it’s a bit more complex!

Code Solution


class RandomizedSet {
  public boolean insert(int val) {
    if (valToIndex.containsKey(val))
      return false;
    valToIndex.put(val, vals.size());
    vals.add(val);
    return true;
  }

  public boolean remove(int val) {
    if (!valToIndex.containsKey(val))
      return false;
    final int index = valToIndex.get(val);
    valToIndex.put(last(vals), index);
    valToIndex.remove(val);
    vals.set(index, last(vals));
    vals.remove(vals.size() - 1);
    return true;
  }

  public int getRandom() {
    final int index = rand.nextInt(vals.size());
    return vals.get(index);
  }

  private Map valToIndex = new HashMap<>();
  private List vals = new ArrayList<>();
  private Random rand = new Random();

  private int last(List vals) {
    return vals.get(vals.size() - 1);
  }
}

Approach

The approach taken in this solution is quite clever. It uses a combination of a HashMap and an ArrayList to achieve the desired operations in constant time. The HashMap (valToIndex) keeps track of the values and their corresponding indices in the ArrayList (vals).

Insert: Check if the value already exists. If not, add it to the list and map its index.
Remove: Find the index of the value to be removed, swap it with the last element in the list (to maintain the array’s compactness), and update the map accordingly.
GetRandom: Simply generate a random index and return the value at that index.

Time and Space Complexity

Operation	Time Complexity	Space Complexity
Insert	O(1)	O(n)
Remove	O(1)
GetRandom	O(1)

Real-World Example

Imagine you’re at a buffet with a variety of dishes. You want to add a new dish (insert), remove a dish that you didn’t like (delete), and sometimes, you just want to randomly pick a dish to try (getRandom). This data structure allows you to manage your buffet selections efficiently, ensuring you can always add, remove, or randomly select a dish without breaking a sweat!