How to check for array intersection?

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By Diet Estus

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.

:bust_in_silhouette: Reply From: Ertain

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

:bust_in_silhouette: Reply From: Keeyan

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.