Problem Statement

Implement the RandomizedSet class:

RandomizedSet() Initializes the RandomizedSet object.
bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.
You must implement the functions of the class such that each function works in average O(1) time complexity.

Test Case :

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^31 <= val <= 2^31 - 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.

Approaches

1) Using ArrayList

• Here we can do the insert operation in O(1)

• We can do the getRandom in O(1) using Random

• But the remove operation costs O(n) as we need to go through the list and then remove. So is there any better one.

2) Using HashSet

• Here we can do insert operation in O(1) avg

• We can do remove operation in O(1) avg

• But the getRandom causes O(n) operations or requires new array to store the value and then apply nextInt() of Random. So is there any better one.

3) Using Doubly LinkedList

• Here we can do insert operation in O(1)

• But the remove operation will be O(n)

• Also the getRandom operation will be O(n) as we have to go through each element. So is there any better one.

Efficient Approach

• We can make use of HashMap and a List.

• In HashMap the key will be the element we are inserting and the value will be its index.

• Insert operation will be O(1). We insert the element into the list and we insert the element, index as key value pair into the hashmap.
  

private Map<Integer, Integer> map;
    private Random random;
    private List<Integer> elements;

    public RandomizedSet() {
        map = new HashMap<>();
        random = new Random();
        elements = new ArrayList<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            elements.add(val);
            map.put(val, elements.size() - 1);
            return true;
        }
        return false;
    }

• Remove operation is bit tricky. We find the index of the value to be deleted from the map. Then we swap the value to be deleted and last element of the list. Then we update the map after replacing because the element which was at the last position before is swapped with the element to be deleted. So now we can just remove the last element of the list which is what we needed in O(1).

public boolean remove(int val) {
        int lastIndex = map.getOrDefault(val, -1);
        if (lastIndex == -1)
            return false;
        Collections.swap(elements, lastIndex, elements.size() - 1);
        int otherSwappedValue = elements.get(lastIndex);
        map.put(otherSwappedValue, lastIndex);
        elements.remove(elements.size() - 1);
        map.remove(val);
        return true;
    }

• We find the random index by using random.nextInt(listsize) and return the value of that index. The complexity will be O(1).

/** Get a random element from the set. */
    public int getRandom() {
        int randomIndex = random.nextInt(elements.size());
        return elements.get(randomIndex);
    }

Complete code :

class RandomizedSet {

    // hashamo key : number and value = its last index
    /** Initialize your data structure here. */
    private Map<Integer, Integer> map;
    private Random random;
    private List<Integer> elements;

    public RandomizedSet() {
        map = new HashMap<>();
        random = new Random();
        elements = new ArrayList<>();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            elements.add(val);
            map.put(val, elements.size() - 1);
            return true;
        }
        return false;
    }

    // here we find the index of the value to be deleted from the map
    // we then swap this element with the element at the back
    // now the element at back will be at the position where the value to be deleted was before
    // and the value to be deleted will be at the last position
    // now we updated the map 
    // remove the val from the map and list
    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        int lastIndex = map.getOrDefault(val, -1);
        if (lastIndex == -1)
            return false;
        Collections.swap(elements, lastIndex, elements.size() - 1);
        int otherSwappedValue = elements.get(lastIndex);
        map.put(otherSwappedValue, lastIndex);
        elements.remove(elements.size() - 1);
        map.remove(val);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int randomIndex = random.nextInt(elements.size());
        return elements.get(randomIndex);
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */