How do you find the first common element in two arrays

Question

How do you find the first common element in two arrays?

My attempt:

I looped through each at the same time and add the current value to a separate set for each of the lists. Also, check if the current element is already in the other list's set.

I have no idea if this works though and if so, why? I know it finds a common element but does it find the first common element? I can't think of counter examples but I'm having trouble convincing myself it's definitely correct. Also, even if it is correct, is there a better way of finding the first common element?

Answer 1

Sorting the arrays will not work. By changing the order you will not be able to determine which element matches first.

The intersect solution will also not work. To use it you'd have to copy both arrays to a set class, which by definition does not preserve order.

Your answer is correct. I would consider using hashsets to reduce search time.

Answer 2

If the problem is to find the first element of list L1 which is also contained in L2, run through the elements of L1 one-by-one and check if the current element is in L2. The second test ("is element in L2") can be either done by a simple loop over all elements in L2. Or you put all elements of L2 into a hashset first, which can speed-up the process fairly.

Now it should be obvious that you can switch roles of L1 and L2 when you are looking for the first element in L2 which is also part of L1. And if you are looking for a common element from one of the lists which has the lowest positional index either in L1 or L2, run both steps described so far, and if you find two different elements, choose the one with the lowest index in either L1 or L2.

This approach has one disadvantage: if L1 and L2 are huge, and you have some non-common elements at the beginning of each lists, you have to read either the full list L1, L2 or both, even when there are some common elements among the first elements of L1 and L2. So the idea of your solution above is to use the following subsets:

K1(n)="the first n elements of L1" (or L1 if n>length(L1))
K2(n)="the first n elements of L2" (or L2 if n>length(L2))

with n running from 1 to max(length(L1),length(L2) and check if K1 and K2 have a common element, for each n. The smallest n where K1(n) and K2(n) have a common elements shows you that either the n-th element of L1 or the n-th element of L2 is the element you are looking for.

It should be obvious that when K1(n) and K2(n) are disjoint, and you are going from n to n+1, you only have to check if the new introduced n+1st elements from L1 and L2 are in K2(n+1) or K1(n+1). The use of a fast hashset data structure for K1 and K2 which is incrementally extended keeps this process fast even for bigger n. And if you found a common element for a certain n, you can stop the process immediately. That is what you described in your post.

This approach will work fairly fast even when L1 and L2 have, for example, more than a million elements, but the first common element in both lists is among the "top ten" in both lists. It won't save you much when L1 and L2 do not have any element in common, but that is also true for any other approach.

Answer 3

Say first array A has length n and second array B has length m.

Whichever is smaller in length, loop through it and put it's elements in a LinkedHashSet (it doesn't matter if it's sorted or unsorted). Then loop through the second array and query the set for that element. Wherever you find your first common element, break.

Space complexity: O(m) assuming m is the smaller or equal to n Time complexity: O(n)

//Java-like pseudo code
class FirstCommonFinder {
    Element[] firstInput = {….};
    Element[] secondInput = {….};
    Set smallerInput = new LinkedHashSet<>();
    boolean found = false;
    //assuming firstInput is smaller than secondInput
    for (Element input: firstInput) {
        smallerInput.add(input);
    }


    //loop through and break upon first common occurrence 
    for (int i = 0; i < secondInput.length; i++) {
        if (smallerInput.contains(secondInput[i])) {
        found = true;
        break;
    }
}


}

In case if you want to keep track of the indices in both input arrays (for commonly occurring elements), use a LinkedHashMap and put the array index as value to the element key.

Answer 4

Personally, I think the set solution works, but if you want to optimize the solution with O(1) memory usage, you could reverse the two lists, which will be O(n), then start at the beginning, use two pointers, find the first difference, and the node just before the difference is the answer. And if it doesn't allow you to change the original list, you can reverse it back. Which is still O(n).

Answer 5

This is a Set Intersect. In .NET, I think the LINQ Intersect() method could be used. Java and others should have their own.

Note that you'd need to be careful about whether the implementation preserves array index order. E.g. in .NET, calling First() might not return the first by array index order.

For the low-level implementation of a Set Intersect, I would need to consult an Algorithms book. :)