Finding common elements in two arrays

Question

I just had this question in an interview. I had to write some code to find all the common elements in two arrays. This is the code I wrote. I could only think of a 2-loop solution, but something tells me there must be a way to accomplish this with only 1 loop. Any ideas?

public List<Integer> findCommonElements(int[] arr1, int[] arr2) { List<Integer> commonElements = new ArrayList<>(); for (int i = 0; i < arr1.length; i++) { for (int j = 0; j < arr2.length; j++) { if (arr1[i] == arr2[j]) { commonElements.add(arr1[i]); break; } } } return commonElements; } 

Answer 1

You use a hashset, this means you have 2 loops, but not nested. You have a boolean hashset in this case where all values start at false of size k where k (this is typically what is used in Big O'notation) is the the number of possible integer values. You loop over your first array and for each value you go hashset[firstArray[i]] = true; once you have done this you loop over your second array, going if(hashset[secondArray[i]]) commonElements.add(secondArray[i]);.

This is O(2n) which then becomes simply O(n) due to getting rid of the constants, your solution was O(n^2). Although it should be noted the storage required for using a hashset is considerably more.

Answer 2

There is a reason why "Data Structures and Algorithms" has the data structures part added in, especially first. The reason why is data structures should be the first thing you think about even before writing any kind of algorithm.

Lets take the specification of the code that you are given:

Write some code to find all the common elements in two arrays.

Now first thing is first this isn't specific enough, what do you mean by "common elements", does this include repeating elements so for example [1,1,2] and [1,1,3] would that be [1,1] or just [1]? For this I'm going to assume you mean elements non repeating.

Now after we have established the specification which is

Given two arrays of numbers find the common unique elements.

I'd say these arrays are sounding a hell of a lot like a set data structure, and this set data structure, because we want to find the intersection between these two sets. In java this would be:

public static void main(String[] args) { List<Integer> alist = Arrays.asList(new Integer[] {1,1,2}); List<Integer> blist = Arrays.asList(new Integer[] {1,1,3}); HashSet<Integer> aset = new HashSet<>(alist); aset.retainAll(blist); System.out.println(aset); } 

It's very important to consider two things when someone gives you a spec, first think through is it clear enough, and secondly, after you have got an idea of what they want you want to strongly consider the data structure as these are structures that have been tried and tested to be efficient at specific tasks.

In the program above, let A be the size of alist and B be the size of blist the time complexity is O(A + B) as it's O(1) to add an element to a hashset which we do for each element in A, then we loop though all elements in B because of the retainAll function needs to do a contains operation on each element, and that is O(1) for a HashSet. This is much more efficient than O(AB) ~ or O(n^2).

edit:

Thanks to nullbyte for pointing out that its more efficient to make one hashset and do ratainAll for just that single set. The code above has been adjusted.

Answer 3

So, the point of this solution is to put the first array into a hash set, and then traverse the second array checking if an element from the second array is present in the set.

This solution requires O(n) time and O(n) space if the arrays have the same length.

 public static List<Integer> findCommon(int[] a, int[] b) { final Set<Integer> set = new HashSet<>(Arrays.stream(a).boxed().collect(Collectors.toList())); final List<Integer> result = new LinkedList<>(); for (int element : b) { if (set.contains(element)) { result.add(element); } } return result; } 

Or a bit more concise solution:

 public static List<Integer> findCommon(int[] a, int[] b) { final Set<Integer> set = new HashSet<>(Arrays.stream(a).boxed().collect(Collectors.toList())); set.retainAll(Arrays.stream(b).boxed().collect(Collectors.toList())); return new ArrayList<>(set); }