LESSON 261 OF 415 · HASH TABLE

Collection of Numbers in Swift: Counting with a Dictionary

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 6

Guided

Ctrl + Enter to check

SWIFT · HASH TABLE

Collection Of Numbers in Swift, explained

Problem overview

The class Solution models a collection of integers that starts out empty. It supports three operations: insert(_:) adds a number, remove(_:) takes one occurrence of a number out, and count(_:) tells how many times a number is currently in the collection. A number can be inserted several times, and each insert counts.

In the example, the calls are insert(5), insert(2), insert(5), count(5), remove(5) and count(5). The first count(5) returns 2, since 5 went in twice. After the removal the second count(5) returns 1.

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

Approach: store a count per number

An array of all inserted numbers would make count and remove scan the whole array, which is O(n). The collection never needs the numbers in order or even as separate items. It only needs to know how many copies of each exist. A hash map from number to count answers all three questions directly:

insert(v) increases the count of v by one.
remove(v) decreases it by one, if it is above zero.
count(v) reads it, giving 0 for a number that was never inserted.

Dictionary reads and writes take O(1) time on average, and the dictionary holds at most one entry per distinct number, so the space is O(n).

Here is the table for the example. After the three inserts it is [5: 2, 2: 1]. The first count(5) reads 2. remove(5) sees a count of 2, which is positive, and stores 1. The second count(5) reads 1.

The dictionary works because a hash map turns a key into a position in its storage with a hash function. It can jump to the entry without comparing against every other key. That jump is what makes each operation constant time on average, and why the other keys' counts are never touched.

Step by step

Declare the table. A stored property freq of type [Int: Int] sits at the top of the class, so every method shares it. It maps a number to its number of occurrences.
Initialise it. Swift requires every stored property to have a value by the end of init, so the initialiser assigns the empty dictionary [:].
Write count. Return freq[val, default: 0]. The plain subscript returns an optional Int?, but the default: form returns a plain Int and gives 0 for a missing key.
Write insert. Store count(val) + 1 back into freq[val]. Assigning through the subscript creates the entry if it is missing and replaces it otherwise.
Write remove. Guard with if count(val) > 0, so removing a number that isn't present does nothing instead of storing -1.
Decrease the count. Inside the if, store count(val) - 1.

The solution in Swift

class Solution {
    var freq: [Int: Int]
    init() {
        freq = [:]
    }

    func count(_ val: Int) -> Int {
        return freq[val, default: 0]
    }

    func insert(_ val: Int) {
        freq[val] = count(val) + 1
    }

    func remove(_ val: Int) {
        if count(val) > 0 {
            freq[val] = count(val) - 1
        }
    }
}

Swift details worth knowing:

Classes need initialisers for stored properties. var freq: [Int: Int] has no default value, so init() must set it. Writing var freq: [Int: Int] = [:] would give it a default, and then the empty init() would be optional.
Methods call each other without self.. Inside the class, count(val) refers to the method, and freq to the property.
Classes are reference types. Every variable that holds the same Solution object sees the same collection. Calling insert and remove on a let constant works too, because the object itself changes, not the variable.
The default: subscript doesn't insert the key when only reading, so count on an unknown number leaves the dictionary alone.

Complexity

The cost here comes from the dictionary. Hashing an Int takes constant time, and the average cost of a lookup does not grow with the number of entries.

Time: O(1) per operation on average. Each method does one or two dictionary reads or writes.

Space: O(n), where n is the number of distinct values stored.

Edge cases and common mistakes

Counting a number that was never inserted. It returns 0, thanks to default: 0.
Removing a number that isn't there. Without the if, the count would become -1 and later inserts would be off by one. With it, remove(7) on an empty collection changes nothing.
Removing the last copy. The entry stays in the dictionary with the value 0. Reads still return 0, so the behaviour is correct, but the dictionary keeps one key for every number ever inserted. Setting the entry to nil when it reaches zero would free that space.
Removing more than was inserted. After insert(5) and two calls of remove(5), the count is 0, not -1.
Using a plain subscript. freq[val] + 1 doesn't compile, because freq[val] is optional.
Using an array. It would break the O(1) requirement.

Testing

After insert(5), insert(2), insert(5), count(5) is 2.
After one remove(5), count(5) is 1.
count(7) on a collection that never held 7 is 0, and remove(7) leaves it at 0.
After remove(5) a second time, count(5) is 0, and a third remove(5) keeps it at 0.

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

Start learning free