Finding the intersection of two arrays is a common programming task that involves identifying the common elements between two sets of data. In this post, we will discuss an approach to implement a function to find the intersection of two arrays, with a step-by-step explanation. We will also discuss the time complexity of this approach in terms of Big O notation.

Approach

We will implement a function to find the intersection of two arrays using the following approach:

1. Create an empty result array to store the intersection.
2. Iterate through the first array.
3. For each element in the first array, check if it exists in the second array.
4. If the element exists in the second array, add it to the result array, and remove it from the second array to prevent duplicates.
5. Return the result array containing the intersection of the two arrays.

Step-by-Step Implementation

Let’s walk through the implementation of this approach in JavaScript:

function findIntersection(arr1, arr2) {
  let intersection = [];

  for (let i = 0; i < arr1.length; i++) {
    let index = arr2.indexOf(arr1[i]);

    if (index !== -1) {
      intersection.push(arr1[i]);
      arr2.splice(index, 1);
    }
  }

  return intersection;
}

Big O Notation of our solution

Big O notation is a way to express the performance of an algorithm by analyzing the relationship between the input size (n) and the number of steps required for the algorithm to complete.

In our findIntersection function, the worst-case time complexity can be determined as follows:

• The outer loop iterates through each element of arr1, which takes O(n) time.
• The indexOf method called inside the loop takes O(m) time in the worst case, where m is the length of arr2.
• The splice method takes O(m) time in the worst case as well.

Thus, the overall time complexity of this function is O(n * (m + m)) or O(n * 2m), which simplifies to O(n * m). This means that the function’s time complexity increases linearly with the size of both input arrays.