The way I did it was to loop 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?
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.
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:
with n running from 1 to
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
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.
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. :)
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)
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.