Array contains element in Java

Question

I've got a task of writing a function that returns integers which are in both two arrays. For example: nums1 [1,2,3] and nums2 [2,3,5] and answer should be [2,3]. I came with this solution:

public static void main(String[] args) {
    System.out.println(arraysIntersection(new int[] {1,2,3}, new int[] {2,3,5}));
}

public static List<Integer> arraysIntersection(int[] nums1, int[] nums2) {
    List<Integer> answer = new ArrayList<>();
    for (int i = 0; i < nums1.length; i++) {
        if (Arrays.asList(nums2).contains(nums1[i])) {
            answer.add(nums1[i]);
        }
    }
    return answer;
}

however it seems this condition doesn't work as intended:

        if (Arrays.asList(nums2).contains(nums1[i]))

It says it doesn't contain the value altough it clearly contains 2 and 3. Any ideas? I know I could just iterate each i over the second array but I thought this solution would be faster. Does anyone knows why it's not working?

Please take `Arrays.asList(nums2)` that is inside the loop, out of the loop, and save it into a variable because it's very very slow to rebuild the array for every iteration !!!! — Yasser CHENIK, Aug 12 '22 at 19:41
`Arrays.asList(nums2)` will give you a `List`, not a `List`, because `nums2` is an array of primitives. To convert a `int[]` to a `List` have a look at: https://stackoverflow.com/questions/1073919/how-to-convert-int-into-listinteger-in-java — QBrute, Aug 12 '22 at 19:42
`return IntStream.of(nums1).filter(x -> IntStream.of(nums2).filter(y -> x == y).findFirst().isPresent()).boxed().collect(Collectors.toList());` — Elliott Frisch, Aug 12 '22 at 19:59

score 1 · Accepted Answer · answered Aug 12 '22 at 19:54

You can do it in O(NlogN) time complexity and O(n) memory. Just sort arrays and use two pointers technique.

    List<Integer> answer = new ArrayList<>();
    int j = 0;
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    for(int i = 0; i < nums1.length; i++) {
        if(i > 0 && nums1[i] == nums1[i - 1]) //we have already processed this number
            continue;
        while(j < nums2.length && nums2[j] < nums1[i])
            j++;
        if(j < nums2.length && nums1[i] == nums2[j])
            answer.add(nums1[i]);
    }
    return answer;

You can do it in O(N) time complexity and O(n) memory (but constant is higher). Just add all elements of nums1 in first HashSet and all elements of nums2 if another HashSet. Then you can for each element in first set check if another set contains this element using O(1)* time.

    List<Integer> answer = new ArrayList<>();
    Set<Integer> set1 = new HashSet<>(), set2 = new HashSet<>();
    set1.addAll(nums1);
    set2.addAll(nums2);
    
    for(var el : set1) {
        if(set2.contains(el)) {
            answer.add(el);
        }
    }
    
    return answer;

*O(1) is middle time of operations with hashset

The worst case of Arrays.sort() for array of primitives if O(n ^ 2), so worst time complexity of second solution is much better. — Voster, Aug 12 '22 at 20:00

Adrian · Answer 2 · 2022-08-13T08:44:18.627

If Arrays is a static object already initialized, or declared at global scope, it may be OK, I don't know for sure. Can't call asList() on an uninitialized object, it must be allocated first.

Now I know, Arrays is a member of the utils package, can be OK. But not anything that looks fine in code, actually works also. As a matter of fact, I don't like the way in which Java calls a function. But it would be more easier and handy like this.

I don't know, if you had included the util package in your code. util, or utils ? Can be 2 different packages, this is important. You can try another way:

import java.util.*;

public static List<Integer> arraysIntersection(int[] nums1, int[] nums2){ 
   List<Integer> answer = new ArrayList<>();
   for (int i = 0; i < nums1.length; i++) {
      int u = nums1[i]; 
      for (int j = 0; j < nums2.length; j++) { 
         if (u == nums2[j]) {  
            answer.add(u); 
            break; 
         }
      } 
   }
   return answer;
}

A break could be necessary, if the values must be added only once. ( a number can be found more times into an array ) The break was meant just for ending the inner loop. The outer loop should continue up to the end of the search.

But the same number can be find more times in the first array. Before returning the answer, the result should be checked for duplicate values. And this is another problem.

It would be more convenient to check before adding number to list. Check if the answer list already contains the number value. And then add the number to the list, if a match is not found. So this can be done more easier:

if (!answer.contains(u)) answer.add(u);

Since you check this condition, the break is not anymore needed. But searching the list so many times, can slow down your code.

From this reason, the u value is read only once, before starting to compare with the another array. So you don't have to read manytimes the same array item, just store it in a temporary variable, u.

In another point of view, when iterating over a collection object, the current value for the current position index could change. It also depends on the basic interface implementation for this object.

If this function would have been written in C, it would have been a very serious problem, to get the value of an item in array, because the current position of the pointer changes. And here is the same, the current read value changes, excepting that we can't see all the underlying mechanism. And if I am not wrong too much, the original Java first time was based also on the C code.

Best regards, Adrian Brinas. Have a nice day.

Thank you, I already knew about this solution but didn't realise I should break, thank you for pointing it out. — Jan Přibyl, Aug 13 '22 at 09:01

Array contains element in Java

2 Answers2