Collection of Numbers in O(1) Time Complexity using Java

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 such that we can insert, remove, and count occurrences of integers in constant time, O(1). This is significant in scenarios where we need to perform a large number of operations quickly, such as in real-time systems or high-frequency trading applications.

Potential pitfalls include not using the right data structure, which could lead to inefficient operations. For example, using a list would result in O(n) time complexity for counting occurrences.

Approach

To achieve O(1) time complexity for all operations, we can use a HashMap in Java. The HashMap will store each integer as a key and its count as the value.

Naive Solution

A naive solution might involve using a list to store the integers and iterating through the list to count occurrences. However, this approach is not optimal as it results in O(n) time complexity for counting and removing elements.

Optimized Solution

The optimized solution involves using a HashMap:

Insert: Increment the count of the integer in the HashMap.
Remove: Decrement the count of the integer in the HashMap. If the count reaches zero, remove the integer from the HashMap.
Count: Return the count of the integer from the HashMap.

Algorithm

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

Initialize a HashMap to store integers and their counts.
For the insert operation, check if the integer is already in the HashMap. If it is, increment its count. If not, add it with a count of 1.
For the remove operation, check if the integer is in the HashMap. If it is, decrement its count. If the count becomes zero, remove the integer from the HashMap.
For the count operation, return the count of the integer from the HashMap. If the integer is not in the HashMap, return 0.

Code Implementation

import java.util.HashMap;

public class CollectionOfNumbers {
    private HashMap<Integer, Integer> map;

    public CollectionOfNumbers() {
        map = new HashMap<>();
    }

    // Insert a new integer into the collection
    public void insert(int num) {
        map.put(num, map.getOrDefault(num, 0) + 1);
    }

    // Remove an integer from the collection
    public void remove(int num) {
        if (map.containsKey(num)) {
            if (map.get(num) == 1) {
                map.remove(num);
            } else {
                map.put(num, map.get(num) - 1);
            }
        }
    }

    // Return the number of occurrences of a given integer
    public int count(int num) {
        return map.getOrDefault(num, 0);
    }

    public static void main(String[] args) {
        CollectionOfNumbers collection = new CollectionOfNumbers();
        collection.insert(5);
        collection.insert(2);
        collection.insert(5);
        System.out.println(collection.count(5)); // Output: 2
        collection.remove(5);
        System.out.println(collection.count(5)); // Output: 1
    }
}

Complexity Analysis

The time complexity for each operation (insert, remove, count) is O(1) because HashMap operations (put, get, remove) are O(1) on average.

The space complexity is O(n), where n is the number of unique integers in the collection, as we are storing each unique integer and its count in the HashMap.

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 HashMap.
Counting an integer that is not in the collection: The algorithm returns 0 in this case.
Inserting and removing the same integer multiple times: The HashMap correctly updates the count each time.

Testing

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

Insert multiple integers and count their occurrences.
Remove integers and check the count after each removal.
Count integers that have not been inserted.
Insert and remove the same integer multiple times.

Using a testing framework like JUnit can help automate these tests.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Identify the operations that need to be optimized and choose the right data structure accordingly.
Think about edge cases and how your solution handles them.
Break down the problem into smaller parts and solve each part step-by-step.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to efficiently manage a collection of integers using a HashMap in Java. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing efficient algorithms and improving problem-solving skills.

Additional Resources

For further reading and practice, consider the following resources: