leetcode_gym/_problems/insertDeleteGetRandom.md

layout, title, last_solved, category, leetcode_url, status

layout	title	last_solved	category	leetcode_url	status
page	Insert Delete GetRandom O(1)	2020-06-12	hashtable, design	https://leetcode.com/problems/insert-delete-getrandom-o1	Solved

Problem

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

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();

Solution

The insight is to use 2 hash tables to achive O(1) time.

The hard part was to achive a O(1) time with getRandom(), we need to make sure it can pick from a hashtable index directly. Therefore, when we delete an element from both hash tables, we can't leave a gap. Writing the code for that was a bit tricky so write out your sample data and write out each step seperately. Like so:

    # map1: {0:10, 1:20}    map1[index] = real value
    # map2: {10:0, 20:1}    map2 is the reverse

{% highlight python %}

class RandomizedSet:

def __init__(self):
    
    self.map1 = {}
    self.map2 = {}
    self.numElements = 0

def insert(self, num):
    
    if num not in self.map2:
        self.map2[num] = self.numElements
        self.map1[ self.numElements ] = num
        self.numElements+=1
        
        return True
    
    return False    # already present
    

def remove(self, num):
    
    if num in self.map2:
        
        # remove last element
        if self.map2[num]==self.numElements-1:
            index = self.map2.pop(num)
            self.map1.pop(index)
            self.numElements-=1

        # remove but not last element
        else:

            # if we remove index, then there will be a gap
            removedIndex = self.map2.pop(num)
            self.map1.pop(removedIndex)
            self.numElements-=1
            
            # take the last element and fill the gap
            lastElement = self.map1[self.numElements]
            saveLastElementIndex = self.map2[lastElement]
            self.map2[lastElement] = removedIndex
            
            self.map1.pop(saveLastElementIndex)
            self.map1[ self.map2[lastElement] ] = lastElement
    
        return True
    
    return False    # not in set


def getRandom(self):
    
    index = random.randrange(0, len(self.map1) )
    return self.map1[index]

{% endhighlight %}