LESSON 260 OF 414 · HASH TABLE

Collection of Numbers in Scala: O(1) Operations with a Hash Map

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 occurrences 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 5

Guided

Ctrl + Enter to check

SCALA · HASH TABLE

Collection Of Numbers in Scala, explained

Problem overview

The class Solution models a collection of integers that starts empty and supports three operations:

insert(value) adds one occurrence of value.
remove(value) removes one occurrence of value.
count(value) returns how many occurrences of value are in the collection.

In the example, the calls insert(5), insert(2), insert(5), count(5), remove(5), count(5) produce 2 and then 1: there are two 5s at first, and one after the removal.

The statement asks for O(1) time per operation and O(n) space.

Approach: store a count for each value

Keeping a list of all the numbers would make count and remove scan it, which is O(n). What matters is only how many times each value occurs, and its order never matters. A hash map from a value to its number of occurrences, a frequency table, answers all three operations in constant time on average:

insert adds 1 to the value's count.
remove subtracts 1, but only when the count is positive.
count reads the count, with 0 for a value never seen.

The map has one entry per distinct value that has been inserted, so the space is linear in the number of values.

This problem is also different from most in this chapter: it is not a single function but a small class. The three methods are called one at a time, in any order, so they need a place to keep the state between calls. In Scala that place is a field of the class, created once for each Solution object and shared by all of its methods.

Other structures give the same answers more slowly. A sorted list could find a value in O(log n) time but still has to shift elements to insert or remove one. The hash map is the simplest choice that reaches O(1) for all three operations.

Step by step

Create the table in the class body. val freq is an empty scala.collection.mutable.Map[Int, Int]. Statements in a class body run when an object is created, so no constructor is needed, and every method shares the same table. The val fixes which map freq refers to; its contents can still change.
Write count. Its body is freq.getOrElse(value, 0). A value that was never inserted reports 0. This is the last expression of the method, so it is the return value.
Write insert. Assign count(value) + 1 to freq(value). Using count keeps the "missing means 0" rule in one place.
Write remove. Wrap the update in if (count(value) > 0). Removing a value that isn't there then does nothing.
Decrement inside the if. Assign count(value) - 1 to freq(value).

The solution in Scala

class Solution {
    val freq = scala.collection.mutable.Map[Int, Int]()
    def count(value: Int): Int = {
        freq.getOrElse(value, 0)
    }
    def insert(value: Int): Unit = {
        freq(value) = count(value) + 1
    }
    def remove(value: Int): Unit = {
        if (count(value) > 0) {
            freq(value) = count(value) - 1
        }
    }
}

Following the example through, freq goes from empty to 5 -> 1, then 5 -> 1, 2 -> 1, then 5 -> 2, 2 -> 1. Now count(5) returns 2. After remove(5) the entry is 5 -> 1, and count(5) returns 1.

The Scala details worth knowing:

Reading a missing key. freq(value) throws a NoSuchElementException with the message key not found: 99 when the key is absent. getOrElse(value, 0) takes a fallback instead, which is why count uses it.
Index assignment. freq(value) = x is shorthand for freq.update(value, x). It adds the key or replaces the old value.
The result type. insert and remove return Unit, Scala's "nothing useful" result, because they work by changing the table.
Each object has its own table. The map is created per Solution object. A new Solution starts empty, and count(5) on it returns 0.

Complexity

Time: O(1) per operation on average. Each method does a constant number of hash-map lookups and updates. The hash map gives constant time on average, rather than in the worst case.

Space: O(n). The map holds at most one entry per distinct value inserted.

Edge cases and common mistakes

Counting a value never inserted. count(7) returns 0 because of getOrElse.
Removing a value that isn't there. remove(7) does nothing, and count(7) still returns 0. Without the if, the table would store -1 for it, and the next insert would produce 0 instead of 1.
Removing more times than inserted. After insert(5) and two calls to remove(5), the count is 0, not -1.
Entries stay at zero. Removing the last occurrence leaves the key in the map with count 0, for example HashMap(2 -> 1, 5 -> 0). The counts stay correct. If you want the map to shrink, call freq.remove(value) when the count reaches 0.
Using a list. A list or array makes count and remove linear, which breaks the O(1) requirement.
Making freq a local variable. Each method would get its own table, and nothing would be remembered between calls.

Testing

The example sequence returns 2, then 1 for the two count(5) calls.
On a fresh object, count(5) returns 0.
remove(7) followed by count(7) returns 0.
insert(5) then remove(5) twice, then count(5), returns 0.

Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free