Introduction:

In the world of programming, determining the common elements between two arrays is a frequent requirement. This process, known as finding the intersection of arrays, finds utility across various domains. In this blog, we will delve into different approaches to discovering the intersection of two arrays using C#. We will explore multiple methods, present practical code examples, explain their inner workings, and compare their performance. By the end of this guide, you will possess a solid understanding of how to efficiently find the intersection of arrays in C#.

Method 1: Naive Approach

The naive approach to finding the intersection of two arrays involves iterating through each element of one array and checking for its existence in the other array. This can be accomplished using nested loops. Here's an example implementation:

using System;
using System.Collections.Generic;

class Program
{
    static int[] FindIntersection(int[] array1, int[] array2)
    {
        List<int> intersection = new List<int>();

        foreach (int num1 in array1)
        {
            foreach (int num2 in array2)
            {
                if (num1 == num2 && !intersection.Contains(num1))
                {
                    intersection.Add(num1);
                    break;
                }
            }
        }

        return intersection.ToArray();
    }

    static void Main()
    {
        int[] array1 = { 1, 2, 3, 4, 5 };
        int[] array2 = { 4, 5, 6, 7, 8 };

        int[] intersection = FindIntersection(array1, array2);

        Console.WriteLine("Intersection of the arrays:");
        foreach (int num in intersection)
        {
            Console.Write(num + " ");
        }
    }
}

Output:

Intersection of the arrays:
4 5

In the above code, we define a FindIntersection method that takes two integer arrays as input and returns an array containing their intersection. We utilize a List<int> called intersection to store the common elements found.

We then use nested loops to compare each element of array1 with every element of array2. If a match is found, and the element is not already present in the intersection list, we add it to the list and break out of the inner loop. Finally, we convert the intersection list to an array and return the result.

Method 2: HashSet Approach

A more efficient approach to finding the intersection of arrays involves leveraging the HashSet data structure. HashSet provides constant time complexity for element lookups, significantly enhancing the performance of our intersection algorithm. Here's an example implementation:

using System;
using System.Collections.Generic;

class Program
{
    static int[] FindIntersection(int[] array1, int[] array2)
    {
        HashSet<int> set1 = new HashSet<int>(array1);
        HashSet<int> intersection = new HashSet<int>();

        foreach (int num2 in array2)
        {
            if (set1.Contains(num2))
            {
                intersection.Add(num2);
            }
        }

        return intersection.ToArray();
    }

    static void Main()
    {
        int[] array1 = { 1, 2, 3, 4, 5 };
        int[] array2 = { 4, 5, 6, 7, 8 };

        int[] intersection = FindIntersection(array1, array2);

        Console.WriteLine("Intersection of the arrays:");
        foreach (int num in intersection)
        {
            Console.Write(num + " ");
        }
    }
}

Output:

Intersection of the arrays:
4 5

In this approach, we introduce two HashSet objects: set1 and intersection. We create set1 by initializing it with the elements of array1 using the HashSet constructor. This allows us to perform fast lookups.

Next, we iterate over each element, num2, in array2. We check if set1 contains num2 using the Contains method. If num2 exists in set1, we add it to the intersection HashSet.

Finally, we convert the intersection HashSet to an array using the ToArray method and return the result.

Conclusion:

Finding the intersection of two arrays is a common programming task, and in this blog, we explored two different approaches to accomplish it in C#. The naive approach relies on nested loops to compare elements, while the HashSet approach takes advantage of the HashSet data structure for efficient lookups. By leveraging the HashSet's constant time complexity, we significantly enhance the performance of our intersection algorithm. This becomes particularly valuable when dealing with larger arrays. It is essential to consider the size and characteristics of your input when choosing the appropriate method.