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.

Key Steps in remove()

1. Get and remove one index from valueIndexMap first. If the set becomes empty, remove the key from the map.
2. If the target index != last index:
   • Overwrite values at target index with the last element.
   • Update the index of the last element in the map by removing the last index and adding the target index.
3. Remove the last element from the list.

Why this order?

• If val == lastValue, deleting val from it set before touching lastValue set avoids corrupting the same set. Removing target index first makes the set “clean” before you reinsert the moved index.
• Guarding target index == last index prevents adding/removing a stale last index in the map. (No operation needed)

Pitfalls

• Updating lastValue index in the map before deleting val target index (breaks when val == lastValue).
• Not guarding target index == last index (leads to adding a stale index in the map).

Also see 380. Insert Delete GetRandom O(1) for the same core idea.

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 {
        val indexSet = valueIndexMap[`val`] ?: return false
        val index = indexSet.first()

        // 1. Remove the target index from map first.
        indexSet.remove(index)
        if (indexSet.isEmpty) {
            valueIndexMap.remove(`val`)
        }

        // 2. Check if we should swap the last element with the target element.
        val lastIndex = values.lastIndex
        if (index != lastIndex) {
            val lastValue = values.last()
            values[index] = lastValue
            valueIndexMap[lastValue]?.remove(lastIndex)
            valueIndexMap[lastValue]?.add(index)
        }

        // 3. Pop the last element from the list.
        values.removeLast()
        return true
    }

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

WA

The following implementation is wrong. It failed at the case:

insert(8) // true
insert(8) // false
remove(8) // true
remove(8) // actual false, expected true.

fun remove(`val`: Int): Boolean {
    if (`val` !in valueIndexMap) return false
    val index = valueIndexMap[`val`]!!.iterator().next()

    val lastIndex = values.lastIndex
    val lastValue = values.last()

    values[index] = lastValue
    valueIndexMap[lastValue]!!.remove(lastIndex)
    valueIndexMap[lastValue]!!.add(index)

    values.removeAt(lastIndex)
    valueIndexMap[`val`]!!.remove(index)
    if (valueIndexMap[`val`]!!.isEmpty()) {
        valueIndexMap.remove(`val`)
    }

    return true
}

Please also test the following cases:

insert(8) // true
remove(8) // true
insert(8) // true
remove(8) // true.