Array Intersection Algorithms Compared

Finding the intersection between two arrays is a common task in programming, and there are multiple ways to approach this problem. In this article, we will compare two algorithms implemented in JavaScript that find the intersection between two arrays. We will evaluate their space and time complexity to understand their efficiency and performance.

Algorithm 1:

const arr1 = [ 1, 2, 3, 4, 5, 6, ];
const arr2 = [ 8, 9, 4, 6, 7, 1, ];

const intercept = arr1.filter(x => arr2.includes(x));

Algorithm 2:

const arr1 = [ 1, 2, 3, 4, 5, 6, ];
const arr2 = [ 8, 9, 4, 6, 7, 1, ];

const computeIntercept = (array1, array2) => {
    const theSet = new Set(array1);
    return array2.filter(x => theSet.has(x));
};

const intercept = computeIntercept(arr2, arr1);

Space Complexity

The space complexity of an algorithm refers to the amount of memory required by the algorithm to solve a problem. In both algorithms, we are using additional data structures to store intermediate results.

Algorithm 1 uses the filter function to create a new array containing the intersecting elements. This algorithm does not require any additional space apart from the resulting array, which will have a maximum size equal to the smaller of the two input arrays. Therefore, the space complexity of Algorithm 1 is O(min(n, m)), where n and m are the sizes of the input arrays.

Algorithm 2 creates a Set from the first array, which requires additional space to store the unique elements. The space complexity of creating a Set is O(n), where n is the size of the first array. The resulting array obtained from filtering the second array will also have a maximum size equal to the smaller of the two input arrays. Hence, the overall space complexity of Algorithm 2 is O(n + min(n, m)).

Time Complexity

The time complexity of an algorithm refers to the amount of time taken by the algorithm to solve a problem. It measures the number of operations performed as the input size increases.

Algorithm 1 utilizes the includes function inside the filter function. The includes function has a time complexity of O(m), where m is the size of the second array. The filter function iterates over the elements of the first array, resulting in a time complexity of O(n). Therefore, the overall time complexity of Algorithm 1 is O(n * m).

Algorithm 2 creates a Set from the first array, which takes O(n) time, where n is the size of the first array. Filtering the second array has a time complexity of O(m), where m is the size of the second array. Thus, the time complexity of Algorithm 2 is O(n + m).

Comparison

Comparing the space and time complexities of the two algorithms, we can make the following observations:

• Algorithm 1 has a better space complexity than Algorithm 2.
• Algorithm 2 has a better time complexity than Algorithm 1.

Conclusion

Algorithm 1 is more space-efficient, but Algorithm 2 is more time-efficient when finding the intersection between two arrays. The choice between the algorithms depends on the specific requirements of the application, such as the available memory and the size of the input arrays.

If you have an alternative algorithm or a more efficient solution, please feel free to share it. 🙂