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?

Answer 1

1. 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;

2. 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