Is there a way to find common elements in multiple lists?

Question

I have a list of integer arrays. I need to find the common elements between those. What I can think of is an extension of what is listed in Common elements in two lists

Example would be 
[1,3,5],
[1,6,7,9,3],
[1,3,10,11]

should result in [1,3]

There are no duplicates in the arrays as well.

Is there a straight forward way to do this?

Allergic

Are you trying to intersect the values of a list of int arrays? What do you mean by "straight forward way"? – Buoyancy

"Common" meaning that they appear in every list, or in more than one list? – Fourpence

I meant by "straight forward way" a method in some kind of library like apache commons, colt, guava etc. – Allergic

You can iterate through all elements in each array and populate Map. Where key is your integer value and value is counter of how many times this element is met. – Reld

Answer 1

You can transform the lists to sets, and then use Set.retainAll method for intersection between the different sets. Once you intersect all sets, you are left with the common elements, and you can transform the resulting set back to a list.

Godard

It still complies with your requirements - you can transform each list to a Set (a HashSet can take a Collection as a constructor argument), do the intersection, and transform the intersected set back to list. This solution is O(n), whereas sorting each list and comparing is O(n*log(n)), and comparing each item with other items is O(n^2). – Godard

@AmirKost converting to a Set (that's not a LinkedHashSet) will lose the ordering of the list. – Warrantable

Answer 2

You can use Set's intersection method offered by Guava, Here is a little example :

public <T> Set<T> intersection(List<T>... list) {
    Set<T> result = Sets.newHashSet(list[0]);
    for (List<T> numbers : list) {
        result = Sets.intersection(result, Sets.newHashSet(numbers));
    }
    return result;
}

Hope that could help you

Mcanally

this helped me a lot thanks for the solution. I wonder why this is not a acceptable, anyways thanks – Achievement

Answer 3

We can use retainAll method of Collections. I initialised my commons arraylist with the first array list and called this for each remaining arraylists.

List<List<Integer>> lists = new ArrayList<List<Integer>>();
lists.add(new ArrayList<Integer>(Arrays.asList(1, 3, 5)));
lists.add(new ArrayList<Integer>(Arrays.asList(1, 6, 7, 9, 3)));
lists.add(new ArrayList<Integer>(Arrays.asList(1, 3, 10, 11)));

List<Integer> commons = new ArrayList<Integer>();
commons.addAll(lists.get(1));
for (ListIterator<List<Integer>> iter = lists.listIterator(1); iter.hasNext(); ) {
    commons.retainAll(iter.next());
}

System.out.println(commons);
System.out.println(lists.get(1));

Phial

Why are you starting from index 1? Aren't we supposed to start from 0? – Capello

Answer 4

with Java 8

ArrayList retain = list1.stream()
                     .filter(list2::contains).filter(list3::contains).collect(toList())

Suzerainty

I think this should be accepted, although I think the correct form is: ArrayList retain = list1.stream().filter(list2::contains).collect(Collectors.toCollection(ArrayList::new)); – Wyn

this only works with 3 lists. I think the question is about arbitrary number of lists. – Manufacture

@Manufacture Correct me if I'm wrong but, why can't you just add more .filter(list3::contains) to the statement? – Granitite

@devdudejohn you can add more at compile time if you know the number of lists at the time of writing code, no problem there. But if the number of lists is unknown at compile-time then you need to write code that could handle any number of lists. – Manufacture

Answer 5

If you are looking for a function that returns elements that exist in all lists,

then the straight forward & simple way is building a statistic { < member, occurences > }

The condition here is no duplicates among the same list,

private Set<Integer> getCommonElements(ArrayList<Integer[]> idList)
{

    MapList<Integer,Short> stat = new MapList<Integer,Short>();

    // Here we count how many times each value occur
    for (int i = 0; i < idList.size(); i++)
    {
        for (int j = 0; j < idList.get(i).size; j++)
        {
            if (stat.containsKey(idList.get(i)[j]))
            {
                stat.set(idList.get(i)[j], stat.get(idList.get(i)[j])+1);
            }
            else
            {
                stat.add(idList.get(i)[j], 1);
            }
        }
    }

    // Here we only keep value that occured in all lists
    for (int i = 0; i < stat.size(); i++)
    {
        if (stat.get(i) < idList.size())
        {
            stat.remove(i);
            i--;
        }
    }

    return stat.keySet();
}

Soften

Unlike in C#, in Java you cannot specify a primitive as a generic type. So instead of Set<int>, use Set<Integer>. – Vale

Answer 6

public class ArrayListImpl{
  public static void main(String s[]){
    ArrayList<Integer> al1=new ArrayList<Integer>();
     al1.add(21);al1.add(23);al1.add(25);al1.add(26);
    ArrayList<Integer> al2=new ArrayList<Integer>();
     al2.add(15);al2.add(16);al2.add(23);al2.add(25);
     ArrayList Al3=new ArrayList<Integer>();
     al3.addAll(al1);
      System.out.println("Al3 Elements :"+al3);
     al3.retainAll(al2); //Keeps common elements of (al1 & al2) & removes remaining elements
       System.out.println("Common Elements Between Two Array List:"+al3);  
}
}

Unmindful

Answer 7

If you are using JAVA 8 streams. Then using stream reduce operation we can achieve the same.

Considering your example: Let's say a = [1,3,5], b = [1,6,7,9,3] and c = [1,3,10,11]

List<Integer> commonElements = Stream.of(a,b,c)
     .reduce((s1,s2) -> {
          s1.retainAll(s2); 
          return s1;
      }).orElse(Collections.emptyList());

Keep in mind that after running this operation a will get modified with common values as well. So you will lose the actual value of a.

So elements of a and the result elements of commonElements will be essentially the same after running this operation.

Sesqui

Answer 8

Giving some another alternative code using retainAll capability of Set

public List getCommonItems(List... lists) {
    Set<Integer> result = new HashSet<>(lists[0]);

    for (List list : lists) {
        result.retainAll(new HashSet<>(list));
    }

    return new ArrayList<>(result);;
}

Usage:

List list1 = [1, 2, 3]
List list2 = [3, 2, 1]
List list3 = [2, 5, 1]

List commonItems = getCommonItems(list1, list2, list3)
System.out.println("Common items: " + result);

Result:

commonItems: [1, 2]

Certifiable

Answer 9

public class commonvalue {

  
   Public static void MyMethod(){
        
       Set<integer> S1 = new set<integer>{1,3,5};
        Set<integer> S2 = new set<integer>{1,6,7,9,3};
        Set<integer> S3 = new set<integer>{1,3,10,11};
           
            s2.retainall(s1);
            s3.retainall(s2);
       
       system.debug(s3);
}
}

Ceratodus

Please explain how this code works and answers the question. – Handsome

Code dumps do not make for good answers. You should explain how and why this solves their problem. I recommend reading, "How do I write a good answer?". This can help future users learn and eventually apply that knowledge to their own code. You are also likely to have positive feedback/upvotes from users, when the code is explained. – Angele