Intersection of Two Arrays

LeetCode Q 349 - Intersection of Two Arrays

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

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

Similar Question: Intersection of Two Arrays II

Solution

Method 1: Use Two Set

Time Complexity: O(n)

Code:

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set = new HashSet<>();
    Set<Integer> duplicates = new HashSet<>();
    for (int num: nums1) 
        set.add(num);
    for (int num: nums2) {
        if (set.contains(num))
            duplicates.add(num);
    }

    int[] res = new int[duplicates.size()];
    int index = 0;
    for (int num: duplicates)
        res[index++] = num;

    return res;
}

Method 2: Sort two arrays, and use two pointers to find duplicates

Time Complexity: O(nlogn)

Code:

public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1); Arrays.sort(nums2);
    int i = 0, j = 0, index = 0;
    int[] temp = new int[nums1.length];
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] == nums2[j]) {
            if (index == 0 || temp[index - 1] != nums1[i]) 
                temp[index++] = nums1[i];
            i++; j++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            i++;
        }
    }
    int[] res = new int[index];
    for (int m = 0; m < index; m++) 
        res[m] = temp[m];
    
    return res;
}