Question

Formatted question description: https://leetcode.ca/all/381.html

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

 Design a data structure that supports all following operations in average O(1) time.

 Note: Duplicate elements are allowed.

 insert(val): Inserts an item val to the collection.
 remove(val): Removes an item val from the collection if present.
 getRandom: Returns a random element from current collection of elements.
    The probability of each element being returned is linearly related to the number of same value the collection contains.

 Example:

 // Init an empty collection.
 RandomizedCollection collection = new RandomizedCollection();

 // Inserts 1 to the collection. Returns true as the collection did not contain 1.
 collection.insert(1);

 // Inserts another 1 to the collection. Returns false as the collection contained 1. Collection now contains [1,1].
 collection.insert(1);

 // Inserts 2 to the collection, returns true. Collection now contains [1,1,2].
 collection.insert(2);

 // getRandom should return 1 with the probability 2/3, and returns 2 with the probability 1/3.
 collection.getRandom();

 // Removes 1 from the collection, returns true. Collection now contains [1,2].
 collection.remove(1);

 // getRandom should return 1 and 2 both equally likely.
 collection.getRandom();

 @tag-array

Algorithm

For the insert() function, we add the position of the number to be inserted in nums to the end of the m[val] array, and then add val to the end of the array nums. We judge whether there is a duplication as long as the m[val] array has only one value of val just added or there are multiple values.

The remove() function is the difficulty of this problem. First, let’s see if there is a val in the HashMap, and if not, return false directly.

Then we take the tail element of nums, and update the last position in the position array of the tail element HashMap to the tail element of m[val], so that we can delete the tail element of m[val]. If m[val] there is only one element, then we delete this mapping directly. Then delete the tail element in the nums array and assign the tail element to the position of val.

Note that we need to use a heap instead of a normal vector array when building the mapping of HashMap

We use the priority queue to automatically sort all the coordinates of the same number, and move out the coordinates of the largest position each time.

Code

public class Insert_Delete_GetRandom_O_1_Duplicates_allowed {

    // https://leetcode.com/problems/insert-delete-getrandom-o1-duplicates-allowed/solution/
    public class RandomizedCollection_official {
        ArrayList<Integer> list;
        HashMap<Integer, Set<Integer>> map;
        java.util.Random rand = new java.util.Random();

        /** Initialize your data structure here. */
        public RandomizedCollection_official() {
            list = new ArrayList<Integer>();
            map = new HashMap<Integer, Set<Integer>>();
        }

        /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
        public boolean insert(int val) {
            if (!map.containsKey(val)) map.put(val, new LinkedHashSet<Integer>());
            map.get(val).add(list.size());
            list.add(val);
            return map.get(val).size() == 1;
        }

        /** Removes a value from the collection. Returns true if the collection contained the specified element. */
        public boolean remove(int val) {
            if (!map.containsKey(val) || map.get(val).size() == 0) return false;

            int locToRemove = map.get(val).iterator().next();
            map.get(val).remove(locToRemove);

            int last = list.get(list.size() - 1);
            list.set(locToRemove, last);
            map.get(last).add(locToRemove);
            map.get(last).remove(list.size() - 1);

            list.remove(list.size() - 1);
            return true;
        }

        /** Get a random element from the collection. */
        public int getRandom() {
            return list.get(rand.nextInt(list.size()));
        }
    }

    // official solution is better
    class RandomizedCollection_unnecessary_ifLogic {

        private List<Integer> list; // hold list
        private Map<Integer, LinkedHashSet<Integer>> map; // val -> list of indexes
        Random random;

        public RandomizedCollection() {
            list = new ArrayList<>();
            map = new HashMap<>();
            random = new Random();
        }

        public boolean insert(int val) {
            boolean ans = !map.containsKey(val);

            int loc = list.size();

            list.add(val);

            LinkedHashSet<Integer> indices = map.getOrDefault(val, new LinkedHashSet<>());
            indices.add(loc);
            map.put(val, indices);

            return ans;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val) || map.get(val).isEmpty()) {
                return false;
            }

