Count Occurrences of an Element
Given an array of integers and a target number, count how many times the target number appears in the array.
Example
Input:
- Array: [1, 2, 3, 2, 4, 2]
- Target: 2
Output: 3
Explanation: The number 2 appears 3 times in the given array.
Approaches
Brute Force Approach
Idea
The brute force approach involves iterating through the array and manually counting each occurrence of the target element.
Steps
- Initialize a counter to zero.
- Loop through each element in the array.
- If the current element matches the target element, increment the counter.
- Return the counter after the loop completes.
Time Complexity
- O(n), where n is the length of the array. We have to traverse the array once.
Space Complexity
- O(1), no extra space is used except for the counter.
Example Code
Dry Run
For arr = [1, 2, 3, 2, 4, 2] and target = 2:
- Initialize
count = 0.
- Check each element:
1 is not equal to 2.2 is equal to 2, increment count.3 is not equal to 2.2 is equal to 2, increment count.4 is not equal to 2.2 is equal to 2, increment count.
- Final count =
3.
Efficient Approach using reduce()
Idea
We can use JavaScript's built-in reduce() function to count occurrences without creating an intermediate array.
Steps
- Use the
reduce() method to iterate through the array and count occurrences.
- Return the final count.
Time Complexity
- O(n), where n is the length of the array.
Space Complexity
- O(1), as we only use a single accumulator variable.
Example Code
Dry Run
For arr = [1, 2, 3, 2, 4, 2] and target = 2:
- Initial count: 0
- 1 !== 2, count: 0
- 2 === 2, count: 1
- 3 !== 2, count: 1
- 2 === 2, count: 2
- 4 !== 2, count: 2
- 2 === 2, count: 3
- Final count: 3
Hashmap Approach
Idea
We can use a JavaScript object as a hashmap to count occurrences of all elements in a single pass.
Steps
- Create an empty object to serve as our hashmap.
- Iterate through the array, updating counts in the hashmap.
- Return the count for the target element.
Time Complexity
- O(n), where n is the length of the array.
Space Complexity
- O(k), where k is the number of unique elements in the array.
Example Code
Dry Run
For arr = [1, 2, 3, 2, 4, 2] and target = 2:
- Create empty countMap: {}
- Iterate:
- countMap: {1: 1}
- countMap: {1: 1, 2: 1}
- countMap: {1: 1, 2: 1, 3: 1}
- countMap: {1: 1, 2: 2, 3: 1}
- countMap: {1: 1, 2: 2, 3: 1, 4: 1}
- countMap: {1: 1, 2: 3, 3: 1, 4: 1}
- Return countMap[2], which is 3
Example Test Case
Complexity Analysis
Brute Force Approach
- Time Complexity: O(n), as we iterate through the array once.
- Space Complexity: O(1), constant space for the counter variable.
Efficient Approach (reduce)
- Time Complexity: O(n), as we iterate through the array once.
- Space Complexity: O(1), constant space for the accumulator.
Hashmap Approach
- Time Complexity: O(n), as we iterate through the array once.
- Space Complexity: O(k), where k is the number of unique elements in the array.
Conclusion
We have explored three approaches to count the occurrences of a number in an array:
-
Brute Force Approach:
- Time Complexity: O(n)
- Space Complexity: O(1)
- Pros: Simple implementation, constant space usage
- Cons: Less efficient for multiple queries
-
Efficient Approach (using reduce()):
- Time Complexity: O(n)
- Space Complexity: O(1)
- Pros: Concise code, efficient for single queries
- Cons: May be less readable for beginners
-
Hashmap Approach:
- Time Complexity: O(n)
- Space Complexity: O(k), where k is the number of unique elements
- Pros: Efficient for multiple queries, counts all elements in one pass
- Cons: Higher space usage
All three approaches offer O(n) time complexity, but they differ in space usage and applicability to different scenarios. The brute force and reduce() methods use constant space, making them more space-efficient. The hashmap approach, while using more space, can be beneficial if you need to count occurrences of multiple elements efficiently in a single pass.
Choose the approach that best fits your specific requirements:
- For simplicity and minimal space usage, go with the brute force approach.
- For a balance of conciseness and efficiency in single queries, use the reduce() method.
- If you need to count occurrences of multiple elements or perform repeated queries, the hashmap approach is ideal.