Solution For Insert Delete Getrandom O1 Duplicates Allowed

Problem Statement:
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();

Approach to Solve:

We can use a map and an array to implement it.
The array will store the actual elements, and the map will store the indices of the elements in the array.

insert(val): To insert an element val in the array, we first check if it is already present in the map. If it is present, we simply insert the val into the array and update its index in the map. If it is not present, we insert the element and its index inside the map and push the index of the element in the array.
Here we are storing the indices in a list to handle duplicates.

remove(val): To remove an element val from the array, we first check if it is present in the map. If it is not present, we return false as we cannot remove an element that is not present in the array. If it is present, we get the last element from the array and copy it to the position of the element to be removed. Then we update its index in the map to be the position from which the element was copied. We remove the removed element’s index from its list and update the index of the last element.

getRandom: To get a random element from the array, we generate a random number between 0 and the size of the array and return the element at that index.

Code:

Here is the python 3 code to implement the solution.

“`
class RandomizedCollection:

def __init__(self):
    """
    Initialize your data structure here.
    """
    self.nums = []
    self.index = {}


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


def remove(self, val: int) -> bool:
    """
    Removes a value from the collection. Returns true if the collection contained the specified element.

    """
    if val in self.index:
        i = self.index[val].pop()
        if not self.index[val]:
            del self.index[val]
        if i != len(self.nums)-1:
            self.nums[i] = self.nums[-1]
            self.index[self.nums[-1]].remove(len(self.nums)-1)
            self.index[self.nums[-1]].append(i)
        self.nums.pop()
        return True
    else:
        return False


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

    """
    return self.nums[random.randint(0,len(self.nums)-1)]

“`

Complexity Analysis:

Time Complexity:

The insert, remove, and getRandom operations take O(1) average time complexity.

Space Complexity:

The space complexity of the algorithm is O(N), where N is the number of elements in the data structure.

Step by Step Implementation For Insert Delete Getrandom O1 Duplicates Allowed

/**
 * 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 {
    
    ArrayList nums;
    HashMap> locs;
    java.util.Random rand = new java.util.Random();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        nums = new ArrayList();
        locs = new HashMap>();
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        boolean contain = locs.containsKey(val);
        if ( ! contain ) locs.put( val, new LinkedHashSet() ); 
        locs.get(val).add(nums.size());        
        nums.add(val);
        return ! contain ;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        boolean contain = locs.containsKey(val);
        if ( ! contain ) return false;
        int loc = locs.get(val).iterator().next();
        locs.get(val).remove(loc);
        if (loc < nums.size() - 1 ) {
           int lastone = nums.get( nums.size()-1 );
           nums.set( loc , lastone );
           locs.get(lastone).remove( nums.size()-1);
           locs.get(lastone).add(loc);
        }
        nums.remove(nums.size() - 1);
        
        if (locs.get(val).isEmpty()) locs.remove(val);
        return true;
    }
    
    /** Get a random element from the collection. */
    public int getRandom() {
        return nums.get( rand.nextInt(nums.size()) );
    }
}

class RandomizedCollection:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.nums = []
        self.pos = {}
        

    def insert(self, val: int) -> bool:
        """
        Inserts a value to the collection. Returns true if the collection did not already contain the specified element.
        """
        if val in self.pos:
            self.nums.append(val)
            self.pos[val].add(len(self.nums)-1)
            return False
        else:
            self.nums.append(val)
            self.pos[val] = {len(self.nums)-1}
            return True
        

    def remove(self, val: int) -> bool:
        """
        Removes a value from the collection. Returns true if the collection contained the specified element.
        """
        if val in self.pos:
            idx = self.pos[val].pop()
            last = self.nums[-1]
            self.nums[idx] = last
            self.pos[last].add(idx)
            self.pos[last].discard(len(self.nums)-1)
            self.nums.pop()
            if not self.pos[val]:
                self.pos.pop(val)
            return True
        return False
        

    def getRandom(self) -> int:
        """
        Get a random element from the collection.
        """
        return self.nums[random.randint(0, len(self.nums)-1)]

/**
 * Initialize your data structure here.
 */
var RandomizedCollection = function() {
    this.map = new Map();
    this.arr = [];
};

/**
 * Inserts a value to the collection. Returns true if the collection did not already contain the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.insert = function(val) {
    let exists = this.map.has(val);
    if(!exists) {
        this.map.set(val, new Set());
    }
    this.map.get(val).add(this.arr.length);
    this.arr.push(val);
    return !exists;
};

/**
 * Removes a value from the collection. Returns true if the collection contained the specified element. 
 * @param {number} val
 * @return {boolean}
 */
