Algocademy Logo

Array Contains - Time Complexity: O(n) - Python


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 the in operator, it would defy the whole 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 without using Python's built-in in operator. This is a fundamental problem in computer science, often used to teach basic iteration and search techniques.

Common applications include searching for an element in a list, which is a frequent operation in many algorithms and data structures.

Potential pitfalls include misunderstanding the requirement to avoid built-in functions and not handling edge cases such as an empty array.

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 linear search algorithm.

Let's discuss a naive solution and then optimize it:

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. This is because in the worst case, we might have to check every element.

Optimized Solution

Since the naive solution already has a time complexity of O(n), which is optimal for this problem, there isn't much room for optimization in terms of time complexity. However, we can ensure that our implementation is clean and efficient.

Algorithm

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

  1. Initialize a loop to iterate through each element in the array nums.
  2. For each element, check if it is equal to value.
  3. If a match is found, return True.
  4. If the loop completes without finding a match, return False.

Code Implementation

def contains(nums, value):
    # Iterate through each element in the array
    for num in nums:
        # Check if the current element is equal to the value
        if num == value:
            return True
    # If no match is found, return False
    return False

# Example usage
print(contains([1, 2, 4, 5], 4))  # Output: True
print(contains([-1, 2, -4, 0, 10], 7))  # Output: False

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) since we are not using any additional space that scales with the input size.

Edge Cases

Consider the following edge cases:

  • 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.
  • Multiple occurrences of the value: The function should return True as soon as it finds the first match.

Examples:

contains([], 1) -> False
contains([1], 1) -> True
contains([1, 2, 3, 1], 1) -> True

Testing

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

  • Simple cases with small arrays.
  • Edge cases such as empty arrays and single-element arrays.
  • Arrays with negative numbers and zero.
  • Arrays where the value is not present.

Example test cases:

assert contains([1, 2, 4, 5], 4) == True
assert contains([-1, 2, -4, 0, 10], 7) == False
assert contains([], 1) == False
assert contains([1], 1) == True
assert contains([1, 2, 3, 1], 1) == True

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 and then look for optimizations.
  • Write clean and readable code with comments to explain your logic.
  • Test your solution with a variety of test cases, including edge cases.

To improve problem-solving skills, practice similar problems and study different algorithms and data structures.

Conclusion

In this blog post, we discussed how to solve the problem of checking if a value exists 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 computer science.

Keep practicing and exploring further to enhance your skills!

Additional Resources

For further reading and practice, consider the following resources: