Java, find intersection of two arrays

Question

I have already read a few other stack overflow threads on this:

to find the intersection of two multisets in java

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

public static int[] intersection (int [] x, int numELementsInX, int [] y, int numElementsInY) {

I am trying to examine two arrays as well as their number of elements (numElementsInX and numElementsInY), and return a new array which contains the common values of array x and y. Their intersection.

Example,if x is{1,3,5,7,9}and y is{9,3,9,4} then
intersection(x, 5, y, 4} should return {3, 9} or {9, 3}

I've read I need to use the LCS algorithm. Can anyone give me an example as to how to do this? Both the array and values in array are initialized and generated in another method, then passed into intersection.

Any help/clarification is appreciated.

EDIT CODE

for (int i=0; i<numElementsInX; i++){
    for (int j=0; j<numElementsInY; j++){
        if (x[j]==x[i]) { //how to push to new array?; 
        }
        else{
        }
    }
}

You already have 2 questions that solve this problem. What have you tried? — Luiggi Mendoza, Jul 25 '13 at 16:10
you don't need the extra `numELementsInX` parameter, you can simply use `x.length`. — jlordo, Jul 25 '13 at 16:10
Im using the extra parameter as the user may enter any number of entries up to 100, both arrays may have a different amount of values. Our professor wants us to initialize the array to 100, THEN keep track of user entry. Which is why I am not using it. — andrsnn, Jul 25 '13 at 16:15

score 60 · Accepted Answer · edited Jul 25 '13 at 16:24

60

The simplest solution would be to use sets, as long as you don't care that the elements in the result will have a different order, and that duplicates will be removed. The input arrays array1 and array2 are the Integer[] subarrays of the given int[] arrays corresponding to the number of elements that you intend to process:

Set<Integer> s1 = new HashSet<Integer>(Arrays.asList(array1));
Set<Integer> s2 = new HashSet<Integer>(Arrays.asList(array2));
s1.retainAll(s2);

Integer[] result = s1.toArray(new Integer[s1.size()]);

The above will return an Integer[], if needed it's simple to copy and convert its contents into an int[].

edited Jul 25 '13 at 16:24

Steven Schlansker

37,580
14
81
100

answered Jul 25 '13 at 16:10

Óscar López

232,561
37
312
386

1

Could you give an example? I will google. My professor has not yet taught us sets. – andrsnn Jul 25 '13 at 16:12
3

you have to mention that `array1` and `array2` need to be `Integer[]` here in order to work correctly, it won't work with `int[]`. – jlordo Jul 25 '13 at 16:15
4

Also, this won't keep duplicates -- even if both `array1` and `array2` have multiple occurrences of `x`, this won't keep those duplicates. – Louis Wasserman Jul 25 '13 at 16:18
1

OK, mentioned both caveats. Thanks, guys! – Óscar López Jul 25 '13 at 16:19
s2 doesn't need to be a set, so you can remove the `new HashSet` constructor call and keep it a `Collection` - might improve performance slightly. – pstanton Jun 28 '18 at 01:59

Bilesh Ganguly · Answer 2 · 2017-11-18T14:57:40.160

22

If you are fine with java-8, then the simplest solution I can think of is using streams and filter. An implementation is as follows:

public static int[] intersection(int[] a, int[] b) {
    return Arrays.stream(a)
                 .distinct()
                 .filter(x -> Arrays.stream(b).anyMatch(y -> y == x))
                 .toArray();
}

edited Nov 18 '17 at 14:57

answered Jun 13 '16 at 11:42

Bilesh Ganguly

3,792
3
36
58

This is incorrect. Consider this case: a = [1,2,2,1] b = [2] Answer should be [2], but this gives the answer as [2,2] – Ujjwal Gulecha Nov 16 '17 at 02:16
that still does not work. Take a = [1,2,2,1] and b = [2,2]. Answer should be [2,2] but this gives answer as [2] – Ujjwal Gulecha Nov 19 '17 at 04:15
@UjjwalGulecha As far as I know, you either care about duplicates or you don't. Can you elaborate on this? Not sure if I'm missing something. – Bilesh Ganguly Nov 20 '17 at 14:23
nvm. What the OP asked was what your answer is. I was looking for intersection with duplicates allowed basically, i.e if A has n x's and B has n-1 x's, their intersection should have n-1 x's. – Ujjwal Gulecha Nov 21 '17 at 18:35
Looks like this doesn't work for `Object`-type like `String` since `toArray()` will return `Object[]` instead. – Andrew T. Sep 15 '20 at 11:22

Husker · Answer 3 · 2021-05-05T14:09:03.590

General test

The answers provide several solutions, so I decided to figure out which one is the most effective.

Solutions

HashSet based by Óscar López
Stream based by Bilesh Ganguly
Foreach based by Ruchira Gayan Ranaweera
HashMap based by ikarayel

What we have

Two String arrays that contain 50% of the common elements.
Every element in each array is unique, so there are no duplicates

Testing code

public static void startTest(String name, Runnable test){
    long start = System.nanoTime();
    test.run();
    long end = System.nanoTime();
    System.out.println(name + ": " + (end - start) / 1000000.  + " ms");
}

With use:

startTest("HashMap", () -> intersectHashMap(arr1, arr2));
startTest("HashSet", () -> intersectHashSet(arr1, arr2));
startTest("Foreach", () -> intersectForeach(arr1, arr2));
startTest("Stream ", () -> intersectStream(arr1, arr2));

Solutions code:

HashSet

public static String[] intersectHashSet(String[] arr1, String[] arr2){
    HashSet<String> set = new HashSet<>(Arrays.asList(arr1));
    set.retainAll(Arrays.asList(arr2));
    return set.toArray(new String[0]);
}

Stream

public static String[] intersectStream(String[] arr1, String[] arr2){
    return Arrays.stream(arr1)
            .distinct()
            .filter(x -> Arrays.asList(arr2).contains(x))
            .toArray(String[]::new);
}

Foreach

public static String[] intersectForeach(String[] arr1, String[] arr2){
    ArrayList<String> result = new ArrayList<>();
    for(int i = 0; i < arr1.length; i++){
        for(int r = 0; r < arr2.length; r++){
            if(arr1[i].equals(arr2[r]))
                result.add(arr1[i]);
        }
    }
    return result.toArray(new String[0]);
}

HashMap

public static String[] intersectHashMap(String[] arr1, String[] arr2){
    HashMap<String, Integer> map = new HashMap<>();
    for (int i = 0; i < arr1.length; i++)
        map.put(arr1[i], 1);

    ArrayList<String> result = new ArrayList<>();
    for(int i = 0; i < arr2.length; i++)
        if(map.containsKey(arr2[i]))
            result.add(arr2[i]);
    return result.toArray(new String[0]);
}

Testing process

Let's see what happens if we give the methods an array of 20 elements:

HashMap: 0.105 ms
HashSet: 0.2185 ms
Foreach: 0.041 ms
Stream : 7.3629 ms

As we can see, the Foreach method does the best job. But the Stream method is almost 180 times slower.

Let's continue the test with 500 elements:

HashMap: 0.7147 ms
HashSet: 4.882 ms
Foreach: 7.8314 ms
Stream : 10.6681 ms

In this case, the results have changed dramatically. Now the most efficient is the HashMap method.

Next test with 10 000 elements:

HashMap: 4.875 ms
HashSet: 316.2864 ms
Foreach: 505.6547 ms
Stream : 292.6572 ms

The fastest is still the HashMap method. And the Foreach method has become quite slow.

Results

If there are < 50 elements, then it is best to use the Foreach method. He strongly breaks away in speed in this category.

In this case, the top of the best will look like this:

Foreach
HashMap
HashSet
Stream - Better not to use in this case

But if you need to process big data, then the best option would be use the HashMap based method.

So the top of the best look like this:

HashMap
HashSet
Stream
Foreach

It's quite obvious that above 'stream' implementation is slow, it's O(n^2), why don't you use HashSet ? — razor, Feb 10 '23 at 16:59
also to do proper measurement, you should warm-up JVM etc. use JMH — razor, Feb 10 '23 at 17:05
if duplicated entries sort first otherwise you might not get the correct results. — Shay Ribera, May 02 '23 at 03:30

Mahesh Naik · Answer 4 · 2016-08-23T22:38:47.490

4

With duplicate elements in array finding intersection.

    int [] arr1 = {1,2,2,2,2,2,2,3,6,6,6,6,6,6,};
    int [] arr2 = {7,5,3,6,6,2,2,3,6,6,6,6,6,6,6,6,};

    Arrays.sort(arr1);
    Arrays.sort(arr2);
    ArrayList result = new ArrayList<>();
    int i =0 ;
    int j =0;
    while(i< arr1.length && j<arr2.length){
    if (arr1[i]>arr2[j]){
        j++;

    }else if (arr1[i]<arr2[j]){
        i++;

    }else {
        result.add(arr1[i]);
        i++;
        j++;
    }
    }
    System.out.println(result);

edited Aug 23 '16 at 22:38

answered Aug 23 '16 at 21:17

Mahesh Naik

71
4

4

Please add an explanation to your answer. Basically explain why it works – warunapww Aug 23 '16 at 21:42

score 2 · Answer 5 · answered Jul 25 '13 at 16:17

2

If you don't want to use other data structures such as a Set, then the basic idea is that you want to iterate through the elements of one of the arrays and for each value see if it appears in the other. How do you see whether it appears in the other array? Walk through the elements in the other array and for each one, see if its value is equal to the value you are looking for. I suspect that you will be best served by trying to work through this problem on your own beyond this point if your goal in taking the class is to learn to write Java well, but it you get stuck you might consider updating your question with the code that you have written so you can get more detailed feedback and pointers in the right direction.

answered Jul 25 '13 at 16:17

tuckermi

839
6
17

updated with a nested for loop, kinda the direction I was attempting to take. Thanks! – andrsnn Jul 25 '13 at 16:23
You can either use the approach from Ruchira's answer (push onto a List or a Set) and then convert to an array before returning or otherwise you will need to keep both an array and a variable where you store the next empty spot in the array (starts at 0). When you find a match, put it in the array at the next empty spot and then increment. Not sure if this is what your course is teaching you, but it should work (except dealing with duplicates, which is an added complication). – tuckermi Jul 29 '13 at 06:23

score 2 · Answer 6 · edited Jul 02 '16 at 14:37

2

Try this:

public static void main(String[] args) {
    int[] arr1 = new int[]{1, 2, 3, 4, 5};
    int[] arr2 = new int[]{3, 2, 5, 9, 11};
    getIntersection(arr1, arr2);
}

public static Object[] getIntersection(int[] arr1, int[] arr2) {
    List<Integer> list = new ArrayList<Integer>();
    for (int i = 0; i < arr1.length; i++) {
        for (int j = 0; j < arr2.length; j++) {
            if (arr1[i] == arr2[j]) {
                list.add(arr1[i]);
            }
        }
    }
    return list.toArray();
}

edited Jul 02 '16 at 14:37

bcsb1001

2,834
3
24
35

answered Jul 25 '13 at 16:26

Ruchira Gayan Ranaweera

34,993
17
75
115

Elegant and it ate my 4GB heap space with 632,698/1,000,000 intersects. I think this is probably faster than HashSet with small arrays and no boxing. – John Jul 30 '21 at 00:05

score 2 · Answer 7 · answered Sep 23 '19 at 20:15

You can find the intersection of two arrays with:

T[] result = Arrays.stream(a1)
                   .filter(new HashSet<>(Arrays.asList(a2))::contains)
                   .toArray(T[]::new);

where T should be substitutable by a reference type e.g. String, Integer, etc.

although the above may seem like it's creating a new set for each element, it's not the case at all. instead only one set instance is created.

The above code is equivalent to:

List<T> list = new ArrayList<>();
HashSet<T> container = new HashSet<>(Arrays.asList(a2));
for (T s : a1) { 
   if (container.contains(s)) list.add(s); 
}
T[] result = list.toArray(new T[0]);

I agree, and these statements do not accept type `int[]` as `a2`. — John, Jul 29 '21 at 23:48
`Arrays.stream(a1).filter(new HashSet<>(Arrays.stream(a2).boxed().collect(Collectors.toList()))::contains).toArray();` — John, Jul 29 '21 at 23:57

score 0 · Answer 8 · edited Mar 25 '17 at 14:10

finding intersection includes duplicate using the hash map.

Output: 1 2 2 15 9 7 12

public static void main(String[] args) {
    int[] arr1 = {1, 2, 2, 1, 5, 9, 15, 9, 7, 7, 12};
    int[] arr2 = {1, 2, 2, 3, 4, 15, 9, 7, 12, 14};
    printIntersect(arr1, arr2);
}

private static void printIntersect(int[] arr1, int[] arr2) {
    Map<Integer, Integer> map = new HashMap<>();
    //put first array to map
    for (int i = 0; i < arr1.length; i++) {
        if (!map.containsKey(arr1[i])) {
            map.put(arr1[i], 1);
        } else {
            map.put(arr1[i], map.get(arr1[i]) + 1);
        }
    }

    //check all value in array two
    for (int i = 0; i < arr2.length; i++) {
        //if exist and value>1  then decrement value
        //if value is 1 remove from map
        if (map.containsKey(arr2[i])) {
            System.out.print(arr2[i] + " ");
            if (map.get(arr2[i]) > 1) {
                map.put(arr2[i], map.get(arr2[i]) - 1);
            } else {
                map.remove(arr2[i]);
            }
        }
    }
}

Sonia Jain · Answer 9 · 2018-02-22T06:39:55.843

if the arrays are sorted

    int a1[]=new int[] {1,2,3,5,7,8};
    int a2[]=new int [] {1,5,6,7,8,9};

     // get the length of both the array
    int n1=a1.length;
    int n2=a2.length;

 //create a new array to store the intersection
   int a3[]=new int[n1];

     //run the loop and find the intersection
    int i=0,j=0,k=0;
    while(i<n1&& j<n2) {
        if(a1[i]<a2[j]) {
         // a1 element at i are smaller than a2 element at j so increment  i
            i++;
        }else if(a1[i]>a2[j]) {
         // a2 element at i are smaller than a2 element at j so increment  j

            j++;
        }else {
             // intersection element store the value and increment i, j, k    to find the next element
            a3[k]=a1[i];
            i++;
            j++;
            k++;
        }
    }


    for(int l=0;l<a3.length;l++) {
        System.out.println(a3[l]);
    }

score 0 · Answer 10 · edited Oct 01 '20 at 06:26

optimised for sorted arrays using only one loop.

    int a1[]=new int[] {1,2,3,5,7,8};
    int a2[]=new int [] {1,5,6,7,8,9};
 // sort both the array
     Arrays.sort(a1);
     Arrays.sort(a2);
     // get the length of both the array
    int n1=a1.length;
    int n2=a2.length;

 //create a new array to store the intersection
   int a3[]=new int[n1];
    
     //run the loop and find the intersection
    int i=0,j=0,k=0;
    while(i<n1&& j<n2) {
        if(a1[i]<a2[j]) {
         // a1 element at i are smaller than a2 element at j so increment  i
            i++;
        }else if(a1[i]>a2[j]) {
         // a2 element at i are smaller than a2 element at j so increment  j
            
            j++;
        }else {
             // intersection element store the value and increment i, j, k    to find the next element
            a3[k]=a1[i];
            i++;
            j++;
            k++;
        }
    }
    
    
    for(int l=0;l<a3.length;l++) {
        System.out.println(a3[l]);
    }

Add some descripton to your answer. – Mathews Sunny Feb 22 '18 at 06:26 — Mathews Sunny, Feb 22 '18 at 06:26

score 0 · Answer 11 · answered Oct 21 '18 at 09:50

How to Find the Intersection of 3 unsorted arrays in Java:-

I have used the Core Java approach using for loops & using Arrays.copyOf to achieve this.

public class Intersection {
    public void intersection3Arrays(int ar1[], int ar2[], int ar3[]) {
            Arrays. sort(ar1);
            Arrays. sort(ar2);
            Arrays. sort(ar3);

            int ar1Len = ar1.length;
            int ar2Len = ar2.length;
            int ar3Len = ar3.length;

            int larArray = ar3Len > (ar1Len > ar2Len ? ar1Len : ar2Len) ? ar3Len : ((ar1Len > ar2Len) ? ar1Len : ar2Len);
            System.out.println("The largest array is " +larArray);
            int[] inputArray1 = Arrays.copyOf(ar1, larArray);
            int[] inputArray2 = Arrays.copyOf(ar2, larArray);
            int[] inputArray3 = Arrays.copyOf(ar3, larArray);

            Integer[] inputArray11 = new Integer[inputArray1.length];
            Integer[] inputArray22 = new Integer[inputArray2.length];
            Integer[] inputArray33 = new Integer[inputArray3.length];

            for (int i = 0; i < inputArray11.length; i++) {
                if (inputArray11[i] == null){
                    inputArray1[i] = 0;
                }
            }
            for (int i = 0; i < inputArray22.length; i++) {
                if (inputArray22[i] == null){
                    inputArray1[i] = 0;
                }
            }
            for (int i = 0; i < inputArray33.length; i++) {
                if (inputArray33[i] == null){
                    inputArray1[i] = 0;
                }
            }

            for (int i = 0; i < inputArray11.length; i++)
                for (int j = 0; j < inputArray22.length; j++)
                    for (int k = 0; k < inputArray33.length; j++)
                    if (inputArray11[i] == inputArray22[j] && inputArray11[i] == inputArray33[k]) {
                        System.out.print(inputArray11[i]+" ");
                    }
        } 
    public static void main(String[] args) {
        Intersection3Arrays arrays = new Intersection3Arrays();
        int ar1[] = { 1, 2, 5, 10, 20, 40, 80 };
        int ar2[] = { 80, 100, 6, 2, 7, 20 };
        int ar3[] = {3, 4, 15, 20, 30, 70, 80, 120}; 
        arrays.intersection3Arrays(ar1, ar2, ar3);
    }
}

score 0 · Answer 12 · answered Oct 29 '18 at 03:36

If you ever wanted to implement this in python, this is one way that you can find intersection.

#find intersection
def find_intersec(list_a, list_b): 
    return set(list_a).intersection(list_b) 

#since lists are kind of like arrays in python we use two lists
list_a = [ 4, 9, 1, 17, 11, 26, 28, 10,28, 26, 66, 91] 
list_b = [9, 9, 74, 21, 45, 11, 63,10] 
print(find_intersec(list_a, list_b))

score 0 · Answer 13 · answered Feb 25 '20 at 07:32

I hope this example will simple one.pass two arrays and you will definitely get INTERSECTION of array without duplicate items.

private static int[] findInterserctorOfTwoArray(int[] array1, int[] array2) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int element : array1) {
            for (int element2 : array2) {
                if(element==element2) {
                    map.put(element, element);
                }
            }
        }
        int[] newArray=new int[map.size()];
        int con=0;
        for(Map.Entry<Integer, Integer> lst:map.entrySet()) {
            newArray[con]=lst.getValue();
            con++;
        }
        return newArray;
    }

