Number of Occurrences in Array in C++ (Time Complexity: O(n))

Given an array of integers nums, count and return the number of occurrences of a given value.

Example:

Input: nums = [1, 4, 2, 2, 5, 2], value = 2
Output: 3
Explanation: the value 2 appears 3 times in the array

Understanding the Problem

The core challenge of this problem is to count the number of times a specific value appears in an array. This is a common problem in data processing and analysis, where you need to determine the frequency of certain elements.

Potential pitfalls include not correctly iterating through the entire array or miscounting the occurrences due to logic errors.

Approach

To solve this problem, we can use a simple linear scan of the array. This approach ensures that we check each element exactly once, making it efficient with a time complexity of O(n), where n is the number of elements in the array.

Here is a step-by-step approach:

Initialize a counter to zero.
Iterate through each element of the array.
For each element, check if it matches the given value.
If it matches, increment the counter.
After the loop, the counter will hold the number of occurrences of the given value.

Algorithm

Let's break down the algorithm step-by-step:

Initialize a variable count to 0.
Loop through each element in the array nums.
For each element, compare it with the value.
If the element is equal to value, increment count.
Return the count after the loop ends.

Code Implementation


#include <iostream>
#include <vector>

int countOccurrences(const std::vector<int>& nums, int value) {
    // Initialize the counter to 0
    int count = 0;
    
    // Iterate through each element in the array
    for (int num : nums) {
        // If the current element matches the value, increment the counter
        if (num == value) {
            count++;
        }
    }
    
    // Return the total count of occurrences
    return count;
}

int main() {
    // Example usage
    std::vector<int> nums = {1, 4, 2, 2, 5, 2};
    int value = 2;
    
    // Call the function and print the result
    std::cout << "The value " << value << " appears " << countOccurrences(nums, value) << " times in the array." << std::endl;
    
    return 0;
}

Complexity Analysis

The time complexity of this approach is O(n), where n is the number of elements in the array. This is because we are iterating through the array once. The space complexity is O(1) since we are using only a constant amount of extra space for the counter.

Edge Cases

Consider the following edge cases:

An empty array: The function should return 0.
An array where no elements match the value: The function should return 0.
An array where all elements match the value: The function should return the length of the array.

Example edge cases:

Input: nums = [], value = 2
Output: 0

Input: nums = [1, 3, 4], value = 2
Output: 0

Input: nums = [2, 2, 2], value = 2
Output: 3

Testing

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

Simple cases with a few elements.
Edge cases as discussed above.
Large arrays to ensure the solution handles them efficiently.

Example test cases:

Input: nums = [1, 4, 2, 2, 5, 2], value = 2
Output: 3

Input: nums = [1, 1, 1, 1, 1], value = 1
Output: 5

Input: nums = [1, 2, 3, 4, 5], value = 6
Output: 0

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Understand the problem requirements and constraints thoroughly.
Start with a simple, brute-force solution to understand the basic logic.
Optimize the solution by reducing unnecessary computations or using efficient data structures.
Test the solution with various cases, including edge cases.

To improve problem-solving skills, practice regularly on coding challenge platforms and study different algorithms and data structures.

Conclusion

In this blog post, we discussed how to count the number of occurrences of a given value in an array using a simple and efficient approach. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in programming.

Additional Resources

For further reading and practice, consider the following resources: