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

$ curl repovive.com/roadmaps/amazon-interview-prep/amazon-coding-ii-stacks-heaps-hash-maps/leetcode-380-insert-delete-getrandom-o1-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████████

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

$ curl repovive.com/roadmaps/amazon-interview-prep/amazon-coding-ii-stacks-heaps-hash-maps/leetcode-380-insert-delete-getrandom-o1-implementation

Repovive

LeetCode 380 Insert Delete GetRandom O(1) - Implementation - Amazon Coding II: Stacks, Heaps & Hash Maps | Amazon Interview Prep | Repovive

Repovive.

Amazon Interview Prep9 sections · 182 units9h total

Open in Course

LeetCode 380 Insert Delete GetRandom O(1) - Implementation

The approach

Here's the full structure with all $3$ operations.

class RandomizedSet:
    map = {}       // val -> index
    arr = []

    function insert(val):
        if val in map:
            return false
        map[val] = arr.length
        arr.append(val)
        return true

    function remove(val):
        if val not in map:
            return false
        idx = map[val]
        lastVal = arr[arr.length - 1]
        arr[idx] = lastVal
        map[lastVal] = idx
        arr.pop()
        delete map[val]
        return true

    function getRandom():
        randIdx = random(0, arr.length - 1)
        return arr[randIdx]