Leetcode

Intersection of Two Arrays II

May 26, 2022 by aAshish

Approach 1: Hash Table

  • Time:O(m + n)
  • Space:O(\min(m, n))

C++

 
class Solution {
 public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size())
      return intersect(nums2, nums1);

    vector<int> ans;
    unordered_map<int, int> count;

    for (const int num : nums1)
      ++count[num];

    for (const int num : nums2)
      if (count.count(num) && count[num]-- > 0)
        ans.push_back(num);

    return ans;
  }
};

JAVA

 
class Solution {
  public int[] intersect(int[] nums1, int[] nums2) {
    if (nums1.length > nums2.length)
      return intersect(nums2, nums1);

    List<Integer> ans = new ArrayList<>();
    Map<Integer, Integer> count = new HashMap<>();

    for (final int num : nums1)
      count.put(num, count.getOrDefault(num, 0) + 1);

    for (final int num : nums2)
      if (count.containsKey(num) && count.get(num) > 0) {
        ans.add(num);
        count.put(num, count.get(num) - 1);
      }

    return ans.stream().mapToInt(i -> i).toArray();
  }
}

Python

 
class Solution:
  def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
    if len(nums1) > len(nums2):
      return self.intersect(nums2, nums1)

    ans = []
    count = Counter(nums1)

    for num in nums2:
      if count[num] > 0:
        ans.append(num)
        count[num] -= 1

    return ans

Approach 2: Two Pointers

  • Time:O(m\log m + n\log n)
  • Space:O(\min(m, n))

C++

 
class Solution {
 public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(begin(nums1), end(nums1));
    sort(begin(nums2), end(nums2));
    // What if the given array is already sorted?
    // How would you optimize your algorithm?

    vector<int> ans;
    int i = 0;  // nums1's index
    int j = 0;  // nums2's index

    while (i < nums1.size() && j < nums2.size())
      if (nums1[i] < nums2[j]) {
        ++i;
      } else if (nums1[i] > nums2[j]) {
        ++j;
      } else {
        ans.push_back(nums1[i]);
        ++i;
        ++j;
      }

    return ans;
  }
};
  • Time:O(\min(m\log n, n\log m))
  • Space:O(\min(m, n))

C++

 
class Solution {
 public:
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    if (nums1.size() > nums2.size())
      return intersect(nums2, nums1);

    vector<int> ans;
    int lowerBound = 0;  // lower bound for the binary search

    sort(begin(nums1), end(nums1));
    sort(begin(nums2), end(nums2));

    for (const int num : nums1) {
      const int i = binarySearch(nums2, lowerBound, num);
      if (i < nums2.size() && nums2[i] == num) {
        ans.push_back(num);
        lowerBound = i + 1;
      }
    }

    return ans;
  }

 private:
  // perform binary search on the bigger array
  // find the first index l s.t nums2[l] >= target
  int binarySearch(vector<int>& nums2, int lo, int target) {
    int l = lo;
    int r = nums2.size();

    while (l < r) {
      const int m = (l + r) / 2;
      if (nums2[m] >= target)
        r = m;
      else
        l = m + 1;
    }

    return l;
  }
};