Common elements among multiple lists

Question

I need to find all common elements (if duplicates exist in all lists, they must be listed as many times) among multiple pre-sorted lists. The number of lists will be determined by the user. I'm trying to find an algorithm that has an O(n) effiency.

I have been toying with the below code, but I can't figure out how to make this work if I don't already know how many lists there are:

Integer[] a = {2, 2, 4, 6, 7, 11};
Integer[] b = {2, 2, 3, 5, 7, 14}
int i = 0;
int j = 0;
while(i < a.length && j < b.length) {
   if(a[i] == b[j]) {
      System.out.print(a[i] + " ");
      i++;
      j++;
   } else if(a[i] > b[j]) {
        j++;
   } else {
        i++;
   }
}

desired output: 2 2 7

Answer 1

The following is for List instead of array, because handling a dynamic number of lists is slightly more complicated, but it provides support for all List, Collection, and Iterable types.

It works for any kind of list of Comparable values, e.g. Integer, Long, Double, String, Date, ...

Code can be modified to handle Integer[] or int[], or any other numeric primitive type, as needed, but you'd have to clone the code for each array type.

No validation is done. Lists must be presorted and nulls are not allowed.

@SafeVarargs
@SuppressWarnings("unchecked")
private static <E extends Comparable<E>> List<E> getCommonValues(Iterable<? extends E> ... lists) {
    // For each list: Get iterator and first value
    Iterator<? extends E>[] iter  = new Iterator[lists.length];
    E[] value = (E[])new Comparable[lists.length];
    for (int i = 0; i < lists.length; i++) {
        iter[i] = lists[i].iterator();
        value[i] = (iter[i].hasNext() ? iter[i].next() : null);
    }

    List<E> commonValues = new ArrayList<>();
    while (true) {

        // Find value count, lowest value, and count of lowest value
        int valueCount = 0, lowestCount = 0;
        E lowestValue = null;
        for (int i = 0; i < lists.length; i++)
            if (value[i] != null) {
                valueCount++;
                int cmp = (lowestValue == null ? -1 : value[i].compareTo(lowestValue));
                if (cmp < 0) {
                    lowestCount = 1;
                    lowestValue = value[i];
                } else if (cmp == 0) {
                    lowestCount++;
                }
            }

        // Exit loop if no more values
        if (valueCount == 0)
            break;

        // Save common value if all values were lowest value
        if (lowestCount == lists.length)
            commonValues.add(lowestValue);

        // For each list: Get next value if value was lowest value
        for (int i = 0; i < lists.length; i++)
            if (value[i] != null && value[i].compareTo(lowestValue) == 0)
                value[i] = (iter[i].hasNext() ? iter[i].next() : null);
    }

    return commonValues;
}

Test

List<Integer> common = getCommonValues(Arrays.asList(2, 2, 4, 6, 7, 11),
                                       Arrays.asList(2, 2, 3, 5, 7, 14),
                                       Arrays.asList(2, 2, 2, 3, 3, 4, 5, 6, 7, 11, 14));
System.out.println(common);

Output

[2, 2, 7]