Intersection of Two Arrays — Problem Statement & Solution Guide
Problem Description
You are given two integer arrays, nums1 and nums2. Construct a new array that contains every integer that appears in both input arrays. If a value occurs k times in nums1 and m times in nums2, it should appear min(k,m) times in the result. The order of elements in the output array is not important; any ordering that satisfies the multiplicity rule is acceptable. Your task is to implement a function that returns this intersection array.
Input: Two arrays of integers, nums1 and nums2.
Output: An array of integers representing the intersection with correct multiplicities.
The function should handle large inputs efficiently, using linear or near‑linear time and constant additional space beyond the output.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Intersection of Two Arrays"
WHY DOES IT MATTER?
Multiset intersection appears in data deduplication, recommendation engines, and inventory reconciliation, where preserving exact counts is critical. Mastering this pattern teaches you how to efficiently handle frequency‑based constraints, a skill that recurs in problems like anagrams, sliding‑window frequency checks, and histogram comparisons.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that you don't need to compare every pair; instead, you can pre‑aggregate frequencies (hash map) or order the data (sorting) so that each element is examined at most once, collapsing the quadratic search space to linear or linear‑logarithmic.
REAL-WORLD CONNECTION
Think of two warehouses syncing stock levels: each SKU appears a certain number of times in each location. The intersection algorithm is analogous to a distributed reconciliation protocol that only transfers the minimum overlapping quantity, minimizing network traffic and storage overhead.
Always scan the smaller input to build the frequency map; this reduces auxiliary space and improves cache locality. In an interview, state this choice explicitly before coding to demonstrate space‑time awareness.
COMPLEXITY AT A GLANCE
O(n + m)O(min(n, m))Core Theory — Why This Approach?
The intersection‑of‑two‑arrays problem is a classic example of multiset intersection, where each element’s multiplicity matters. A naive solution would compare each element of the first array against every element of the second, leading to O(n·m) time, which quickly becomes prohibitive for large inputs (e.g., 10^5 elements each). The optimal paradigm leverages hash‑based counting or sorting to reduce the search space: by recording the frequency of each value in one array, we can determine in constant amortized time how many times it appears in the other, respecting the min(k,m) rule. This transforms the problem into linear time with respect to the total number of elements, plus the overhead of building a hash map or sorting.
When using a hash map, we iterate through the smaller array to build a frequency table (O(min(n,m)) space) and then scan the larger array, decrementing counts and emitting results when a matching count exists. Sorting both arrays (O(n log n + m log m)) also works: a two‑pointer technique walks the sorted lists in tandem, advancing pointers based on value comparison, which naturally respects multiplicities. Both approaches avoid the quadratic blow‑up of the brute‑force method and are cache‑friendly, making them suitable for production‑grade workloads.
Interview Questions on This Problem
Q1How would you modify the solution if the arrays are stored on disk and cannot both fit into memory?
Use an external‑merge strategy: sort each array using an external sort (e.g., multi‑way merge sort) and then stream the sorted files with two pointers, emitting intersections on the fly. This keeps memory usage O(1) beyond the buffers needed for the streams.
Q2What is the time and space complexity if the input arrays are already sorted?
With pre‑sorted inputs, a two‑pointer scan runs in O(n + m) time and O(1) extra space (ignoring the output array), because no additional data structures are required.
Q3Can you achieve O(n + m) time without extra space when the value range is bounded (e.g., 0 ≤ value ≤ 10^5)?
Yes. Allocate a fixed‑size counting array of length 10^5 + 1, increment counts for nums1, then decrement while scanning nums2, appending values when the count stays positive. This runs in O(n + m) time and O(R) space where R is the range, which is constant relative to input size.
Examples
Input
nums1 = [1,2,2,1] nums2 = [2,2]
Output
[2,2]
Explanation: Count occurrences: 1 appears twice in nums1 and zero times in nums2 → min(2,0)=0. 2 appears twice in nums1 and twice in nums2 → min(2,2)=2. The intersection contains two 2’s, so the output is [2,2].
Input
nums1 = [4,9,5] nums2 = [9,4,9,8,4]
Output
[4,9]
Explanation: Counts: 4 appears once in nums1 and twice in nums2 → min(1,2)=1. 9 appears once in nums1 and twice in nums2 → min(1,2)=1. 5 appears once in nums1 and zero times in nums2 → min(1,0)=0. The intersection contains one 4 and one 9; any order such as [4,9] is valid.
Input
nums1 = [-1,-2,-3] nums2 = [-1,-2,-3,-4]
Output
[-1,-2,-3]
Explanation: Each of -1, -2, -3 appears once in both arrays, so each appears once in the result. -4 appears only in nums2 and is excluded.
Input
nums1 = [1,1,1,1] nums2 = [1,1]
Output
[1,1]
Explanation: 1 appears four times in nums1 and twice in nums2 → min(4,2)=2. The intersection contains two 1’s.
Input
nums1 = [5,10,15] nums2 = [20,25,30]
Output
[]
Explanation: No value is common to both arrays, so the intersection is empty.
Constraints
- 1 <= nums1.length <= 100000
- 1 <= nums2.length <= 100000
- -1000000000 <= nums1[i], nums2[i] <= 1000000000
- The total number of elements across both arrays does not exceed 200000
- The solution must run in O(n + m) time and use O(n) additional space, where n and m are the lengths of nums1 and nums2 respectively.
Optimal Approach & Strategy
Build a frequency hash map from the smaller array, then iterate the larger array, appending elements to the result while decrementing the map’s count when it’s positive.
Brute Force Approach
Loop through every element of nums1 and, for each, scan nums2 to find a matching unused element, marking it as used when found.
Verified Code Solutions
function intersection(nums1, nums2) {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
let result = [];
for (let num of set1) {
if (set2.has(num)) {
result.push(num);
}
}
return result;
}class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> set1(nums1.begin(), nums1.end());
unordered_set<int> set2(nums2.begin(), nums2.end());
vector<int> result;
for (int num : set1) {
if (set2.find(num) != set2.end()) {
result.push_back(num);
}
}
return result;
}
};import java.util.*;
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for (int num : nums1) {
set1.add(num);
}
for (int num : nums2) {
set2.add(num);
}
set1.retainAll(set2);
int[] result = new int[set1.size()];
int i = 0;
for (int num : set1) {
result[i++] = num;
}
return result;
}
}def intersection(nums1, nums2):
set1 = set(nums1)
set2 = set(nums2)
return list(set1 & set2)function intersection(nums1, nums2) {
let set1 = new Set(nums1);
let set2 = new Set(nums2);
let result = [];
for (let num of set1) {
if (set2.has(num)) {
result.push(num);
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.