How to find intersection of two arrays (Optimal solution)

Question

I am writting algorithm for intersection of two arrays A and B , I want an optimized solution in terms of space complexity and time complexity. I have written algorithm and it works fine but i want to know if there is any more optimal solution then this exist or if someone could provide me.

What i do is:

(1) Find the Smallest size array among two.

(2) The new array wil be of size allocated size equal to smaller size array

(3) From smaller size array i go and compare with each element in bigger array if it exists one ,i get it in third array"C" and break it right there (because we need to find intersection, even if it repeats 100 times after we don't care for us only one existence is enough to put in third array). At the same time we also have to check if the element in smaller array which to be compared with all elements in bigger array already exist in third array, Example A=[0,1,1], B[0,1,2,3]. Now we start with A's first element, it is present in array B we save it in C[0], then go to second , now C is [0,1], and in next step we again have 1 to compare, which we have already compared.So for this situation we have to do check if element to be compare already exist in array C then we eliminate check for it.

(4) We store the found element in C (third array) and print it.

My full working code for it is :

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] aar1 = { 0, 1, 1, 7, 2, 6, 3, 9, 11, 2, 2,3,3,3,3,3,1 };
            int[] aar2 = { 0, 1, 2, 3, 4, 5, 6, 11, 11, 1, 1, 1, 1 };
            int[] arr3 = findIntersection(aar1, aar2);
            Console.WriteLine("the array is : " + arr3);
            Console.ReadKey();
        }

        private static int[] findIntersection(int[] aar1, int[] aar2)
        {
            int[] arr3 = { 0 };
            if (aar1.Count() < aar2.Count())
            {
                int counter = 0;
                arr3 = new int[aar1.Count()];
                foreach (int var1 in aar1)
                {
                    if (!checkifInThirdArray(var1, arr3))
                    {
                        foreach (int var2 in aar2)
                        {
                            if (var1 == var2)
                            {
                                arr3[counter++] = var1;
                                break;
                            }
                        }
                    }
                }
            }
            else
            {
                int counter = 0;
                arr3 = new int[aar1.Count()];
                foreach (int var2 in aar2)
                {
                    if (!checkifInThirdArray(var2, arr3))
                    {
                        foreach (int var1 in aar1)
                        {
                            if (var2 == var1)
                            {
                                arr3[counter++] = var2;
                                break;
                            }
                        }
                    }
                }
            }
            return arr3;
        }

        private static bool checkifInThirdArray(int var1, int[] arr3)
        {
            bool flag = false;
            if (arr3 != null)
            {
                foreach (int arr in arr3)
                {
                    if (arr == var1) { flag = true; break; }
                }
            }
            return flag;
        }
    }
}

One space complexity issue i found is (the others i would really appreciate if you let me know with solution if you find any) :

(1) When i allocate the size to third array, i allocate the Min of the two arrays to be compared, In case if the intersection element are too less then we have unnecessarily allocated the extra memory. How to solve this issue ?

Please note that i don't have to use any inbuilt function like intersection() or any other.

Answer 1

It sounds like your solution is an O(n2) one in that, for every single element in one array, you may need to process every single element in the other (in the case where the intersection is the null set). You should be aware that C# actually has facilities for finding the intersection of arrays but, should you wish to implement your own, read on.

You would probably be better of sorting both arrays (in-place if allowed otherwise to a separate collection) then doing a merge-check of the two to construct another. The sort could be O(n log n) and the merge check would be O(n).

If you're wondering what I mean by merge check, it's simply processing both (sorted) arrays side by side.

If the first element in both matches, you have an intersect point and you should store that value and advance both lists until the next value is different.

If they're different, there's no intersect point and you can advance the array with the lowest value until it changes.

---

By way of example, here's some code in Python (the ideal pseudo-code language) that implements such a solution. Array a contains all the multiples of three between 0 and 18 inclusive (in arbitrary order and including duplicates), while array b has all the even numbers in that range (again, with some duplicates and ordered "randomly").

a = [0,3,15,3,9,6,12,15,18,6]
b = [10,0,2,12,4,6,18,8,16,10,12,6,14,16]

# Copy and sort.

a2 = a; a2.sort()
b2 = b; b2.sort()

# Initial pointers and results for merge check.

ap = 0
bp = 0
c = []

# Continue until either array is exhausted.

while ap < len(a2) and bp < len(b2):
    # Check for intersect or which list has lowest value.

    if a2[ap] == b2[bp]:
        # Intersect, save, advance both lists to next number.

        val = a2[ap]
        c.append(val)
        while ap < len(a2) and a2[ap] == val:
            ap += 1
        while bp < len(b2) and b2[bp] == val:
            bp += 1
    elif a2[ap] < b2[bp]:
        # A has smallest, advance it to next number.

        val = a2[ap]
        while ap < len(a2) and a2[ap] == val:
            ap += 1
    else:
        # B has smallest, advance it to next number.

        val = b2[bp]
        while bp < len(b2) and b2[bp] == val:
            bp += 1

print(c)

If you run that, you'll see the intersect list that's formed between the two arrays:

[0, 6, 12, 18]

Answer 2

You can use LINQ Intersect method. It uses hashing and works for linear O(N+M) which is faster than your algorithm:

int[] aar1 = { 0, 1, 1, 7, 2, 6, 3, 9, 11, 2, 2, 3, 3, 3, 3, 3, 1 };
int[] aar2 = { 0, 1, 2, 3, 4, 5, 6, 11, 11, 1, 1, 1, 1 };

int[] result = aar1.Intersect(aar2).ToArray();

It will also solve your unnecessarily allocated items problem, because it will create an array of the exact answer size.

Answer 3

Maybe I am not understanding you right but why don't you use the following;

int[] aar1 = { 0, 1, 1, 7, 2, 6, 3, 9, 11, 2, 2,3,3,3,3,3,1 };
int[] aar2 = { 0, 1, 2, 3, 4, 5, 6, 11, 11, 1, 1, 1, 1 };

aarResult = aar1.Intersect(aar2).ToArray();

This will result in an array with only the space needed and intersects the arrays. You can also initialize the aarResult as follows to get the minimum array size:

int[] aarResult = new int[Math.Min(aar1.Count(), aar2.Count())];