score 0 · Answer 14 · answered Jul 30 '21 at 13:52

Primitive Iterator: 6 Times Faster than HashSet

Tested on sorted arrays of 10,000,000 random elements, values between 0 and 200,000,000. Tested on 10 processor i9 with 4GB heap space. Sort time for two arrays was 1.9 seconds.

results:

primitive() - 1.1 seconds

public static int[] primitive(int[] a1, int[] a2) {
    List<Integer> list = new LinkedList<>();
    OfInt it1 = Arrays.stream(a1).iterator();
    OfInt it2 = Arrays.stream(a2).iterator();
    int i1 = it1.next();
    int i2 = it2.next();
    do {
      if (i1==i2) {
        list.add(i1);
         i1 = it1.next();
      }
      if (i1 < i2) i1 = it1.next();
      if (i2 < i1) i2 = it2.next();
    } while(it1.hasNext() && it2.hasNext());
    if (i1==i2) list.add(i1);
    return list.stream().mapToInt(Integer::intValue).toArray();
  }

boxed() - 6.8 seconds

  public static int[] boxed(int[] a1, int[] a2) {
    return Arrays.stream(a1)
                   .filter(new HashSet<>(Arrays.stream(a2).boxed()
                         .collect(Collectors.toList()))::contains)
                   .toArray();
  }