RandomizedCollection.prototype.remove = function(val) {
    if(!this.map.has(val)) {
        return false;
    }
    let last = this.arr[this.arr.length - 1];
    let valSet = this.map.get(val);
    let lastSet = this.map.get(last);
    let valIndex = valSet.values().next().value;
    valSet.delete(valIndex);
    if(val === last) {
        if(valSet.size === 0) {
            this.map.delete(val);
        }
        this.arr.pop();
    } else {
        this.arr[valIndex] = last;
        lastSet.delete(this.arr.length - 1);
        lastSet.add(valIndex);
        this.arr.pop();
        if(this.map.get(last).size === 0) {
            this.map.delete(last);
        }
    }
    return true;
};

/**
 * Get a random element from the collection.
 * @return {number}
 */
RandomizedCollection.prototype.getRandom = function() {
    return this.arr[Math.floor(Math.random() * this.arr.length)];
};

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

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection* obj = new RandomizedCollection();
 * bool param_1 = obj->insert(val);
 * bool param_2 = obj->remove(val);
 * int param_3 = obj->getRandom();
 */
 
class RandomizedCollection {
public:
    /** Initialize your data structure here. */
    RandomizedCollection() {
        
    }
    
    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    bool insert(int val) {
        bool ret = m.find(val) == m.end();
        m[val].push_back(nums.size());
        nums.push_back(val);
        return ret;
    }
    
    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    bool remove(int val) {
        if (m.find(val) == m.end()) return false;
        int last = nums.back();
        m[last].erase(remove(m[last].begin(), m[last].end(), nums.size() - 1), m[last].end());
        m[last].push_back(m[val].front());
        nums[m[val].front()] = last;
        nums.pop_back();
        m[val].pop_front();
        if (m[val].empty()) m.erase(val);
        return true;
    }
    
    /** Get a random element from the collection. */
    int getRandom() {
        return nums[rand() % nums.size()];
    }
private:
    unordered_map> m;
    vector nums;
};

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

using System; 
using System.Collections.Generic; 

public class RandomizedCollection { 

//list to store values 
List list; 

//dictionary to store value-index key-value pairs 
Dictionary> dict; 

//random number generator 
Random rand; 

/** Initialize your data structure here. */ 
public RandomizedCollection() { 
list = new List(); 
dict = new Dictionary>(); 
rand = new Random(); 
} 

/** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */ 
public bool Insert(int val) { 
bool contains = dict.ContainsKey(val); 

//if val is not in the dictionary, add it with an empty hashset 
if (!contains) { 
dict.Add(val, new HashSet()); 
} 

//add val to the end of the list and add its index to the hashset 
dict[val].Add(list.Count); 
list.Add(val); 

return !contains; 
} 

/** Removes a value from the collection. Returns true if the collection contained the specified element. */ 
public bool Remove(int val) { 

//if val is not in the dictionary, return false 
if (!dict.ContainsKey(val)) { 
return false; 
} 

//get a random index associated with val 
int index = dict[val].GetEnumerator().Current; 

//remove the index from the hashset 
dict[val].Remove(index); 

//if the list is not empty and the last element in the list is not val 
if (list.Count > 0 && list[list.Count - 1] != val) { 

//swap val with the last element in the list 
int last = list[list.Count - 1]; 
list[index] = last; 

//update the index associated with the last element in the list 
dict[last].Remove(list.Count - 1); 
dict[last].Add(index); 
} 

//remove the last element in the list 
list.RemoveAt(list.Count - 1); 

//if the hashset associated with val is empty, remove it from the dictionary 
if (dict[val].Count == 0) { 
dict.Remove(val); 
} 

return true; 
} 

/** Get a random element from the collection. */ 
public int GetRandom() { 

//if the list is empty, throw an exception 
if (list.Count == 0) { 
throw new System.InvalidOperationException("The list is empty."); 
} 

//return a random element from the list 
return list[rand.Next(list.Count)]; 
} 
} 

/** 
* Your RandomizedCollection object will be instantiated and called as such: 
* RandomizedCollection obj = new RandomizedCollection(); 
* bool param_1 = obj.Insert(val); 
* bool param_2 = obj.Remove(val); 
* int param_3 = obj.GetRandom(); 
*/