# How to check for array intersection?

Attention Topic was automatically imported from the old Question2Answer platform.

I have two arrays, each containing a few thousand `Vector2s`.

I want to find out if they intersect, but don’t care about the intersection itself.

Currently, I do it this way.

``````func intersects(array1, array2):
var intersect = false
for item in array1:
if item in array2:
intersect = true
break
return intersect
``````

I do not feel like this is the most optimal way to do it. In fact, I am experiencing performance issues doing it this way.

What is the fastest way to check arrays for intersection?

I am open to using a different data type, like dictionaries. I am even open to using a different type of object for my elements, for example, using subarrays rather than `Vector2s`.

A way you could do it is like this:

``````func intersect(array1, array2):
var intersection = false
for item in array1:
if array2.has(item):
intersection = true
break
return intersection
``````

A little different from your code. The `has()` method may speed things up.

You could even get more sophisticated, and return the elements which do intersect:

``````func intersect(arra1, array2):
var intersection = []
for item in array1:
if array2.has(item):
intersection.append(item)
return intersection
``````

Hope this helps.

This solution still has to check every element of the second array for every element in the first array, which means the performance will be similar

Keeyan | 2021-08-01 16:12

Your solution is n^2 meaning that for each element of the first array it has to go through each element of the second array. As the array sizes grow the search times grow exponentially.

By using dictionaries, you can make this n log n which is much faster:

``````func intersects(arr1, arr2):
var arr2_dict = {}
for v in arr2:
arr2_dict[v] = true

for v in arr1:
if arr2_dict.get(v, false):
return true
return false
``````

Or if you want to return the actual elements, change it like this:

``````func intersect_arrays(arr1, arr2):
var arr2_dict = {}
for v in arr2:
arr2_dict[v] = true

var in_both_arrays = []
for v in arr1:
if arr2_dict.get(v, false):
in_both_arrays.append(v)
return in_both_arrays
``````

The reason this is faster, is because the lookup speed for dictionaries is much faster than the lookup speed for an element in an array (since that has to go over every single element). So this code should be able to handle much larger inputs.