AlgoMaster Logo

Intersection of Two Arrays II

easyFrequency6 min readUpdated June 23, 2026

Understanding the Problem

This problem asks us to find the common elements between two arrays while respecting frequencies. If the number 2 appears three times in nums1 and twice in nums2, it should appear twice in the result, the minimum of the two counts.

This differs from "Intersection of Two Arrays" (LeetCode #349), which asks only for unique common elements. Here, duplicates matter. We need to track how many times each element appears in both arrays and output the overlap.

Key Constraints:

  • 1 <= nums1.length, nums2.length <= 1000. With n up to 1000, even an O(n^2) scan stays under a million operations, so correctness matters more than raw speed. The goal is a linear-time solution that also scales beyond these bounds.
  • 0 <= nums1[i], nums2[i] <= 1000. Values are small non-negative integers, so a fixed-size counting array of size 1001 works in place of a hash map. The values also fit comfortably in a 32-bit integer, so there is no overflow concern.

Approach 1: Brute Force

Intuition

For each element in nums1, search through nums2 for a match. When a match is found, add it to the result and mark that element in nums2 as used so it cannot be matched again. Marking matched positions is what enforces the frequency rule: each copy in nums2 can satisfy at most one copy from nums1.

Algorithm

  1. Create a boolean array to track which indices in nums2 have already been matched.
  2. For each element in nums1, scan through nums2.
  3. If you find an unmatched element in nums2 that equals the current element from nums1, add it to the result and mark that index as used.
  4. Return the result.

Example Walkthrough

Input:

0
1
1
2
2
2
3
1
nums1
0
2
1
2
nums2

For each element in nums1, we search nums2 for a match. Element 1 at index 0 has no match. Element 2 at index 1 matches nums2[0], mark it used. Element 2 at index 2 matches nums2[1], mark it used. Element 1 at index 3 has no match.

0
2
1
2
result

Code

The inner scan over nums2 is what makes this quadratic. Counting the frequency of each element in one array up front replaces that scan with an O(1) lookup.

Approach 2: Hash Map (Frequency Count)

Intuition

Count the frequency of every element in nums1 using a hash map. Then walk through nums2 once: for each element, check if it exists in the map with a positive count. If it does, add it to the result and decrement the count. The hash map acts as an inventory of available copies that the scan over nums2 draws from.

Build the map from the smaller array. The map then holds at most min(m, n) distinct keys, and the lookup phase scans the larger array.

Algorithm

  1. If nums1 is longer than nums2, swap them so we always build the map from the smaller array.
  2. Count the frequency of each element in nums1 using a hash map.
  3. Iterate through nums2. For each element, if it exists in the map with count > 0, add it to the result and decrement the count.
  4. Return the result.

Example Walkthrough

nums1
1Build frequency map from nums1: scan all elements
0
1
1
2
2
2
3
1
countMap
1Counting nums1: 1→1, 2→1, 2→2, 1→2
result
1Result starts empty
1/5

Code

This is optimal in time but uses extra space for the hash map. Sorting both arrays first lets two pointers find matches without any auxiliary map, and it handles the follow-up where the inputs arrive already sorted.

Approach 3: Sorting + Two Pointers

Intuition

Sort both arrays, then use two pointers to walk through them in tandem. When both pointers point to the same value, that value belongs to the intersection. When they differ, advance the pointer at the smaller value. The smaller value cannot match anything later in the other array, because every remaining element there is greater than or equal to the current one, so no future match is lost by skipping it.

When the inputs arrive already sorted (the first follow-up), the O(n log n) sort drops out and only the O(m + n) two-pointer scan remains.

Algorithm

  1. Sort both nums1 and nums2.
  2. Initialize two pointers, i at the start of nums1 and j at the start of nums2.
  3. While both pointers are within bounds:
    • If nums1[i] == nums2[j], add the value to the result and advance both pointers.
    • If nums1[i] < nums2[j], advance i.
    • If nums1[i] > nums2[j], advance j.
  4. Return the result.

Example Walkthrough

nums1 (sorted)
1After sorting: nums1=[1,1,2,2], nums2=[2,2]. Initialize i=0, j=0.
0
1
i
1
1
2
2
3
2
nums2 (sorted)
1Initialize j=0
0
2
j
1
2
result
1Result starts empty
1/6

Code