Intersection of Two Arrays II — HashMap Frequency Count [Amazon Easy]

Problem Statement

Given nums1 = [1,2,2,1], nums2 = [2,2] → [2,2]. Given nums1 = [4,9,5], nums2 = [9,4,9,8,4] → [4,9].

Key Insight: Count frequencies in nums1 with a HashMap. Walk nums2 — when an element exists in the map with count > 0, add it to the result and decrement the count.

C Solution
C++ Solution
Java Solution
JavaScript Solution
Python Solution
Complexity Analysis

C Solution

#include <stdlib.h>
#include <string.h>
// Use sorted approach for C simplicity
int cmp(const void*a,const void*b){return *(int*)a-*(int*)b;}
int* intersect(int* n1,int s1,int* n2,int s2,int* rsz){
    qsort(n1,s1,sizeof(int),cmp); qsort(n2,s2,sizeof(int),cmp);
    int* r=malloc(sizeof(int)*(s1<s2?s1:s2)); *rsz=0;
    int i=0,j=0;
    while(i<s1&&j<s2){
        if(n1[i]==n2[j]){r[(*rsz)++]=n1[i++];j++;}
        else if(n1[i]<n2[j])i++;else j++;
    }
    return r;
}

C++ Solution

#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int,int> cnt;
        for (int n : nums1) cnt[n]++;
        vector<int> res;
        for (int n : nums2) {
            if (cnt.count(n) && cnt[n] > 0) {
                res.push_back(n);
                cnt[n]--;
            }
        }
        return res;
    }
};

Java Solution

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

JavaScript Solution

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

Python Solution

from collections import Counter
def intersect(nums1, nums2):
    count = Counter(nums1)
    result = []
    for num in nums2:
        if count[num] > 0:
            result.append(num)
            count[num] -= 1
    return result

Complexity Analysis

| O(m+n) time | O(min(m,n)) space |

Follow-up: If arrays are sorted → use two pointers, O(1) extra space. If nums2 is too large for memory → chunk it through a sorted nums1.