Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

350. Intersection of Two Arrays II

Time: $O(m + n)$

Space: $O(\min(m, n))$

			


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;
  }
};




			


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(Integer::intValue).toArray();
  }
}




			


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