Array Contains in C++

Given an array of integers nums and another integer value, check if value occurs in nums.

If the value occurs in nums, return true; otherwise return false.

Examples:

contains([1, 2, 4, 5], 4) -> true

contains([-1, 2, -4, 0, 10], 7) -> false

Note:

Do not use builtin functions such as find() or includes(), it would defy the purpose of the challenge. Write the whole code yourself.

Understanding the Problem

The core challenge of this problem is to determine if a given integer value exists within an array of integers nums. This is a fundamental problem in computer science, often referred to as the "search problem". It has significant applications in various fields such as database querying, information retrieval, and more.

Potential pitfalls include misunderstanding the problem constraints or attempting to use built-in functions which are not allowed in this challenge.

Approach

To solve this problem, we need to iterate through the array and check each element to see if it matches the given value. This is a straightforward approach but let's break it down step-by-step:

Naive Solution

The naive solution involves iterating through each element of the array and checking if it matches the value. This approach has a time complexity of O(n), where n is the number of elements in the array. While this is not the most optimized solution, it is simple and effective for this problem.

Optimized Solution

Given the constraints of the problem, the naive solution is actually optimal. Since we need to check each element at least once to determine if the value exists in the array, we cannot do better than O(n) time complexity.

Algorithm

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

Initialize a loop to iterate through each element of the array nums.
For each element, check if it is equal to the value.
If a match is found, return true.
If the loop completes without finding a match, return false.

Code Implementation


#include <iostream>
#include <vector>

bool contains(const std::vector<int>& nums, int value) {
    // Iterate through each element in the array
    for (int num : nums) {
        // Check if the current element is equal to the value
        if (num == value) {
            return true; // Value found
        }
    }
    return false; // Value not found
}

int main() {
    std::vector<int> nums1 = {1, 2, 4, 5};
    int value1 = 4;
    std::cout << std::boolalpha << contains(nums1, value1) << std::endl; // Output: true

    std::vector<int> nums2 = {-1, 2, -4, 0, 10};
    int value2 = 7;
    std::cout << std::boolalpha << contains(nums2, value2) << std::endl; // Output: false

    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 may need to check each element in the worst case. The space complexity is O(1) as we are not using any additional space that scales with the input size.

Edge Cases

Potential edge cases include:

An empty array: The function should return false.
An array with one element: The function should correctly identify if the single element matches the value.
All elements are the same but not equal to value: The function should return false.

Examples:

contains([], 1) -> false
contains([1], 1) -> true
contains([2, 2, 2], 1) -> false

Testing

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

Basic cases with small arrays.
Edge cases as mentioned above.
Large arrays to test performance.

Using a testing framework like Google Test can help automate and manage these tests effectively.

Thinking and Problem-Solving Tips

When approaching such problems, it is crucial to:

Understand the problem statement and constraints thoroughly.
Start with a simple solution and then think about optimizations.
Consider edge cases and test your solution against them.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to determine if a value exists in an array without using built-in functions. We explored a straightforward approach, implemented it in C++, and analyzed its complexity. Understanding and solving such problems is fundamental in computer science and helps build a strong foundation for more complex challenges.

Additional Resources

For further reading and practice, consider the following resources:

Array Contains - Time Complexity: O(n) - C++