Collection of Numbers in C++ with O(1) Time Complexity

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.

Understanding the Problem

The core challenge of this problem is to efficiently manage a collection of integers with the ability to insert, remove, and count occurrences of integers in constant time. This is significant in scenarios where real-time data processing is required, such as in databases or live data feeds.

Potential pitfalls include ensuring that the removal operation correctly handles cases where the integer is not present in the collection and maintaining the count accurately.

Approach

To solve this problem, we can use a hash map (unordered_map in C++) to store the integers and their counts. This allows us to perform insertions, deletions, and lookups in average O(1) time.

Naive Solution

A naive solution might involve using a list or array to store the integers and iterating through it to count occurrences. However, this would result in O(n) time complexity for the count operation, which is not optimal.

Optimized Solution

Using an unordered_map, we can achieve O(1) time complexity for all operations:

Insert: Increment the count of the integer in the map.
Remove: Decrement the count of the integer in the map, and remove it if the count reaches zero.
Count: Return the count of the integer from the map.

Algorithm

Here is a step-by-step breakdown of the algorithm:

Initialize an unordered_map to store the integers and their counts.
For the insert operation, increment the count of the integer in the map.
For the remove operation, decrement the count of the integer in the map. If the count reaches zero, remove the integer from the map.
For the count operation, return the count of the integer from the map.

Code Implementation


#include <iostream>
#include <unordered_map>

class Collection {
private:
    std::unordered_map<int, int> countMap;

public:
    // Insert a new integer into the collection
    void insert(int num) {
        countMap[num]++;
    }

    // Remove an integer from the collection
    void remove(int num) {
        if (countMap.find(num) != countMap.end()) {
            countMap[num]--;
            if (countMap[num] == 0) {
                countMap.erase(num);
            }
        }
    }

    // Return the number of occurrences of a given integer
    int count(int num) {
        if (countMap.find(num) != countMap.end()) {
            return countMap[num];
        }
        return 0;
    }
};

int main() {
    Collection collection;
    collection.insert(5);
    collection.insert(2);
    collection.insert(5);
    std::cout << collection.count(5) << " "; // Output: 2
    collection.remove(5);
    std::cout << collection.count(5) << std::endl; // Output: 1
    return 0;
}

Complexity Analysis

The time complexity for each operation (insert, remove, count) is O(1) due to the use of an unordered_map. The space complexity is O(n), where n is the number of unique integers in the collection.

Edge Cases

Potential edge cases include:

Removing an integer that is not in the collection: The algorithm handles this by checking if the integer exists in the map before decrementing.
Counting an integer that is not in the collection: The algorithm returns 0 if the integer is not found in the map.

Testing

To test the solution comprehensively, consider the following test cases:

Inserting and counting multiple integers.
Removing integers and checking the count after each removal.
Handling edge cases such as removing non-existent integers and counting non-existent integers.

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to think about the data structures that provide the most efficient operations for the given requirements. Practice solving similar problems and study different data structures to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to efficiently manage a collection of integers with insert, remove, and count operations in constant time using an unordered_map in C++. Understanding and implementing such solutions is essential for optimizing performance in real-time data processing scenarios.