find common items across multiple lists in C#

I have two generic list :

List<string> TestList1 = new List<string>();
List<string> TestList2 = new List<string>();
TestList1.Add("1");
TestList1.Add("2");
TestList1.Add("3");
TestList2.Add("3");
TestList2.Add("4");
TestList2.Add("5");

What is the fastest way to find common items across these lists?

Assuming you use a version of .Net that has LINQ, you can use the Intersect extension method:

var CommonList = TestList1.Intersect(TestList2)

If you have lists of objects and want to get the common objects for some property then use;

var commons = TestList1.Select(s1 => s1.SomeProperty).ToList().Intersect(TestList2.Select(s2 => s2.SomeProperty).ToList()).ToList();

Note: SomeProperty refers to some criteria you want to implement.

Assuming you have LINQ available. I don't know if it's the fastest, but a clean way would be something like:

var distinctStrings = TestList1.Union(TestList2).Distinct();

var distinctStrings = TestList1.Union(TestList2);

Update: well never mind my answer, I've just learnt about Intersect as well!

According to an update in the comments, Unions apply a distinct, which makes sense now that I think about it.

You can do this by counting occurrences of all items in all lists - those items whose occurrence count is equal to the number of lists, are common to all lists:

    static List<T> FindCommon<T>(IEnumerable<List<T>> lists)
    {
        Dictionary<T, int> map = new Dictionary<T, int>();
        int listCount = 0; // number of lists

        foreach (IEnumerable<T> list in lists)
        {
            listCount++;
            foreach (T item in list)
            {
                // Item encountered, increment count
                int currCount;
                if (!map.TryGetValue(item, out currCount))
                    currCount = 0;

                currCount++;
                map[item] = currCount;
            }
        }

        List<T> result= new List<T>();
        foreach (KeyValuePair<T,int> kvp in map)
        {
            // Items whose occurrence count is equal to the number of lists are common to all the lists
            if (kvp.Value == listCount)
                result.Add(kvp.Key);
        }

        return result;
    }

Sort both arrays and start from the top of both and compare if they are equal.

Using a hash is even faster: Put the first array in a hash, then compare every item of the second array if it is already in the hash.

I don't know those Intersect and Union are implemented. Try to find out their running time if you care about the performance. Of course they are better suited if you need clean code.

Use the Intersect method:

IEnumerable<string> result = TestList1.Intersect(TestList2);

Using HashSet for fast lookup. Here is the solution:

using System;
using System.Linq;
using System.Collections.Generic;

public class Program
{
    public static void Main()
    {
        List<int> list1 = new List<int> {1, 2, 3, 4, 5, 6 };
        List<int> list2 = new List<int> {1, 2, 3 };
        List<int> list3 = new List<int> {1, 2 };

        var lists = new IEnumerable<int>[] {list1, list2, list3 };

        var commons = GetCommonItems(lists);
        Console.WriteLine("Common integers:");
        foreach (var c in commons)
            Console.WriteLine(c);

    }

    static IEnumerable<T> GetCommonItems<T>(IEnumerable<T>[] lists)
    {
        HashSet<T> hs = new HashSet<T>(lists.First());
        for (int i = 1; i < lists.Length; i++)
            hs.IntersectWith(lists[i]);
        return hs;
    }
}

Following the lead of @logicnp on counting the number of lists containing each member, once you have your list of lists, it's pretty much one line of code:

List<int> l1, l2, l3, cmn;
List<List<int>> all;

l1 = new List<int>() { 1, 2, 3, 4, 5 };
l2 = new List<int>() { 1, 2, 3, 4 };
l3 = new List<int>() { 1, 2, 3 };
all = new List<List<int>>() { l1, l2, l3 };

cmn = all.SelectMany(x => x).Distinct()
      .Where(x => all .Select(y => (y.Contains(x) ? 1 : 0))
      .Sum() == all.Count).ToList();

Or, if you prefer:

public static List<T> FindCommon<T>(IEnumerable<List<T>> Lists)
{
  return Lists.SelectMany(x => x).Distinct()
      .Where(x => Lists.Select(y => (y.Contains(x) ? 1 : 0))
      .Sum() == Lists.Count()).ToList();
}