381.insert-delete-getrandom-o1-duplicates-allowed.md

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

Hash Table

We extend the same idea from 380. Insert Delete GetRandom O(1). Since we allow duplicates, we need:

• A way to track multiple occurrences of a value.
• A way to remove a specific occurrence of a value efficiently.

We need two key data structures:

• List values to store all values for O(1) random access.
• Hash table valueIndexMap: Map a value to a set of indexes in the list values.

index    0  1  2  3, 4
lists = [5, 6, 7, 6, 5]

valueIndexMap = {
    5: {0, 4},
    6: {1, 3},
    7: {2},
}

We store all the index of each element in a hash table. When we remove an element, we swap it with the last element in the list and update the index of the last element in the hash table. This way, we can remove an element in O(1) time.

There are something we need to pay attention to in our implementation, see the comments in the code.

class RandomizedCollection() {

    // {value: {index}}
    private val valueIndexMap = HashMap<Int, HashSet<Int>>()
    private val values = mutableListOf<Int>()

    // Return true if not exist, false if exist.
    fun insert(`val`: Int): Boolean {
        values.add(`val`)
        val lastIndex = values.lastIndex
        if (`val` in valueIndexMap) {
            valueIndexMap[`val`]!!.add(lastIndex)
            return false
        } else {
            val set = HashSet<Int>()
            set.add(lastIndex)
            valueIndexMap[`val`] = set
            return true
        }
    }

    // Return true if exist, false if not exist.
    fun remove(`val`: Int): Boolean {
        if (`val` !in valueIndexMap) {
            return false
        }
        val indexes = valueIndexMap[`val`]!!

        // Take one index of the value to remove
        val toRemoveIndex = indexes.iterator().next()

        // Remove the index of `val` from map, and remove key if the set becomes empty
        // NOTE: We have to ensure the index is removed from the map before we update the index of last element in map.
        indexes.remove(toRemoveIndex)
        if (indexes.isEmpty()) {
            valueIndexMap.remove(`val`) 
        }
        // We move the last element to the current index, and update the index of last element in map
        val lastValue = values.last()
        val lastIndex = values.lastIndex
        values[toRemoveIndex] = lastValue // Swap the last element with the element to remove
        values.removeAt(values.lastIndex) // Remove the last element from list
        
        // Update the index of last element in map
        // NOTE: The `valueIndexMap[lastValue]` might be null. `insert(1), remove(1)` will remove the key from map.
        valueIndexMap[lastValue]?.remove(lastIndex)
        valueIndexMap[lastValue]?.add(index)
        return true
    }

    fun getRandom(): Int {
        val index = (Math.random() * values.size).toInt()
        return values[index]
    }
}