Code Logo

Intersection of Two Arrays II

Published at24 Jul 2026
Created by
Medium 0 views
Like0

Given two integer arrays nums1 and nums2, return an array of their intersection as a list. Each element in the result must appear as many times as it appears in both arrays. You may return the result in any order.

Unlike the simpler "Intersection of Two Arrays" which uses a hash set for unique matches, this version tracks multiplicities. A hash map counter is the natural tool: count occurrences of each number in the first array, then iterate the second array, checking if the count is positive. If so, include the number and decrement the count.

This algorithm runs in O(n + m) time with O(min(n, m)) space. A brute-force double loop would be O(n * m) and fail for large arrays. The hash map approach is optimal because it trades space for time. It also handles the duplicate requirement naturally — each occurrence in nums1 is tracked individually by the counter, and each match in nums2 consumes one unit.

Edge cases include one or both arrays being empty (return []), arrays with no common elements (return []), and arrays where one number appears more times in nums2 than in nums1 (only include up to the count in nums1).

When one array is much larger than the other, it is more efficient to build the frequency map from the smaller array to reduce memory usage. The algorithm remains the same but the space becomes O(min(n,m)) instead of O(max(n,m)).

Example Input & Output

Example 1
Input
[1,2,2,1], [2]
Output
[2]
Explanation

nums2 has fewer duplicates.

Example 2
Input
[4,9,5], [9,4,9,8,4]
Output
[4,9] or [9,4]
Explanation

Each number appears once in intersection.

Example 3
Input
[1,2,2,1], [2,2]
Output
[2,2]
Explanation

Both 2s appear in both arrays.

Example 4
Input
[], [1,2]
Output
[]
Explanation

Empty first array yields empty result.

Example 5
Input
[1,2], [3,4]
Output
[]
Explanation

No common elements.

Algorithm Flow

Recommendation Algorithm Flow for Intersection of Two Arrays II

Solution Approach

Find the intersection of two arrays including duplicates. Count frequencies of elements in the first array, then iterate through the second array: if an element has a positive count, add it to the result and decrement the count.

function intersect(nums1, nums2) {
  var freq = {}, result = [];
  for (var i = 0; i < nums1.length; i++) freq[nums1[i]] = (freq[nums1[i]] || 0) + 1;
  for (var i = 0; i < nums2.length; i++) {
    if (freq[nums2[i]]) { result.push(nums2[i]); freq[nums2[i]]--; }
  }
  return result;
}

Using a frequency map ensures duplicates are handled correctly. Each matching element decrements the count, preventing more copies than actually exist.

Time O(n + m), Space O(n).

Best Answers

java
import java.util.*;
class Solution {
    public int[] solution(int[] nums1, int[] nums2) {
        Map<Integer,Integer> freq = new HashMap<>();
        for (int n : nums1) freq.put(n, freq.getOrDefault(n, 0) + 1);
        List<Integer> list = new ArrayList<>();
        for (int n : nums2) {
            if (freq.getOrDefault(n, 0) > 0) {
                list.add(n);
                freq.put(n, freq.get(n) - 1);
            }
        }
        int[] r = new int[list.size()];
        for (int i = 0; i < list.size(); i++) r[i] = list.get(i);
        return r;
    }
}