Intersection of Two Arrays II

easy array hash map counter

Problem

Return the intersection of two arrays preserving the multiplicity — each value appears as many times as it shows up in both arrays.

Inputnums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]

Output[4, 9]

Count nums1's values, then for each value in nums2 emit and decrement if positive.

nums1

nums2

from collections import Counter

def intersect(nums1, nums2):
    cnt = Counter(nums1)
    out = []
    for x in nums2:
        if cnt[x] > 0:
            out.append(x)
            cnt[x] -= 1
    return out

function intersect(nums1, nums2) {
  const cnt = new Map();
  for (const x of nums1) cnt.set(x, (cnt.get(x) || 0) + 1);
  const out = [];
  for (const x of nums2) {
    if ((cnt.get(x) || 0) > 0) {
      out.push(x);
      cnt.set(x, cnt.get(x) - 1);
    }
  }
  return out;
}

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums1) cnt.merge(x, 1, Integer::sum);
        List<Integer> out = new ArrayList<>();
        for (int x : nums2) {
            if (cnt.getOrDefault(x, 0) > 0) { out.add(x); cnt.merge(x, -1, Integer::sum); }
        }
        return out.stream().mapToInt(Integer::intValue).toArray();
    }
}

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> cnt;
    for (int x : nums1) cnt[x]++;
    vector<int> out;
    for (int x : nums2) if (cnt[x] > 0) { out.push_back(x); cnt[x]--; }
    return out;
}

Explanation

Unlike the plain intersection, here a value should appear in the result as many times as it appears in both arrays. To respect that, we track how many copies are still available.

First we build a frequency map of nums1 using Counter(nums1). Then we sweep nums2: for each value x, if cnt[x] > 0 we emit it and decrement the count so each available copy is used at most once.

The decrement is the whole trick — it stops us from outputting a shared value more times than it actually occurs in nums1.

Example: nums1 = [4, 9, 5] gives counts {4:1, 9:1, 5:1}. Scanning nums2 = [9, 4, 9, 8, 4]: 9 hits (count→0), 4 hits (count→0), the second 9 is now 0 so skipped, 8 absent, second 4 already 0. Result [9, 4].

Counting one array and probing the other keeps this linear in the combined length of both arrays.

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