Intersection of Two Arrays II — Problem & Solution
Intersection of Two Arrays II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Intersection of Two Arrays II is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Meta, Bloomberg and Databricks interviews.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Sorting, Two Pointers
- Asked at: Amazon, Meta, Bloomberg, Databricks
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two integer arrays nums1 and nums2, return their intersection including multiplicity: each value appears as many times as it shows in both arrays. Return the result in increasing order.
Example 1
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Explanation: 2 appears twice in each array, so it appears twice in the answer.
Example 2
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Example 3
Input: nums1 = [1,2], nums2 = [3,4]
Output: []
Constraints
1 <= nums1.length, nums2.length <= 300 <= nums1[i], nums2[i] <= 60
Follow-up: What if the arrays were already sorted? What if one of them was far larger than the other?
Hints for Intersection of Two Arrays II
Hint 1
A plain set loses the counts. Use a map from value to how many copies remain.
Hint 2
Build the map from one array, then walk the other and take a copy whenever the remaining count is positive.
Hint 3
Decrement the count as you take, so a value is never taken more often than it occurs.
How to solve Intersection of Two Arrays II
Multiplicity means a set is not enough. Count the first array, then walk the second and take a value only while its remaining count is positive.
Approach
- Build
count[value]fromnums1. - For each
xinnums2, ifcount[x] > 0, appendxand decrement. - Sort the collected values.
Why it works
Each take decrements the budget for that value, so it is emitted min(count1, count2) times — the multiset intersection.
Complexity
- Time —
O(n + m + k log k) - Space —
O(n)
Pitfalls
- Count the smaller array if memory matters; the logic is symmetric.
- If both arrays are already sorted, two pointers do it with no map.
Reference solution
Python
def intersect(nums1, nums2):
count = {}
for x in nums1:
count[x] = count.get(x, 0) + 1
out = []
for x in nums2:
if count.get(x, 0) > 0:
out.append(x)
count[x] -= 1
out.sort()
return outJava
public static int[] intersect(int[] nums1, int[] nums2) {
Map<Integer, Integer> count = new HashMap<>();
for (int x : nums1) count.put(x, count.getOrDefault(x, 0) + 1);
List<Integer> out = new ArrayList<>();
for (int x : nums2) {
int c = count.getOrDefault(x, 0);
if (c > 0) {
out.add(x);
count.put(x, c - 1);
}
}
Collections.sort(out);
int[] res = new int[out.size()];
for (int i = 0; i < res.length; i++) res[i] = out.get(i);
return res;
}C++
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> count;
for (int x : nums1) count[x]++;
vector<int> out;
for (int x : nums2) {
if (count[x] > 0) {
out.push_back(x);
count[x]--;
}
}
sort(out.begin(), out.end());
return out;
}JavaScript
var intersect = function(nums1, nums2) {
const count = new Map();
for (let i = 0; i < nums1.length; i++) {
count.set(nums1[i], (count.get(nums1[i]) || 0) + 1);
}
const out = [];
for (let i = 0; i < nums2.length; i++) {
const c = count.get(nums2[i]) || 0;
if (c > 0) {
out.push(nums2[i]);
count.set(nums2[i], c - 1);
}
}
return out.sort(function(a, b) { return a - b; });
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets