LESSON 236 OF 347 · HASH TABLE

Collection of Numbers in C#: O(1) Operations 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 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

Guided

Ctrl + Enter to check

C# · HASH TABLE

Collection Of Numbers in C#, explained

Problem overview

The lesson asks for a small class that holds a collection of integers, which starts empty, and supports three operations:

Insert(val) adds one occurrence of val.
Remove(val) removes one occurrence of val, if there is one.
Count(val) returns how many occurrences of val are currently 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. The collection holds two 5s after the third call and one after the removal. Each operation must run in O(1) time, and the class may use O(n) space.

Approach: a frequency table

Storing the numbers in a list would make Count a scan of every element, which is O(n), and Remove would need a search too. The operations never ask about order or positions, only about how many copies of each value exist. So store exactly that: a dictionary from each value to its number of occurrences.

With a dictionary freq, the three operations become one-step lookups and updates:

Count(val) is the stored number, or 0 if the value was never inserted.
Insert(val) stores the current count plus one.
Remove(val) stores the current count minus one, but only if the count is above zero.

Each dictionary access is O(1) on average, and the table holds one entry per distinct value, so the space is O(n).

On the example, the table goes from empty to {5: 1}, then {5: 1, 2: 1}, then {5: 2, 2: 1}. Count(5) reads 2. After Remove(5) the entry for 5 is 1, and the second Count(5) reads 1.

Step by step

Declare the table as a field. A Dictionary<int, int> named freq is declared at class level, so all three methods share it.
Create it in the constructor. A field with no initializer is null until something assigns it, and calling a method on a null dictionary would throw NullReferenceException. The collection starts empty, so the constructor assigns a new empty dictionary.
Write Count first. The other two methods reuse it. TryGetValue reports whether the key exists and gives the value through an out variable, so a value that was never inserted yields 0 without an exception.
Write Insert. Assign Count(val) + 1 through the indexer. Assignment adds the key when it is missing and overwrites it otherwise, so one line covers both the first and later insertions.
Guard Remove. Check that Count(val) is positive. Without the check, removing a value that was never inserted would store -1, and a later Count would report a negative number of copies.
Decrement inside the guard. Store Count(val) - 1. The entry stays in the dictionary at 0, which is harmless because Count reports 0 for it, the same as a missing key.

The solution in C#

class Solution {
    Dictionary<int, int> freq;
    public Solution() {
        freq = new Dictionary<int, int>();
    }

    public int Count(int val) {
        return freq.TryGetValue(val, out int v) ? v : 0;
    }

    public void Insert(int val) {
        freq[val] = Count(val) + 1;
    }

    public void Remove(int val) {
        if (Count(val) > 0) {
            freq[val] = Count(val) - 1;
        }
    }
}

Details specific to C#:

Fields and constructors. freq is a private field, since members of a class are private unless marked otherwise. The constructor has the same name as the class and no return type.
out int v. This declares v inline and lets TryGetValue write into it. If the key is missing, v is set to the default 0 and the method returns false.
The conditional operator. condition ? a : b yields a when the condition is true and b otherwise. Here the condition is the bool from TryGetValue.
Indexer reads throw. Writing freq[val] on the right-hand side of an expression when val is not a key throws KeyNotFoundException. That is why Count uses TryGetValue and the other methods go through Count.
Indexer writes do not throw. freq[val] = ... works for new and existing keys alike.

Complexity

Time: O(1) per operation. Each method performs a constant number of dictionary lookups and at most one write. Dictionary operations are O(1) on average.

Space: O(n). The table has at most one entry for each distinct value ever inserted, and never more than the number of Insert calls.

Edge cases and common mistakes

Counting a value that was never inserted. Count(9) returns 0 and does not throw.
Removing a value that is not there. Remove(9) on an empty collection does nothing. Skipping the guard would store -1.
Removing more times than inserted. After Insert(5) and two calls to Remove(5), the count is 0, not -1, thanks to the guard.
Reading with the indexer. return freq[val]; throws KeyNotFoundException the first time a new value is counted.
Forgetting the constructor. Without freq = new ..., the first call fails with NullReferenceException.
Removing the key when the count reaches zero is also correct and would keep the table smaller. The lesson's version leaves the zero entry in place, which does not affect any answer.

Testing

Call the operations in this order on a fresh object and compare the results:

Insert(5), Insert(2), Insert(5), then Count(5) gives 2.
Remove(5), then Count(5) gives 1.
Remove(9), then Count(9) gives 0.

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

Start learning free