16.01.2024
380. Insert Delete GetRandom O(1) medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/473
Problem TLDR
Implement HashSet<Int> with random method.
Intuition
There is a random
method exists in Kotlin’s MutableSet
https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/random.html.
However, let’s just use array to store values and save positions in a HashMap
. The order in array didn’t matter, so we can remove elements in O(1).
Approach
To save some symbols of code, we can extend from ArrayList.
Complexity
Time complexity:
O(1), per operationSpace complexity:
O(1), per operation
Code
class RandomizedSet(): ArrayList<Int>() {
val vToPos = HashMap<Int, Int>()
fun insert(v: Int): Boolean {
if (vToPos.contains(v)) return false
add(v)
vToPos[v] = lastIndex
return true
}
override fun remove(v: Int): Boolean {
val pos = vToPos.remove(v) ?: return false
set(pos, last())
if (last() != v) vToPos[last()] = pos
removeLast()
return true
}
fun getRandom() = random()
}