Intersections of Two Arrays

Problem

Given two arrays, write a function to compute their intersection.

Example: Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

Solution

Brute force using two Hash Sets with time O(n)

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Set<Integer> intersections = new HashSet<>();
        for (int num : nums1) set.add(num);
        for (int num : nums2) {
            if (set.contains(num)) intersections.add(num);
        }
        int[] res = new int[intersections.size()];
        int i = 0;
        for (int num : intersections) res[i++] = num;
        return res;
    }
}

O(nlgn) solution using two pointers and sort

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = new HashSet<>();
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) i++;
            else if (nums1[i] > nums2[j]) j++;
            else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        int[] res = new int[set.size()];
        int index = 0; 
        for (int num : set) res[index++] = num;
        return res;
    }
}

Java 8 two lines! O(nlgn)

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set = Arrays.stream(nums1).boxed().collect(Collectors.toSet());
        return Arrays.stream(nums2).distinct().filter(e -> set.contains(e)).toArray();
    }
}

Analysis

The first solution is very straightforward and easy to come out to one's mind in the interview
We decrease the number of sets by sorting the arrays and two pointers
While the third solution is super concise with the help of Java 8
We need to have a set to be used later in the method filter()
Hence, we convert the IntStream to Stream<Integer> by calling boxed() function
Then we use collect(Collectors.collect()) on the Stream<Integer> we just got
For the nums2, we convert it to IntStream and call distinct() to get distinct elements
Then we use filter() to get intersected elements
At the end, we convert the IntStream to array by calling toArray()

Time complexity is mentioned in the title of each solution