            // Get loc of the val to be removed
            int locToRemove = map.get(val).iterator().next(); // Set iterator

            if (locToRemove < list.size() - 1) { // if not last index, then swap to last index

                // Get the number to be swapped
                int numToSwap = list.get(list.size() - 1);

                // Put the tail number to the location to be removed
                list.set(locToRemove, numToSwap);
                map.get(numToSwap).add(locToRemove);

                // Update the loc
                // @note: when swap two are the same val
                // [2,1,1] => remove(1)
                if (map.get(numToSwap).contains(list.size() - 1)) {
                    // undo above "map.get(numToSwap).add(locToRemove);" , if it's the last index
                    // remove the same duplicate
                    map.get(numToSwap).remove(list.size() - 1);
                }
            }

            // Remove the val in Set
            map.get(val).remove(locToRemove);

            // Remove the val
            list.remove(list.size() - 1);

            return true;
        }

        /** Get a random element from the collection. */
        public int getRandom() {
            int loc = random.nextInt(list.size());
            return list.get(loc);
        }
    }

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

class RandomizedCollection {
public:
    RandomizedCollection() {}
    bool insert(int val) {
        m[val].insert(nums.size());
        nums.push_back(val);
        return m[val].size() == 1;
    }
    bool remove(int val) {
        if (m[val].empty()) return false;
        int idx = *m[val].begin();
        m[val].erase(idx);
        if (nums.size() - 1 != idx) {
            int t = nums.back();
            nums[idx] = t;
            m[t].erase(nums.size() - 1);
            m[t].insert(idx);
        } 
        nums.pop_back();
        return true;
    }
    int getRandom() {
        return nums[rand() % nums.size()];
    }

private:
    vector<int> nums;
    unordered_map<int, unordered_set<int>> m;
};

from collections import defaultdict
from random import choice

class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.lst = []
        self.idx = defaultdict(set)


    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        self.idx[val].add(len(self.lst))
        self.lst.append(val)
        return len(self.idx[val]) == 1


    '''
        >>> a = set([1,1,2,3])
        >>> a
        {1, 2, 3}
        >>> a.pop()
        1
        >>> a
        {2, 3}
    '''
    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        if not self.idx[val]: return False
        remove_index, last = self.idx[val].pop(), self.lst[-1] # pop() on a set
        self.lst[remove_index] = last
        self.idx[last].add(remove_index)
        self.idx[last].discard(len(self.lst) - 1)

        self.lst.pop()
        return True


    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        return choice(self.lst)

# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

############

class RandomizedCollection(object):
  def __init__(self):
    """
    Initialize your data structure here.
    """
    self.dOfd = collections.defaultdict(dict)
    self.d = collections.defaultdict(list)
    self.a = []

  def insert(self, val):
    """
    Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
    :type val: int
    :rtype: bool
    """
    self.d[val].append(len(self.a))
    self.dOfd[val][len(self.a)] = len(self.d[val]) - 1
    self.a.append(val)
    return len(self.d[val]) == 1

  def remove(self, val):
    """
    Removes a value from the collection. Returns true if the collection contained the specified element.
    :type val: int
    :rtype: bool
    """
    dd = self.dOfd
    a = self.a
    d = self.d
    if not d[val]:
      return False
    idx = d[val][-1]
    a[idx] = a[-1]
    idxInDForLast = dd[a[-1]][len(a) - 1]
    d[a[-1]][idxInDForLast] = idx
    dd[a[-1]][idx] = idxInDForLast

    # del dd[val][idx]
    del dd[a[-1]][len(a) - 1]
    d[val].pop()
    a.pop()
    return True

  def getRandom(self):
    """
    Get a random element from the collection.
    :rtype: int
    """
    return self.a[random.randrange(0, len(self.a))]

# Your RandomizedCollection object will be instantiated and called as such:
# obj = RandomizedCollection()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

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

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions