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));

    }
}

Multiple problems here. First, your function returns 0. Second, if you want to return more than one number you must change findCommonElement to return an Array or List. — mdewit, Nov 16 '16 at 13:11
Also, the counter variable in findCommonElement currently does nothing. Why does the if(tempCounter == 1) statement only check whether the tempCounter is 1? Should it not be if(tempCounter > 0)? — mdewit, Nov 16 '16 at 13:17
Please indent you code properly — I have trouble reading it. — Ole V.V., Nov 16 '16 at 13:36
Possible duplicate of [Java, find intersection of two arrays](http://stackoverflow.com/questions/17863319/java-find-intersection-of-two-arrays) — xenteros, Nov 16 '16 at 13:46

score 7 · Answer 1 · answered Nov 16 '16 at 13:18

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

I think that solution is much better because has less complexity, is it `n+n+n` that is much better than `nxn` — deFreitas, Sep 24 '17 at 03:31

score 1 · Answer 2 · answered Oct 16 '17 at 04:38

1

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

answered Oct 16 '17 at 04:38

talshahar

528
3
12

Are you considering both the arrays to be pre-sorted. – Akshay Oct 25 '17 at 17:24
1

this is working only for sorted array. int []array1= {2,3,5,6,7,9,11,22}; int []array2= {22,2,4,5,6,8,10,12}; ArrayList list = commonElements(array1, array2); System.out.println(list); Output : [2, 5, 6] – Ashish Agrawal Yodlee Apr 20 '19 at 14:28
I've made some improvements in this and posted it. Covers the edge cases. https://stackoverflow.com/a/67289502/6438896 – Ayush Kumar Apr 27 '21 at 19:35

score 0 · Answer 3 · answered Nov 16 '16 at 13:57

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)));

Mrudav Shukla · Accepted Answer · 2016-11-16T15:02:17.847

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

@deFreitas I can think of O(n) solution, where I am use a hashmap for one array and while traversing other i just do map.containsKey() everytime.... I am trying to think if there is any better way to do that...other than creating O(n) space — Akki, Mar 12 '19 at 09:52
This would be a very costly approach with `O(n*n)` complexity. Check out my solution with `O(n)` complexity and without the use of HashSets; thereby saving memory. https://stackoverflow.com/a/67289502/6438896 — Ayush Kumar, Apr 27 '21 at 19:33

score 0 · Answer 5 · edited Apr 28 '21 at 05:39

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);
}

score 0 · Answer 6 · answered Sep 11 '18 at 08:42

0

    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] +" ");
            }
        }
    }

answered Sep 11 '18 at 08:42

Manjunath Jakkandi

1

While this code may solve the problem, a few words of explanation will help current and future readers understand your answer even better. – Thom Sep 11 '18 at 11:13

Keshav Gera · Answer 7 · 2019-08-20T13:00:54.297

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 );
        }
       }
    }
}

score 0 · Answer 8 · answered Apr 27 '21 at 19:29

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

score 0 · Answer 9 · answered Sep 19 '21 at 19:21

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

score -1 · Answer 10 · answered Oct 15 '18 at 15:36

-1

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]);
            }
        }
    }

answered Oct 15 '18 at 15:36

Ishan Lakshitha

365
3
6

1

Welcome to Stack Overflow! It is recommended to add a brief explanation of your code, which goes a long way in helping others understand it. – Acapulco Oct 15 '18 at 15:59

finding common elements in two integer arrays java

10 Answers10

Linked