finding common elements in two integer arrays java

Question

The code returns 0 and the common numbers more than once. I want it to return an array with the common numbers once! So how do I return an array with numbers that are common to both arrays. I want to return {2,7,4} - something like this. I keep getting out of bounds exceptions when I try to return an array. Thanks, Barry

public class Test {
    public int findCommonElement(int[] a, int[] b){
        int counter=0;
        int temp= 0;
        int tempCounter = 0;
        for(int i=0; i<a.length; i++){
            temp=a[i];
            tempCounter=0;
            for(int j=0; j<b.length; j++){
                if (temp==b[j]){
                    tempCounter++;  
                }

            }

            if (tempCounter == 1) {
                temp = a[i];

                counter++;

                System.out.println(temp);

            }

        }

        return 0;
    }

    public static void main(String []args){
        int myArray[] = {2,2,7,7,2,1,5,4,5,1,1};
        int myArray2[] = {2,3,4,7,10};


        Test hello = new Test ();
        System.out.println(hello.findCommonElement(myArray, myArray2));

    }
}

Answer 1

Time complexity o(n) i.e. using single for loop to get the common elements in an array.

    int[] arr1 = { 1, 2, 5, 5, 8, 9, 7, 10 };
    int[] arr2 = { 1, 0, 6, 5, 6, 4, 7, 0 };

    System.out.println("Array1 : " + Arrays.toString(arr1));
    System.out.println("Array2 : " + Arrays.toString(arr2));

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

Output:

Array1 : [1, 2, 5, 5, 8, 9, 7, 10]
Array2 : [1, 0, 6, 5, 6, 4, 7, 0]
Common element is : 1
Common element is : 5
Common element is : 7

Answer 2

O(m+n) solution with the usage of Java Provided excellent Collection Data Structures. The key being .retainAll() function used in Hashset, which retains all the common elements:

It is worth mentioning that retainAll() works with any of the Collection class and internally calls contains() on it. Hence, O(m+n) will only be if the collection here is HashSet since it gives 0(1) lookup. If it is a linear one, like List, complexity will be 0(n^2)

public class common {
public static void main(String[] args) {

    Integer[] arr1 = new Integer[]{1,1,3,4,6,6,7,2,2};
    Integer[] arr2 = new Integer[]{1,1,3,2,4,8,9,5,6};
    List<Integer> alist = Arrays.asList(arr1);
    List<Integer> blist = Arrays.asList(arr2);

    HashSet<Integer> aset =  new HashSet<>(alist);
    aset.retainAll(blist);

    System.out.println(aset);
}

Answer 3

The following is a simple O(n) solution that takes into consideration that arrays are sorted. If not, you can sort them. This is an improvement of the solution provided by @talshahar that also covers the last element being common(an edge case).

public List<Integer>  getCommon(int[]array1, int[] array2){
    int p1 = 0;
    int p2 = 0;
    ArrayList<Integer> common = new ArrayList<Integer>();
    while(p1<array1.length || p2<array2.length) {       ​
       ​if (array1[p1] == array2[p2]) {
           ​common.add(array1[p1]);
           ​p1++;p2++;
       ​}
      ​
       ​else if (array1[p1] < array2[p2]) {
           ​p1++;
       ​} else {
           ​p2++;
       ​}
   ​}
    return common;
}

Answer 4

Remove Complexity Using HashSet

Finding common elements in two integer arrays in java

import java.util.*;
public class Complexity
{
    public static void main(String args[])
    {
    int arr1[] = {2,2,7,7,2,1,5,4,5,1,1};
        int arr2[] = {2,3,4,7,10};

        HashSet<Integer> hashset= new HashSet<Integer>();

        for (int i : arr1){
            hashset.add(i);
        }
        for (int i : arr2) 
        {
            if (hashset.contains(i))
        {
            // found duplicate!   
                System.out.println("Common Elements --> " +i );
        }
       }
    }
}

Answer 5

int x[] = {5, 3, 7, 2, 8}; int y[] = {6, 3, 8, 0, 2, 7, 4, 9};

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

Answer 6

    int arr1[] = {1,2,5,7,89,3};
    int arr2[] = {1,45,87,34,3};

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

Answer 7

here is an O(m+n) solution:

static ArrayList<Integer> commonElements(int[] array1, int[] array2) {
    int p1 = 0;
    int p2 = 0;
    ArrayList<Integer> common = new ArrayList<Integer>();

    while(true) {
        if (array1[p1] == array2[p2]) {
            common.add(array1[p1]);
        }
        if (p1 == array1.length - 1 || p2 == array2.length - 1) break;
        if (array1[p1 + 1] < array2[p2 + 1]) {
            p1++;
        } else {
            p2++;
        }
    }
    return common;
}

Answer 8

Basically the number of common element from the two elements will be dynamic. Hence if you try to put common elements into an array then it won't be possible as you need to declare size of this array (which in this case will be dynamic).

Consider using list. I've tried to keep the logic as simple as possible along with comprehensive variable names.

    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;

    public class Test {

    public static void main(String[] args) {

        int myArray[] = { 2, 2, 7, 7, 2, 1, 5, 4, 5, 1, 1 };
        int myArray2[] = { 2, 3, 4, 7, 10 };

        Test hello = new Test();
        System.out.println(hello.findCommonElement(myArray, myArray2));
    }
    /**
     * 
     * @param a
     * @param b
     * @return commonElements
     */
    public List<Integer> findCommonElement(int[] a, int[] b) {

        List<Integer> commonElements = new ArrayList<Integer>();

        for(int i = 0; i < a.length ;i++) {
            for(int j = 0; j< b.length ; j++) {
                    if(a[i] == b[j]) {  
                    //Check if the list already contains the common element
                        if(!commonElements.contains(a[i])) {
                            //add the common element into the list
                            commonElements.add(a[i]);
                        }
                    }
            }
        }
        return commonElements;
    }
}

Answer 9

I see the following issues with your code:

I want it to return an array with the common numbers once!

So you need to declare that your method returns an array. Add square brackets:

public int[] findCommonElement(int[] a, int[] b) {

Inside your method you must also keep track of all common elements found so far. You may use a new array or more conveniently an ArrayList or even more conveniently a HashSet (since the set automatically eliminates duplicates so you get each common number only once). I think you meant the counter variable to keep track of the number of elements in the new array, only the array is not there yet.

You check:

if (tempCounter == 1) {

This is not right if the number occurs more than once in b. Instead do

if (tempCounter > 0) {

As I said, you need a way to filter away duplicates from a so you don’t get [2, 2, 7, 7, 2, 4] but only [2, 7, 4]. You may use a set I as I mentioned, or you may use ArrayList.contains() or introduce another loop to check whether the number is already in your array of common numbers. Just don’t add it again if it is.

Finally, to print the contents of an array, use Arrays.toString():

    System.out.println(Arrays.toString(hello.findCommonElement(myArray, myArray2)));

Answer 10

an alternative solution for findCommonElement method

public int[] findCommonElement(int[] a, int[] b){
    List<Integer> array = new LinkedList<Integer>();
    Set<Integer> set = new HashSet<Integer>();
    for(int ele:a){
        set.add(ele);
    }

    for(int ele:b){
        if(set.contains(ele)){
            array.add(ele);
        }
    }

    int[] arr = new int[array.size()];
    for(int i = 0; i < array.size();i++){
        arr[i] = array.get(i);
    }
    return arr;
}