CODEWITHSUNDEEP
java
user3272408
user3272408

Reputation: 47

Find duplicate in two arrays

My interview question was to find duplicates in two arrays.

array1 = [1,2,4,6,9,50,34];
array2 = [1,5,4,50,24,78,34];

I know the code for this is to use two for loops:

for(int i=0; i<arr1.length; i++){
    for(int j=0; j<arr2.length; j++) {
        if(arr1[i]==arr2[j]) {
            System.out.println(arr1[i]);
        }
    }
}

The interviewer asked for a better method with much iteration. Can I get any suggestions regarding this?

Upvotes: 2

Views: 3766

Answers (7)

Suvam Roy
Suvam Roy

Reputation: 953

import java.util.*;
public class Duplicate {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    int array1[]= {1,2,4,6,9,50,34};
    int array2[]= {1,5,4,50,24,78,34};

    HashSet<Integer> hashValue=new HashSet<>();
    for(int i=0;i<array1.length;i++) {
        hashValue.add(array1[i]);
    }

    for(int j=0;j<array2.length;j++) {
        if(hashValue.contains(array2[j])) {
            System.out.println("the duplicate value is  "+array2[j]);
        }
    }


}

}

Upvotes: 1

Ubica
Ubica

Reputation: 1051

I did the tests again... set and maps are indeed a lot faster then the loops

private static int size = 100000;

public static void main(String[] args) {
    int[] array1 = new int[size];
    int[] array2 = new int[size];

    for (int i = 0; i < size; i++) {
        array1[i] = i;
        array2[i] = i + i;
    }

    System.out.println("starting set");
    startTimer();
    compareAgainstSet(array1, array2);
    long set = stopTimer();
    System.out.println("against set: " + set + "ms\n");

    System.out.println("starting map");
    startTimer();
    compareAgainstMap(array1, array2);
    long map = stopTimer();
    System.out.println("against hashmap: " + map + "ms\n");

    System.out.println("starting loops with break");
    startTimer();
    twoLoopsWithBreak(array1, array2);
    long loopsBreak = stopTimer();
    System.out.println("2 loops with break: " + loopsBreak + "ms\n");

    System.out.println("starting loops without break");
    startTimer();
    twoLoopsWithoutBreak(array1, array2);
    long loops = stopTimer();
    System.out.println("2 loops without break: " + loops + "ms\n");

}

private static void twoLoopsWithoutBreak(int[] arr1, int[] arr2) {
    ArrayList<Integer> doubles = new ArrayList<>();
    for (int i : arr1) {
        for (int j : arr2) {
            if (i == j) {
                doubles.add(i);
            }
        }
    }
}

private static void twoLoopsWithBreak(int[] arr1, int[] arr2) {
    ArrayList<Integer> doubles = new ArrayList<>();
    for (int i : arr1) {
        for (int j : arr2) {
            if (i == j) {
                doubles.add(i);
                break;
            }
        }
    }
}

private static void compareAgainstSet(int[] arr1, int[] arr2) {
    ArrayList<Integer> doubles = new ArrayList<>();
    Set<Integer> set1 = new HashSet<Integer>();
    for (int i : arr1) {
        set1.add(i);
    }
    for (int i : arr2) {
        if (set1.contains(i)) {
            doubles.add(i);
        }
    }
}

private static void compareAgainstMap(int[] arr1, int[] arr2) {
    ArrayList<Integer> doubles = new ArrayList<>();
    HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
    for (int i : arr1) {
        hashmap.put(i, 0);
    }
    for (int i : arr2) {
        if (hashmap.containsKey(i)) {
            doubles.add(i);
        }
    }
}

private static long startTime;

private static void startTimer() {
    startTime = System.currentTimeMillis();
}

private static long stopTimer() {
    return System.currentTimeMillis() - startTime;
}

Upvotes: 1

Kaushik Gopalakrishnan
Kaushik Gopalakrishnan

Reputation: 1

If you don't want two for loops. Then you can use hashtable. Iterate the first array and insert to the hastable. When iterating the 2nd array to the hash table, check for the key, if present then it is duplicated else no.

With this approach, the time complexity will be getting reduced to O(kn) where k is a constant which is the number of arrays you have, but auxiliary space complexity will be increased.

Upvotes: 0

outdev
outdev

Reputation: 5492

As dasblinkenlight said before me:

public static void main(String[] args) {
        int[] arr1 = new int[] { 10, 3, 4, 20};
        int[] arr2 = new int[] { 10, 20, 30 };

        //convert arr1 to java.util.Set
        Set<Integer> set1 = new HashSet<Integer>();
        for (int i : arr1) {
            set1.add(i);
        }
        // print the duplicates
        for (int i : arr2) {
            if (set1.contains(i)) {
                System.out.println(i); // print 10 20
            }
        }
    }

Upvotes: 1

MiChAeLoKGB
MiChAeLoKGB

Reputation: 805

Why not just using array_intersect?

$a = array(1, 2, 5, 10, 15, 16);
$b = array(1, 4, 5, 6, 10, 13, 15, 19);

print_r(array_intersect($a, $b));

Whoops, I tought it was PHP, not JS...

Then: How do I get the intersection between two arrays as a new array?

Upvotes: 0

Eran
Eran

Reputation: 393771

Your solution required O(n^2) time (assuming n is the length of the larger of the two arrays).

A better solution would be to sort the two arrays - O(n log(n))
and then find the duplicates in a single iteration over both sorted arrays - O(n).
The total running time would be O(n log(n)).

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726479

The code with two loops is O(m*n), where m and n are array sizes. You can do better than that if you put the content of one array into a hash-based container, say, HashSet<T>, and then go through the items of the second array, checking if they are in the hash set or not. This has the complexity of O(m+n), i.e. linear in the total number of elements in both arrays.

Upvotes: 4

Related Questions