Intersection of Two Arrays

Question (LC.349)

Given two arrays, find their intersection.

Example

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Return: result = [2, 2] nope need to return [2]

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

Analysis

Hashing: Quick and dirty O(n) time and space solution - hash set. Dump nums1 in a hash set, then use nums2 to check against the hash set. Time analysis is a bit off. We need O(n+m) time and only need O(min(n,m)) space. Alright now we want to do in in constant space. Sorting seems like the alternative approach.

Sorting: The runtime is O(nlogn + mlogm). Space is O(1). Then use two pointers (one for each array) to find the common element. What if n or m is super large?

Binary search: We only need to sort one array (the smaller one). Then for each element in the bigger array, we binary search in the smaller one. Again O(1) space. For runtime, if n < m, O(nlogn + mlogn) or m < n O(mlogm + nlogm) so you swap the big term logm with a smaller term logn.

Hash Set

public int[] intersection(int[] nums1, int[] nums2) {
    if (nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0) {
        return new int[] {};
    }
    Set<Integer> set1 = new HashSet<>();
    for (int num : nums1) {
        set1.add(num);
    }
    Set<Integer> result = new HashSet<>();
    for (int num: nums2) {
        if (set1.contains(num)) {
            result.add(num);
        }
    }
    int[] intsec = new int[result.size()];
    int i = 0;
    for (Integer num: result) {
        intsec[i++] = num.intValue();
    }
    return intsec;
}

Sorting and P1/P2

public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int n = nums1.length, m = nums2.length;
    int i = 0, j = 0;

    Set<Integer> results = new HashSet<>();
    // scan all the way to the end of num1 or the end of num2
    while (i < n && j < m) {
        if (nums1[i] == nums2[j]) {
            results.add(nums1[i]);
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    int[] intsec = new int[results.size()];
    int a = 0;
    for (Integer ele : results) {
        intsec[a++] = ele;
    }
    return intsec;
}

Binary Search

public int[] intersection(int[] nums1, int[] nums2) {
    Arrays.sort(nums2);
    Set<Integer> results = new HashSet<>();
    for (int i = 0; i < nums1.length; i++) {
        if (binarySearch(nums2, nums1[i])) {
            results.add(nums1[i]);
        }   
    }
    int[] intsec = new int[results.size()];
    int a = 0;
    for (Integer ele : results) {
        intsec[a++] = ele;
    }
    return intsec;
}

// vanilla binary search
public boolean binarySearch(int[] data, int query) {
    int start = 0, end = data.length - 1;
    int mid;
    while (start <= end) {
        mid = (start + end) / 2;
        if (data[mid] == query) {
            return true;
        } else if (data[mid] < query) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }
    return false;
}