LESSON 237 OF 348 · HASH TABLE

Collection of Numbers in TypeScript: 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 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 5

Guided

Ctrl + Enter to check

TYPESCRIPT · HASH TABLE

Collection Of Numbers in TypeScript, explained

Problem overview

The lesson asks for a class that keeps a collection of integers, initially empty, and supports three operations:

insert(val) adds one occurrence of val;
remove(val) removes one occurrence of val;
count(val) returns how many occurrences of val the collection holds.

The same number can be inserted several times. 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, because 5 was inserted twice. After one remove(5), the second returns 1.

Every operation must run in O(1) time, and the collection may use O(n) space, where n is the number of distinct values stored.

Approach: store a frequency per value

A list of all inserted numbers would make count and remove scan the whole list, which is O(n). But the collection never needs to remember the order of the numbers or which copy is which. It only needs to know how many copies of each value it holds.

So keep a hash map from each value to its number of occurrences. All three operations then become one lookup or one update:

count(val) reads the stored count, or gives 0 when the value was never stored.
insert(val) adds 1 to the count.
remove(val) subtracts 1, but only when the count is positive, so a value that isn't in the collection stays at 0.

Hash map reads and writes take O(1) time on average, which gives the required running time.

Step by step

Declare the property. A TypeScript class must declare its properties, so the first line of the class body is freq: Record<number, number>;, a map from numbers to numbers. In the constructor, this.freq = {} starts it empty.
Write count. Return this.freq[val] || 0. A missing key reads as undefined, which is falsy, so || turns it into 0. A stored 0 also gives 0, which is correct.
Write insert. Set this.freq[val] to this.count(val) + 1. Going through count handles the first insertion of a value, when nothing is stored yet.
Guard remove. Wrap the update in if (this.count(val) > 0). Removing a value that isn't there then changes nothing.
Decrease the count. Inside the if, subtract 1 from this.freq[val]. The entry is known to exist and to be positive, so updating it in place is safe.

The solution in TypeScript

class Solution {
    freq: Record<number, number>;
    constructor() {
        this.freq = {};
    }

    count(val: number): number {
        return this.freq[val] || 0;
    }

    insert(val: number): void {
        this.freq[val] = this.count(val) + 1;
    }

    remove(val: number): void {
        if (this.count(val) > 0) {
            this.freq[val] -= 1;
        }
    }
}

The TypeScript details worth a closer look:

Record<number, number> is the type of an object whose keys are numbers and whose values are numbers. Types are erased when the code is compiled to JavaScript, so at run time freq is just an ordinary object.
Number keys become strings. JavaScript objects store keys as strings, so freq[5] is stored under "5". Lookups with the same number always find it, and negative numbers work too: -3 is stored as "-3".
Why the property declaration is needed. Without the line freq: Record<number, number>;, the compiler reports that freq does not exist on the class. A property that is only assigned inside the constructor still has to be declared in the class body.
Missing keys give undefined. TypeScript types this.freq[val] as a number, but when the key is absent the value at run time is undefined. The type doesn't know that, which is why || 0 matters.
Why insert uses count. undefined + 1 is NaN, and NaN would then be stored for that key. Starting from this.count(val) always begins at a real number.
Counts are not deleted. After the last copy is removed, the key stays with the value 0. That is harmless, because count returns 0 either way.
|| versus ??. || replaces every falsy value, ?? only undefined and null. Here both work, because replacing a 0 with 0 changes nothing.

Complexity

Time: O(1) per operation. Each method does a fixed number of object reads and writes, which take constant time on average.

Space: O(n). The object holds one entry per distinct value ever inserted, so it grows with the number of distinct values, not with the number of calls.

Edge cases and common mistakes

Counting a value never inserted. count(7) returns 0, thanks to the || 0.
Removing a value that isn't there. With the guard, remove(7) does nothing. Without it, an in-place subtraction on the missing entry stores NaN, and removing a value more often than it was inserted pushes its count below 0.
Removing more times than inserting. After insert(-3) and two remove(-3) calls, count(-3) is still 0. The second removal sees a count of 0 and skips the update.
Incrementing directly. this.freq[val] += 1 on a missing key gives NaN. This is why insert goes through count.
Forgetting that remove removes one copy. It lowers the count by 1. It doesn't delete every occurrence of the value.
Using an array of all inserted numbers. Searching it makes count and remove take O(n) time, which breaks the limit.

Testing

The example calls give counts 2 and then 1 for the value 5.
On a new collection, count(7) returns 0.
On a new collection, remove(7) followed by count(7) returns 0.
insert(-3), remove(-3), remove(-3), count(-3) returns 0.

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

Start learning free