Start learning free

LESSON 233 OF 338 · HASH TABLE

Collection of Numbers in Go: O(1) Operations with a Frequency Map

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 5
    Ctrl + Enter to check

    GO · HASH TABLE

    Collection Of Numbers in Go, explained

    Problem overview

    The task is to build a small data structure, Solution, that holds a collection of integers, initially empty, and supports three operations: Insert(val) adds one copy of a number, Remove(val) removes one copy, and Count(val) returns how many copies are currently present. Duplicates are allowed, so this is a multiset.

    In the example, the calls are Insert(5), Insert(2), Insert(5), Count(5), Remove(5), Count(5). After the first three calls the collection holds two 5s and one 2, so the first count is 2. After the removal one 5 is left, so the second count is 1.

    Every operation must run in O(1) time, and the structure may use O(n) space for n stored numbers.

    Approach: store counts, not elements

    A slice of numbers would make Count and Remove scan the whole slice, which is O(n). The order of the numbers does not matter here, only how many copies of each one exist. So store exactly that: a map from each number to its count. Map reads, writes and increments take O(1) on average, and the map holds one entry per distinct number, which fits the space limit.

    Go helps in a lucky way: reading a key that is not in a map returns the zero value, which is 0 for an int. A number that was never inserted therefore counts as 0 copies with no special case, and incrementing a missing key creates it with the value 1.

    Here is the example as the map sees it. It starts empty. Insert(5) makes it {5: 1}, Insert(2) makes it {5: 1, 2: 1}, and the second Insert(5) makes it {5: 2, 2: 1}. Count(5) reads 2. Remove(5) sees a count of 2, which is positive, and lowers it to 1, so the last Count(5) reads 1. No operation ever looks at more than one key, which is why none of them depends on how many numbers are stored.

    Step by step

    1. Add the freq field to the struct, of type map[int]int. The provided Constructor creates the map with make, so the field only has to be declared.
    2. Write Count as a single read of s.freq[val]. Missing numbers report 0.
    3. Write Insert as an increment of s.freq[val]. The first insert of a number turns the implicit 0 into 1.
    4. Guard Remove with a check that the stored count is positive. Without it, removing a number that is not present would store -1, and a later Insert would bring it to 0 instead of 1.
    5. Decrement inside the guard to record the removal.

    The solution in Go

    type Solution struct {
    freq map[int]int
}

func Constructor() Solution {
    return Solution{freq: make(map[int]int)}
}

func (s *Solution) Count(val int) int {
    return s.freq[val]
}

func (s *Solution) Insert(val int) {
    s.freq[val]++
}

func (s *Solution) Remove(val int) {
    if s.freq[val] > 0 {
        s.freq[val]--
    }
}

    The Go details:

    • Structs and methods instead of classes. Go has no classes. Data lives in a struct, and methods are functions with a receiver written before the name, here (s *Solution). The receiver is a pointer so that methods can change the struct, and the map inside is shared anyway because a map value is a reference to its table.
    • The constructor is a plain function. Constructor() returns a Solution whose freq was built with make. A zero Solution{} has a nil map: Count would still work, but Insert would panic with "assignment to entry in nil map".
    • s.freq[val]++ on a map entry. It reads the entry (0 if absent), adds one and writes it back. In Go, ++ and -- are statements, so they cannot be used as values.
    • Reading does not insert. Count on a missing number leaves the map unchanged.

    Complexity

    Time: O(1) per operation on average. Each method does at most one map read and one map write.

    Space: O(n). The map has one entry per distinct number ever inserted, which is at most n.

    Edge cases and common mistakes

    • Removing a number that is absent. The guard makes it a no-op. Without the guard the count would become -1.
    • Removing more times than inserted. After Insert(5) and two calls to Remove(5), the count is 0, not -1.
    • Counting an unknown number. Count(9) on an empty collection returns 0.
    • Zero counts stay in the map. Removing the last copy of a number leaves the key with the value 0 instead of deleting it. That is harmless for Count, and the entry count still stays within the number of distinct values inserted. Calling delete(s.freq, val) when the count reaches 0 would keep the map smaller, but the lesson does not need it.
    • Using the zero value of the struct. Always create the collection with Constructor(), so the map exists before the first Insert.

    Testing

    • The example calls give counts 2 then 1.
    • Remove(9) followed by Count(9) on an empty collection gives 0.
    • Insert(5), then Remove(5) twice, then Count(5) gives 0.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free