Start learning free

LESSON 237 OF 348 · HASH TABLE

Collection of Numbers in Kotlin: O(1) Operations with a HashMap

Practice O(1) Read the full explanation

We have a collection of integers which is initially empty and events of the following types:

    1. insert a new integer into the collection
    2. remove an integer from the collection
    3. return the number of occurences of a given integer

Implement all the operations above.

Example:

Input:
    insert(5) 
    insert(2)
    insert(5)
    count(5)
    remove(5)
    count(5)
Output:2 1
Explanation There are two 5s at the first count and one after the second

Note:

Each operation should run in O(1) time and your algorithm should use O(n) space.


STEP 1 OF 6
    Ctrl + Enter to check

    KOTLIN · HASH TABLE

    Collection Of Numbers in Kotlin, explained

    Problem overview

    The task is to build a collection of integers that starts empty and supports three operations: insert(value) adds one occurrence of a number, remove(value) takes one occurrence away, and count(value) returns how many occurrences of that number the collection currently holds. The same number can be inserted several times, so this is a multiset, not a set.

    In the example, insert(5), insert(2) and insert(5) leave two 5s and one 2. The first count(5) returns 2. After remove(5) there is one 5, so the second count(5) returns 1. Every operation must run in O(1) time, with O(n) total space.

    Approach: store a frequency for each value

    A list of all inserted numbers would make count and remove scan the list, which is O(n). The collection doesn't need to remember the numbers one by one. It only needs to know how many of each there are.

    So keep a hash map from each value to its number of occurrences, a frequency table. Looking up, updating and removing a key in a hash map are O(1) on average. Each operation becomes a small change to one entry:

    • count(value) reads the entry, and a value that was never inserted counts as 0.
    • insert(value) adds 1 to the entry.
    • remove(value) subtracts 1, but only if the count is positive.

    The table has at most one entry per distinct value inserted, so the space is O(n).

    Step by step

    This lesson is a class, Solution, with a property and three methods. The state has to live in the class so that all the methods share it between calls.

    1. Declare the table as a property. var freq: HashMap<Int, Int> goes at the top of the class, above the init block. It has no initial value yet, which Kotlin allows only if every constructor path assigns it before use.
    2. Assign it in init. The init block runs when a Solution is created, and freq = HashMap() gives the collection its empty starting state. Kotlin infers the type arguments from the declared type of freq.
    3. Write count. Return freq.getOrDefault(value, 0). A plain freq[value] has type Int?, which can't be returned from a function declared to return Int. getOrDefault returns a plain Int and gives 0 for an unknown value.
    4. Write insert. Store count(value) + 1 back with freq[value] = .... The bracket assignment adds the key if it is new, and overwrites it otherwise. Reusing count means the first insertion starts from 0.
    5. Guard remove. Wrap the update in if (count(value) > 0). Removing something that isn't there must do nothing. Without the check, remove of an unknown value would store -1.
    6. Subtract one inside the if: freq[value] = count(value) - 1.

    The solution in Kotlin

    class Solution {
    var freq: HashMap<Int, Int>
    init {
        freq = HashMap()
    }

    fun count(value: Int): Int {
        return freq.getOrDefault(value, 0)
    }

    fun insert(value: Int) {
        freq[value] = count(value) + 1
    }

    fun remove(value: Int) {
        if (count(value) > 0) {
            freq[value] = count(value) - 1
        }
    }
}

    Kotlin details worth knowing:

    • Properties and init. A property declared without an initializer must be assigned in an init block before the class can be used. The shorter form val freq = HashMap<Int, Int>() does both jobs in one line; the lesson's two-part form shows how init works.
    • freq[value] is nullable. The bracket read returns Int?, and Kotlin won't let you add 1 to it or return it as Int. The compiler reports that the type is Int? where Int is expected. This is why count is the one place that reads the table.
    • map[key] = v is put. It is the Kotlin shorthand for put(key, v).
    • Methods call each other. insert and remove call count on the same object, with no prefix needed.
    • Functions without a return type return Unit, so insert and remove need no return.

    Complexity

    Time: O(1) per operation on average. Each method does a constant number of hash-map reads and writes.

    Space: O(n). The table holds one entry per distinct value that was ever inserted, which is at most the number of inserts. An entry whose count has dropped to 0 stays in the map. That doesn't affect correctness, since a count of 0 is what a missing entry means too.

    Edge cases and common mistakes

    • Counting a value never inserted. count(9) returns 0 and doesn't add an entry.
    • Removing a value never inserted. remove(9) does nothing, and count(9) is still 0, not -1.
    • Removing more times than inserted. After insert(2), calling remove(2) twice leaves the count at 0, because the second call fails the guard.
    • Removing every copy at once. remove takes away one occurrence only. After two insert(5) calls and one remove(5), the count is 1.
    • Negative numbers and zero. They work as keys like any other integer.
    • Forgetting the default. Using freq[value] directly in count doesn't compile, because of the nullable type.

    Testing

    Starting from an empty collection:

    • insert(5), insert(2), insert(5), then count(5) gives 2.
    • Then remove(5) and count(5) gives 1.
    • remove(9) and count(9) gives 0.
    • remove(2) twice and count(2) gives 0.
    Keep going with KotlinAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free