Finding duplicate values between two arrays

Question

Let's say I have the following two arrays:

int[] a = [1,2,3,4,5];
int[] b = [8,1,3,9,4];

I would like to take the first value of array a - 1 - and see if it is contained in array b. So, I would get that the '1' from a is in b even if it is not in the same position. Once I have gone through the comparison for the first element in a, I move on to the next number in array a and continue the process until I have completely gone through the first array.

I know I need to do some looping (possibly nested?) but I can't quite figure out how I stick with just the first number in array a while looping through all the numbers in array b.

This seems to be fairly simple I just can't get my head around it...

Answer 1

These solutions all take O(n^2) time. You should leverage a hashmap/hashset for a substantially faster O(n) solution:

void findDupes(int[] a, int[] b) {
    HashSet<Integer> map = new HashSet<Integer>();
    for (int i : a)
        map.add(i);
    for (int i : b) {
        if (map.contains(i))
            // found duplicate!   
    }
}