349. Intersection of Two Arrays

Source link: https://leetcode.com/problems/intersection-of-two-arrays/

Design

The problem could be solved by several intuitive ways, such as initializing two sets (eliminate duplicates) and compare elements within them. However, we would practice the binary search approach for this problem.

  1. Initialize a set to store intersections of both arrays, which could also eliminate duplicates.
  2. Sort the array nums2, traverse the nums1 and apply the binary search to search if there are elements in nums1 and also in nums2.
  3. Transfer elements inside the set into the result array.

Implementation

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

  private boolean binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
      int mid = left + (right - left) / 2;
      if (target == nums[mid]) {
        return true;
      } else if (target > nums[mid]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    return false;
  }
}

Complexity Analysis

Time: $O(nlogn)$

Space: $O(n)$