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
Recommendation Algorithm Flow for Intersection of Two Arrays II

Solution Approach

Build a frequency map from nums1. Iterate nums2, if the number has a positive count, add to result and decrement.

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

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

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