Start learning free

LESSON 256 OF 410 · HASH TABLE

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

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 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.


STEP 1 OF 6
    Ctrl + Enter to check

    JAVA · HASH TABLE

    Collection Of Numbers in Java, explained

    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:

    1. Initialize a HashMap to store integers and their counts.
    2. 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.
    3. 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.
    4. 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:

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