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...

Urus

Smells like homework to me. What have you got so far? – Rashad

What is the output you're trying to produce? – Sorrows

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!   
    }
}

Reptilian

They take constant time. For large values of n, lookup costs would be negligible. You propose it is O(n+nk), where k is some small cost? Either way, this solution will amortize to O(n). – Reptilian

Answer 2

Yes, you need two loops, and yes, nested.

pseudocode it will look like:

for each in A do
    for each in B do
       if (current item of A equals to current item of B)
           say yes!
    done
done

Now everything you need is to translate it to Java. Since it sounds like a homework or some exercise you should do it by yourself.

Also, think about what output you need. If you just need a true/false whether a and b have some common values, then you can exit the loops as soon as you find the first match. If instead you need to count the number of common elements between the arrays, you'll need to throw a counter into that set of nested loops. I'll leave it up to you to figure out that portion.

Mydriasis

Answer 3

You just need two nested for loops

for(int i = 0; i < a.length; i++)
{
    for(int j = 0; j < b.length; j++)
    {
        if(a[i] == b[j])
        {
            //value is in both arrays
        }
    }
}

What this does is go to the first value of a and compare to each value in b, then go to the next value of a and repeat.

Sturtevant

What each person gets out of StackOverflow, and which questions they choose to answer, is up to them. You're certainly free to spend your votes as you see fit (that's what votes are for), but the answer isn't technically wrong. – Boswall

Thank you! This is exactly what I had, except when I comparing values in the if() statement I was doing [i] for both of the numbers instead of [i] for one and the other counter for the other. – Urus

Beginer: if someone asks for help, I'm happy to give it. Unless someone says "this is for homework" then frankly I'm not part of any education board, I neither know nor care why they want to know and it's not my place to ask. Surely, however, the essential point is that the asker now knows how to perform the task - education complete, and at no cost to the education system. – Sturtevant

Answer 4

//O(n log(n)), Linear Space Complexity  

void findDuplicates(int[] x, int[] y){
    Arrays.sort(x);
    Arrays.sort(y);
    int i = 0,j = 0;
    while (i < x.length && j < y.length) {
        if(x[i] == y[j]){
            System.out.println(x[i]);
            i++;
            j++;
        }else if (x[i] < y[j])
            i++;
        else
            j++;
    }
}

Intendant

Answer 5

Since you haven't got this tagged as homework, I'll give you the benefit of the doubt. As you said you'll need two loops; loop foreach int in a[] and foreach int in b[]. Then just compare the two values at each iteration, which gives you the simple code of:

for (int x : a) {
   for (int y : b) {
      if (x == y) {
         System.out.println("a[] and b[] both contain " + x);
      }
   }
}

Innsbruck

Most likely OP hasn't had the possibility to add this tag yet. – Mydriasis

@Beginner: Just looking at your code, it's barely any different to mine, be it pseudo-code or not. Not everything is homework. – Innsbruck

Your code can be copypasted. This is the problem. Mine - not. – Mydriasis

Duplicate answers aren't, in and of themselves, bad answers, so long as their technical content is correct. It is my opinion that, if you don't feel that a question deserves an answer, that you should not answer the question and move on, rather than down-vote answers that give correct information. – Boswall

@Beginner Have you ever used actual code from the internet as a learning tool? I have. You are assuming bad intentions without need. – Towns

@Towns Yes, it will be helpful for other people that visit this site later to study the code, but it is by no means helpful for the OP, to whom this answer must serve in the first place. – Mydriasis

@Beginner: How exactly is this unhelpful to the OP? What is it they put in programming books, code samples? The snippet is explained and has only 3 main lines, and demonstrates a foreach loop as opposed to a for loop that uses random access to iterate the arrays. Unless this is tagged as homework it's in no way unhelpful. I don't mind down votes at all, however I don't see anything wrong with the answer. Same goes for the other answers you down voted. – Innsbruck

@Beginner I understand your concern. But lets try and assume good faith on everyone's part. – Towns

Answer 6

Depending on the data (its size, whether every value is unique, etc) and what you're trying to get from it (ie, whether each element of a is in b, or also its index in b), it may be beneficial to do a bit of overhead work before you do the meat of it. For instance, if you sort both arrays (which you'll only need to do once), you can start the inner loop where you stopped it last (since you know that you're looking for a number >= the one you looked for last, so it's got to be at this index or greater), and you can also stop the inner loop sooner (since you know that if you're looking for X and you haven't found it before seeing a value > X, then X isn't there). Another approach would be to load both values into a Set, which you can now probe efficiently.

Blackdamp

Answer 7

import java.util.*;
class Test {
    public static void main(String[] args) {
        int[] a = {1,2,3,4,5};
        int[] b = {4,5,6,7,8};
        findDuplicate(a,b);
    }
    
    static void findDuplicate(int[] a, int[] b){
        HashMap<Integer, Integer> hash = new HashMap<>();
        for(int i : a){
            hash.put(i,1);
        }
        for(int j : b){
            if(hash.containsKey(j)){
                System.out.println(j);
            }
        }
    }
}

Aldose

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Canine