Array Contains in JavaScript

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 includes(), 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 exists within an array of integers. This is a fundamental problem in computer science with applications in search algorithms, data validation, and more. A common pitfall is to use built-in functions like includes(), which simplifies the task but does not help in understanding the underlying algorithm.

Approach

To solve this problem, we can iterate through the array and check each element to see if it matches the given value. This is a straightforward approach but ensures we understand the basics of array traversal and comparison.

Naive Solution

The naive solution involves iterating through each element of the array and checking if it matches the given 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 for very large arrays, it is sufficient for this problem.

Optimized Solution

Given the constraints of the problem, the naive solution is already optimal. We cannot improve the time complexity beyond O(n) for this problem because we need to check each element at least once.

Algorithm

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

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

Code Implementation

function contains(nums, value) {
  // Iterate 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) {
      return true; // Return true if a match is found
    }
  }
  return false; // Return false if no match is found
}

// Test cases
console.log(contains([1, 2, 4, 5], 4)); // true
console.log(contains([-1, 2, -4, 0, 10], 7)); // 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 once. 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 a variety of test cases:

Simple cases with small arrays.
Edge cases like empty arrays and single-element arrays.
Arrays with negative numbers and zeros.
Large arrays to test performance.

Example test cases:

console.log(contains([1, 2, 4, 5], 4)); // true
console.log(contains([-1, 2, -4, 0, 10], 7)); // false
console.log(contains([], 1)); // false
console.log(contains([1], 1)); // true
console.log(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, naive solution to ensure you understand the basics.
Think about edge cases and how your solution handles them.
Optimize your solution if possible, but ensure it remains correct and readable.

Conclusion

In this blog post, we discussed how to determine if a given integer exists within an array of integers. We explored a straightforward approach with a time complexity of O(n) and provided a detailed explanation of the algorithm and code implementation. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice, consider the following resources:

LeetCode - A platform for practicing coding problems.
GeeksforGeeks - A comprehensive resource for learning algorithms and data structures.
MDN Web Docs - Official documentation for JavaScript.

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