Number of Occurrences in Array - JavaScript Solution with O(n) Time Complexity

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

Note:

Do not use builtin functions, it would defy the purpose of the challenge. Write the whole code yourself.

Understanding the Problem

The core challenge of this problem is to count the number of times a specific value appears in an array of integers. This is a common problem in programming, often used to understand basic iteration and counting techniques. The significance of this problem lies in its simplicity and the foundational concepts it reinforces, such as loops and conditionals.

Potential pitfalls include misunderstanding the problem requirements, such as using built-in functions which are not allowed in this challenge, or incorrectly handling edge cases like an empty array or an array with no occurrences of the given value.

Approach

To solve this problem, we can use a simple loop to iterate through the array and count the occurrences of the given value. This approach is straightforward and efficient, with a time complexity of O(n), where n is the length of the array.

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

Initialize a counter to zero.
Loop through each element in the array.
For each element, check if it matches the given value.
If it matches, increment the counter.
After the loop, return the counter.

Algorithm

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

Initialize a variable count to 0. This will keep track of the number of occurrences.
Use a for loop to iterate through each element in the array nums.
Inside the loop, use an if statement to check if the current element is equal to the given value.
If the condition is true, increment the count by 1.
After the loop ends, return the count.

Code Implementation

// Function to count occurrences of a value in an array
function countOccurrences(nums, value) {
    // Initialize the counter to 0
    let count = 0;
    
    // Loop through each element in the array
    for (let i = 0; i < nums.length; i++) {
        // Check if the current element matches the given value
        if (nums[i] === value) {
            // Increment the counter if a match is found
            count++;
        }
    }
    
    // Return the final count
    return count;
}

// Example usage:
const nums = [1, 4, 2, 2, 5, 2];
const value = 2;
console.log(countOccurrences(nums, value)); // Output: 3

Complexity Analysis

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

Edge Cases

Here are some potential edge cases and how the algorithm handles them:

Empty array: If the array is empty, the function will return 0 since there are no elements to count.
No occurrences: If the given value does not exist in the array, the function will return 0.
All elements match: If all elements in the array are the given value, the function will return the length of the array.

Examples:

// Edge case: Empty array
console.log(countOccurrences([], 2)); // Output: 0

// Edge case: No occurrences
console.log(countOccurrences([1, 3, 4, 5], 2)); // Output: 0

// Edge case: All elements match
console.log(countOccurrences([2, 2, 2, 2], 2)); // Output: 4

Testing

To test the solution comprehensively, we should include a variety of test cases:

Basic cases with a few elements.
Edge cases like an empty array, no occurrences, and all elements matching.
Large arrays to ensure the solution handles them efficiently.

Example test cases:

// Basic test cases
console.log(countOccurrences([1, 4, 2, 2, 5, 2], 2)); // Output: 3
console.log(countOccurrences([1, 1, 1, 1], 1)); // Output: 4

// Edge cases
console.log(countOccurrences([], 2)); // Output: 0
console.log(countOccurrences([1, 3, 4, 5], 2)); // Output: 0
console.log(countOccurrences([2, 2, 2, 2], 2)); // Output: 4

// Large array
const largeArray = new Array(1000000).fill(2);
console.log(countOccurrences(largeArray, 2)); // Output: 1000000

Thinking and Problem-Solving Tips

When approaching such problems, it's important to:

Understand the problem requirements and constraints.
Break down the problem into smaller, manageable steps.
Consider edge cases and how your solution handles them.
Write clean, readable code with comments to explain your thought process.
Practice similar problems to improve your problem-solving skills.

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 programming skills. Keep practicing and exploring further to improve your problem-solving abilities.

Additional Resources

For further reading and practice, consider the following resources: