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

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 without using any built-in functions. This is a common problem in programming that helps in understanding basic iteration and counting techniques.

Common applications of this problem include data analysis, where you might need to count occurrences of specific data points, and in algorithms that require frequency analysis.

Potential pitfalls include not correctly iterating through the entire array or incorrectly counting the occurrences.

Approach

To solve this problem, we can use a simple iteration approach:

1. Initialize a counter to zero.
2. Iterate through each element in the array.
3. If the current element matches the given value, increment the counter.
4. After the iteration, the counter will hold the number of occurrences of the given value.

This approach is straightforward and has a time complexity of O(n), where n is the number of elements in the array. This is because we need to check each element once.

Algorithm

1. Initialize a variable count to 0.
2. Loop through each element num in the array nums.
3. If num is equal to the given value, increment count by 1.
4. Return the value of count.

Code Implementation

def count_occurrences(nums, value):
    # Initialize the counter to 0
    count = 0
    
    # Iterate through each element in the array
    for num in nums:
        # If the current element matches the given value, increment the counter
        if num == value:
            count += 1
    
    # Return the final count
    return count

# Example usage
nums = [1, 4, 2, 2, 5, 2]
value = 2
print(count_occurrences(nums, value))  # Output: 3

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 iterate through each element exactly once.

The space complexity is O(1) because we are using a constant amount of extra space (the counter variable).

Edge Cases

Consider the following edge cases:

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

Examples:

print(count_occurrences([], 2))  # Output: 0
print(count_occurrences([1, 3, 4], 2))  # Output: 0
print(count_occurrences([2, 2, 2], 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 function handles them efficiently.

Example test cases:

assert count_occurrences([1, 4, 2, 2, 5, 2], 2) == 3
assert count_occurrences([], 2) == 0
assert count_occurrences([1, 3, 4], 2) == 0
assert count_occurrences([2, 2, 2], 2) == 3
assert count_occurrences([1, 1, 1, 1, 1], 1) == 5

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Break down the problem into smaller steps.
• Think about the simplest way to solve the problem first.
• Consider edge cases and how your solution handles them.
• Write clean and readable code with comments to explain your logic.

To improve your problem-solving skills, practice similar problems and study different algorithms. Platforms like LeetCode, HackerRank, and CodeSignal offer a variety of challenges to help you practice.

Conclusion

In this blog post, we discussed how to count the number of occurrences of a given value in an array without using built-in functions. 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.

Keep practicing and exploring different problems to enhance your skills further.

Additional Resources

• LeetCode - Practice coding problems
• HackerRank - Coding challenges and competitions
• CodeSignal - Coding practice and assessments
• Python Official Documentation - Learn more about Python