Insert Delete GetRandom O(1) - Duplicates allowed

Hard Design Data Structures Hash Map + Array Original on LeetCode

Reported atLinkedIn

Insert Delete GetRandom O(1) - Duplicates allowed is a hard design data structures problem solved with the hash map + array pattern. The best approach, optimal (array + map of index sets), runs in O(1) average per operation time and O(n) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (plain list, linear remove) up.

Problem

Design a class RandomizedCollection that stores a multiset of integers (the same value may be stored several times) and supports every operation in average O(1) time:

  • insert(val): add one copy of val. Return true if val was not in the collection before this call, otherwise false (the copy is added either way).
  • remove(val): if at least one copy of val is stored, remove one copy and return true; otherwise return false.
  • getRandom(): return a random stored value. The chance of each value is proportional to how many copies of it are stored: with {1, 1, 2}, the value 1 comes back with probability 2/3.

Examples

Example 1

Input
insert(3), insert(3), insert(8), getRandom(), remove(3), getRandom()
Output
true, false, true, 3 or 8, true, 3 or 8
Why
The bag first holds {3, 3, 8}, so getRandom returns 3 with probability 2/3 and 8 with probability 1/3. After one 3 is removed the bag is {3, 8} and both are equally likely.

Example 2

Input
insert(-5), remove(-5), remove(-5), insert(-5), insert(-5), getRandom()
Output
true, true, false, true, false, -5
Why
The second remove fails because the bag is empty. Inserting -5 again succeeds as a new value, the next insert adds a duplicate and returns false, and only -5 can be drawn.

Constraints

  • -2^31 <= val <= 2^31 - 1
  • getRandom is only called when the collection holds at least one value.
  • At most 2 * 10^5 calls in total.
  • Each operation must run in average O(1) time.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (plain list, linear remove)O(n) for insert and remove, O(1) for getRandomO(n)
Optimal (array + map of index sets)O(1) average per operationO(n)

1Brute force (plain list, linear remove)

TimeO(n) for insert and remove, O(1) for getRandomThe contains check and the removal both scan the list, and removal shifts later elements.
SpaceO(n)Every inserted copy is stored once.

Keep every copy in a dynamic array. A random index gives the right probabilities automatically. Insert checks whether the value exists by scanning, and remove deletes the first copy it finds, shifting the elements after it.

  1. insert: fresh = list does not contain val; append val; return fresh.
  2. remove: find the first index of val; if none return false; delete it and return true.
  3. getRandom: return list[random index below the size].
class RandomizedCollection {
    private final List<Integer> list = new ArrayList<>();
    private final Random rnd = new Random();

    public boolean insert(int val) {
        boolean fresh = !list.contains(val);
        list.add(val);
        return fresh;
    }

    public boolean remove(int val) {
        return list.remove(Integer.valueOf(val));
    }

    public int getRandom() {
        return list.get(rnd.nextInt(list.size()));
    }
}

2Optimal (array + map of index sets)

TimeO(1) average per operationEach operation does a constant number of hash map, hash set and array end operations.
SpaceO(n)The array and the index sets each hold one entry per stored copy.

Keep all copies packed in an array so a random index is a fair draw weighted by count. Next to it keep a map from each value to the set of indices where it lives. Removal takes any index i of the value, copies the last element into slot i, moves that element's index from the last position to i in its own set, and pops the end. Nothing shifts, so every operation is O(1) on average.

  1. insert: add the new index (array size) to idx[val], append val, return true if idx[val] had been empty.
  2. remove: if idx[val] is missing or empty return false. Take any i from idx[val] and remove it.
  3. Let last = the final element. Put last at position i, add i to idx[last], remove the old last index from idx[last], pop the array. Delete idx[val] if it became empty.
  4. getRandom: return array[random index below the size].
class RandomizedCollection {
    private final List<Integer> vals = new ArrayList<>();
    private final Map<Integer, Set<Integer>> idx = new HashMap<>();
    private final Random rnd = new Random();

    public boolean insert(int val) {
        Set<Integer> s = idx.computeIfAbsent(val, k -> new HashSet<>());
        boolean fresh = s.isEmpty();
        s.add(vals.size());
        vals.add(val);
        return fresh;
    }

    public boolean remove(int val) {
        Set<Integer> s = idx.get(val);
        if (s == null || s.isEmpty()) return false;
        int i = s.iterator().next();
        s.remove(i);
        int lastPos = vals.size() - 1;
        int last = vals.get(lastPos);
        vals.set(i, last);
        Set<Integer> ls = idx.get(last);
        ls.add(i);
        ls.remove(lastPos);
        vals.remove(lastPos);
        if (s.isEmpty()) idx.remove(val);
        return true;
    }

    public int getRandom() {
        return vals.get(rnd.nextInt(vals.size()));
    }
}

Edge cases to test

  • Inserting a value that is already present: it is still added, but the call returns false
  • Removing one copy of a value that has several copies: the others stay and the call returns true
  • Removing the copy that sits in the last slot of the array
  • Removing a value that is not present returns false
  • Many copies of one value and a single copy of another: getRandom must favour the frequent value

Hints

Hint 1

A plain list already gives the right probabilities: picking a uniform random index returns each value with probability equal to its share of the list. The hard part is removing quickly.

Hint 2

Store, for each value, the set of all indices where it appears in the list.

Hint 3

To delete in O(1), take any index of the value, move the last element of the list into that slot, fix the moved element's index set, and pop the end.

FAQ

What is the best time complexity for Insert Delete GetRandom O(1) - Duplicates allowed?

Optimal (array + map of index sets) runs in O(1) average per operation time and O(n) extra space. Each operation does a constant number of hash map, hash set and array end operations.

Which pattern does Insert Delete GetRandom O(1) - Duplicates allowed use?

It is a design data structures problem that uses the hash map + array pattern. Other problems with the same pattern: Insert Delete GetRandom O(1), Logger Rate Limiter, Design Parking System.

Is there a brute force solution for Insert Delete GetRandom O(1) - Duplicates allowed?

Yes. Brute force (plain list, linear remove) takes O(n) for insert and remove, O(1) for getRandom time and O(n) space. Keep every copy in a dynamic array.

Which edge cases should I test for Insert Delete GetRandom O(1) - Duplicates allowed?

Inserting a value that is already present: it is still added, but the call returns false; Removing one copy of a value that has several copies: the others stay and the call returns true; Removing the copy that sits in the last slot of the array; Removing a value that is not present returns false; Many copies of one value and a single copy of another: getRandom must favour the frequent value.