Python solution with detailed explanation


  • 0
    G

    Solution

    Insert Delete GetRandom O(1) https://leetcode.com/problems/insert-delete-getrandom-o1/

    Algorithm

    • Use a hash-map + list to implement this structure.
    • hash-map points to the index in list. If the value is not in the set, then hash-map will either not have it or it would be pointing to None.
    • Insertion is simple. If the the value is not in the set or it points to None, append to end of list and make the hash-map point to the end of list.
    • Deletion is tricky. If the val is in the set (i.e. hmap contains it and hmap doesn't point to None), swap the value with the last value in list. Then update the hmap appropriately. Then pop the last value.
    • Be careful when you need to delete the last value - you need a special condition for that case.
    from random import randint
    class RandomizedSet(object):
        def __init__(self):
            """
            Initialize your data structure here.
            """
            self.hmap, self.nums = {}, []
            
    
        def insert(self, val):
            """
            Inserts a value to the set. Returns true if the set did not already contain the specified element.
            :type val: int
            :rtype: bool
            """
            if val not in self.hmap:
                self.nums.append(val)
                self.hmap[val] = len(self.nums)-1
                return True
            return False
            
    
        def remove(self, val):
            """
            Removes a value from the set. Returns true if the set contained the specified element.
            :type val: int
            :rtype: bool
            """
            if val in self.hmap:
                curr_idx = self.hmap[val]
                if curr_idx == len(self.nums)-1:
                    self.nums.pop()
                    del self.hmap[val]
                    return True
                self.nums[curr_idx], self.nums[-1] = self.nums[-1], self.nums[curr_idx]
                self.nums.pop()
                self.hmap[self.nums[curr_idx]] = curr_idx
                del self.hmap[val]
                return True
            return False
            
    
        def getRandom(self):
            """
            Get a random element from the set.
            :rtype: int
            """
            index = randint(0, len(self.nums)-1)
            return self.nums[index]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.