Insert Delete Get Random O(1)

Share

Implement the RandomizedSet class:

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1
Input: Operations order ["insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[1], [2], [2], [], [1], [2], []]
Output: [true, false, true, 2, true, false, 2]
Explanation:
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:

Contents

Solution 1 - Using a HashMap to have Insert() and Remove() operations in O(1) time, and a List to track current elements and to have Get() operation in O(1) time

In this approach, we are going to use a HashMap to store elements as well as into an ArrayList. The reason we are storing elements into a HashMap is because we need to be able to insert() and remove() operation in O(1) time. But, we need to have getRandom() operation also run in O(1) time, so for this reason, we are going to store elements into an ArrayList as well, and the index of the element is stored and retrieved from the HashMap.

Implementation details:
  • Initialize a ArrayList that we are going to store elements into, call it numbers, a HashMap that we are going to use it to store elements and key and index as value, call it numberToIndex.
  • insert() operation: If the numberToIndex already contains the input element, return false, otherwise add it to the numbers as well as to numberToIndex and return true.
  • remove() operation: If the numberToIndex doesn't contains the input element, return false, otherwise check the index of the element from numberToIndex and if this is the last element in numbers, then remove it from numbers and numberToIndex. If the index of the element is not the end index, then we will replace that element with end element in numbers, and update end element indexed element to current index in numberToIndex. Then, remove end element from numbers and remove input element from numberToIndex.
    The reason we do this is because, if the element is not at the end, then removing an element will require resizing of the array and this is O(n) operation, so instead or removing the element, we replace that with end indexed element and remove that end element, and update the end element index in the numberToIndex to reflect it.
  • getRandom() operation: To get random number within the range of numbers indexes range, we will use java.util.Random class's nextInt(int bound) method, and return that random indexed element from numbers.
Java
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Random;

public class InsertDeleteGetRandom {

  final HashMap<Integer, Integer> numberToIndex;
  final List<Integer> numbers;
  final Random randomGen;

  public InsertDeleteGetRandom() {
      numberToIndex = new HashMap<>();
      numbers = new ArrayList<>();
      randomGen = new Random();
  }

  public boolean insert(int val) {
      if(numberToIndex.containsKey(val)) {
          return false;
      }
      numberToIndex.put(val, numbers.size());
      numbers.add(val);
      return true;
  }

  public boolean remove(int val) {

      if(!numberToIndex.containsKey(val)) {
          return false;
      }
      int index = numberToIndex.get(val);
      int lastIndex = numbers.size()-1;
      if(index != lastIndex) { // re-arrange numbers
          // update the index for last element of list in the map
          // replace the element that we are going tot delete with the last element in the List
          int lastElement = numbers.get(lastIndex);
          numbers.set(index, lastElement);
          numberToIndex.put(lastElement, index);
      }
      numbers.remove(lastIndex);
      numberToIndex.remove(val);
      return true;
  }

  public int getRandom() {
      int random = randomGen.nextInt(numbers.size());
      return numbers.get(random);
  }

  public static void main(String[] args) {
      InsertDeleteGetRandom insertDeleteGetRandom = new InsertDeleteGetRandom();

      System.out.println(insertDeleteGetRandom.insert(1));
      System.out.println(insertDeleteGetRandom.remove(2));
      System.out.println(insertDeleteGetRandom.insert(2));
      System.out.println(insertDeleteGetRandom.getRandom());
      System.out.println(insertDeleteGetRandom.remove(1));
      System.out.println(insertDeleteGetRandom.insert(2));
      System.out.println(insertDeleteGetRandom.getRandom());


      insertDeleteGetRandom = new InsertDeleteGetRandom();
      System.out.println(insertDeleteGetRandom.remove(0));
      System.out.println(insertDeleteGetRandom.remove(0));
      System.out.println(insertDeleteGetRandom.insert(0));
      System.out.println(insertDeleteGetRandom.getRandom());
      System.out.println(insertDeleteGetRandom.remove(0));
      System.out.println(insertDeleteGetRandom.insert(0));
      System.out.println(insertDeleteGetRandom.getRandom());


  }
}
Complexity Analysis:

Time complexity: Above code runs in O(1) time for all operations insert(), remove() and getRandom().
Space complexity: O(n), since we are storing elements into a HashMap and an ArrayList.

Full source code on GitHub