Intersection of Two Arrays

Question

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.

Note

遇到重复相关的问题，仍然优先考虑hash

Solutions

Three Solution

1. Two HashSets
   • nums1的hashset，intersection为另一个hashset，通过遍历nums2构建这个hashset
   • O(n), HashSet.contains only cost O(1)

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

1. Two pointers
   • 分别指向两个数组，比较向后移动
   • O(nlogn) because of 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;
        int 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[] result = new int[set.size()];
        int k = 0;
        for (Integer num : set) {
            result[k++] = num;
        }
        return result;
    }
}

1. Sort, Set, and Binary Search

   • hashset仍然用来保存intersection，对nums1遍历，每个数在nums2进行binarySearch

   • O(nlogn)

     public class Solution {
     public int[] intersection(int[] nums1, int[] nums2) {
       Set<Integer> set = new HashSet<>();
       Arrays.sort(nums2);
       for (Integer num : nums1) {
           if (binarySearch(nums2, num)) {
               set.add(num);
           }
       }
       int i = 0;
       int[] result = new int[set.size()];
     
       //loop through the set
       for (Integer num : set) {
           result[i++] = num;
       }
       return result;
     }
     
     public boolean binarySearch(int[] nums, int target) {
       int low = 0;
       int high = nums.length - 1;
       while (low <= high) {
           int mid = low + (high - low) / 2;
           if (nums[mid] == target) {
               return true;
           }
           if (nums[mid] > target) {
               high = mid - 1;
           } else {
               low = mid + 1;
           }
       }
       return false;
     }
     }
     

Intersection of Two Arrays II

Question

instead of return [2], return [2,2], a.k.a allows duplicate 遇到这类有重复数字的，需要根据次数的，用HashMap instead of HashSet

Solutions

1. HashMap, store the (number, counts)
   • O(n+m)

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        ArrayList<Integer> result = new ArrayList<Integer>();
        for(int i = 0; i < nums1.length; i++)
        {
            if(map.containsKey(nums1[i])) map.put(nums1[i], map.get(nums1[i])+1);
            else map.put(nums1[i], 1);
        }

        for(int i = 0; i < nums2.length; i++)
        {
            if(map.containsKey(nums2[i]) && map.get(nums2[i]) > 0)
            {
                result.add(nums2[i]);
                map.put(nums2[i], map.get(nums2[i])-1);
            }
        }

       int[] r = new int[result.size()];
       for(int i = 0; i < result.size(); i++)
       {
           r[i] = result.get(i);
       }

       return r;
    }
}

1. Two pointers
   • O(nlogn)

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        if (nums1 == null || nums2 == null) return null;
        if (nums1.length == 0 || nums2.length == 0) return new int[0];

        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int len1 = nums1.length;
        int len2 = nums2.length;
        int i = 0, j = 0;
        ArrayList<Integer> results = new ArrayList<>();

        while (i < len1 && j < len2) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                results.add(nums1[i]);
                i++;
                j++;
            }
        }

        int[] nums = new int[results.size()];

        for (int k = 0; k < results.size(); k++) {
            if (results.get(k) != null) {
                nums[k] = results.get(k);
            }
        }
        return nums;
    }
}

Follow ups

Q. What if the given array is already sorted? How would you optimize your algorithm?

I would use two pointers to iterate, now it is O(Math.max(n,m))

Q. What if nums1's size is small compared to nums2's size? Which algorithm is better?

Suppose lengths of two arrays are N and M, the time complexity of hashmap solution is O(N+M) and the space complexity if O(N) considering the hash. So it's better to use the smaller array to construct the counter hash.

Well, as we are calculating the intersection of two arrays, the order of array doesn't matter. We are totally free to swap to arrays.

Q. What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections. If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections. (two pointers)