Leetcode 381. Insert Delete GetRandom O(1) - Duplicates allowed

Problem Explanation

This problem asks us to design a data structure that supports three operations: insert(), remove(), and getRandom(). All three operations need to be done in O(1) average time. To do this, we need to make use of a combination of two data structures: an Array (or Vector) and a HashMap (or dictionary).

Here is a walkthrough of these operations:

Insert: This operation calls for inserting an element into the collection. If the collection already contains the specific element, we return false, otherwise we return true. We store the element being inserted into an Array and also store the index of the element in the Array as a value in the HashMap with the key being the inserted element.

Remove: In the remove operation, we remove an item from the collection only if it is present. If the element isn't found in the collection, we return false, otherwise we return true. Since removal from an array can't be done in O(1) time without disturbing the order of elements, we swap the element to be removed with the last element in the array and then delete the last element. We also update the index in the HashMap.

GetRandom: This operation should return a random element from our data structure in constant time. As Arrays support random access in O(1) time, we just pick a random index and return the element at that index.

Now let's walk through an example:

We initialize an empty collection. Then we insert 1 into the collection. After that, we again insert 1 into the collection. Now our collection looks like this: [1,1], and the HashMap contains the element 1 associated with the indexes [0,1]. Then we insert 2 into the collection. Now the collection is [1,1,2] and the HashMap contains 1->[0,1], and 2->[2]. When we call getRandom, the chances of picking 1 is 2/3, and the chances of picking 2 is 1/3 since 1 occurs twice and 2 occurs once.

Let's say we remove 1 from the collection. Now our collection is [1,2] and HashMap contains 1->[0] and 2->[1]. When we call getRandom, both 1 and 2 have equal chances of being selected as they have equal number of occurance.

Solution

Python Solution

1
2python
3import random
4class RandomizedCollection:
5	def __init__(self):
6		"""
7		Initialize your data structure here.
8		"""
9		self.list, self.dic = [], {}
10
11	def insert(self, val: int) -> bool:
12		"""
13		Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
14		"""
15		self.dic[val] = self.dic.get(val, []) + [len(self.list)]
16		self.list.append(val)
17		return len(self.dic[val]) == 1
18
19	def remove(self, val: int) -> bool:
20		"""
21		Removes a value from the collection. Returns true if the collection contained the specified element.
22		"""
23		if self.dic.get(val) != None:
24			last, idx = self.list[-1], self.dic[val][-1]
25			self.list[idx], self.dic[last][-1] = last, idx
26			if(self.dic[val][-1] != idx):
27				self.dic[val].remove(idx)
28			else:
29				self.dic[val].pop()
30			self.list.pop();
31			if len(self.dic[val]) == 0:
32				del self.dic[val]
33			return True
34		return False
35
36	def getRandom(self) -> int:
37		"""
38		Get a random element from the collection.
39		"""
40		return random.choice(self.list)

C++ Solution

1
2cpp
3class RandomizedCollection {
4    vector<pair<int, int>> nums;
5    unordered_map<int, vector<int>> m;
6    
7    public:
8    /** Initialize your data structure here. */
9    RandomizedCollection() {}
10
11    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
12    bool insert(int val) {
13        bool contain = m.count(val);
14        m[val].push_back(nums.size());
15        nums.push_back(pair<int, int>(val, m[val].size() - 1));
16        return !contain;
17    }
18
19    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
20    bool remove(int val) {
21        if (!m.count(val)) {
22            return false;
23        }
24        auto last = nums.back();
25        m[last.first][last.second] = m[val].back();
26        nums[m[val].back()] = last;
27        m[val].pop_back();
28        if (m[val].empty()) m.erase(val);
29        nums.pop_back();
30        return true;
31    }
32
33    /** Get a random element from the collection. */
34    int getRandom() {
35        return nums[rand() % nums.size()].first;
36    }
37};

JavaScript Solution

In JavaScript, we can use ES6 Map data structure. A JavaScript Map object can hold key-value pairs where elements are ordered based on their insertion order. Here is the code:

1
2javascript
3
4class RandomizedCollection {
5    constructor() {
6        this.collection = new Map();
7        this.values = [];
8    }
9
10    insert(val) {
11        let inserted = false;
12        if(!this.collection.has(val)) {
13            inserted = true;
14            this.collection.set(val, new Set());
15        } 
16        this.collection.get(val).add(this.values.length);
17        this.values.push(val);
18        return inserted;
19    }
20
21    remove(val) {
22        if(!this.collection.has(val)) return false;
23        let idx = this.collection.get(val).values().next().value;
24        let lastNum = this.values[this.values.length - 1];
25        this.collection.get(val).delete(idx);
26        if(this.collection.get(val).size === 0) {
27            this.collection.delete(val);
28        }
29        if(idx !== this.values.length - 1) {
30            this.values[idx] = lastNum;
31            this.collection.get(lastNum).add(idx);
32            this.collection.get(lastNum).delete(this.values.length - 1);
33        }
34        this.values.pop();
35        return true;
36    }
37
38    getRandom() {
39        return this.values[Math.floor(Math.random() * this.values.length)];
40    }
41}
42

In JavaScript, this solution gives us O(1) times for all three operations.

Java Solution

We can use Java ArrayList and HashMap data structures to solve this. An ArrayList in Java represents a resizable list of objects.

1
2java
3public class RandomizedCollection {
4   private ArrayList<Integer> nums;
5   private HashMap<Integer, Set<Integer>> locs;
6   private java.util.Random rand = new java.util.Random();
7
8   /** Initialize your data structure here. */
9   public RandomizedCollection() {
10      nums = new ArrayList<Integer>();
11      locs = new HashMap<Integer, Set<Integer>>();
12   }
13   
14   /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
15   public boolean insert(int val) {
16      boolean contain = locs.containsKey(val);
17      if ( ! contain ) locs.put( val, new LinkedHashSet<Integer>() );
18      locs.get(val).add(nums.size());
19      nums.add(val);
20      return ! contain ;
21   }
22   
23   /** Removes a value from the collection. Returns true if the collection contained the specified element. */
24   public boolean remove(int val) {
25      boolean contain = locs.containsKey(val);
26      if ( ! contain ) return false;
27      int loc = locs.get(val).iterator().next();
28      locs.get(val).remove(loc);
29      if ( locs.get(val).isEmpty() ) locs.remove(val);
30
31      if ( loc < nums.size() - 1 ) {
32         int lastone = nums.get( nums.size()-1 );
33         nums.set( loc , lastone );
34         locs.get(lastone).remove(nums.size()-1);
35         locs.get(lastone).add(loc);
36      }
37      nums.remove(nums.size() - 1);
38      return true;
39   }
40   
41   /** Get a random element from the collection. */
42   public int getRandom() {
43      return nums.get( rand.nextInt(nums.size()) );
44   }
45}

In this Java solution, we also get O(1) time complexity for all three operations.