What pattern does Intersection of Two Arrays II use?

The Pattern: Hash Maps (Frequency Counting) The Heuristic: When needing to find common elements with counts between two arrays, use a hash map to store frequencies of one array and then iterate the other to efficiently find intersections by decrementing counts.

Intersection of Two Arrays II | Hash Maps

Q: What is the time complexity of Intersection of Two Arrays II?

O(n + m). Building the frequency map takes O(n) time, iterating through nums2 takes O(m), and each hash map operation is O(1) on average, resulting in linear time relative to input sizes.

Problem

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

1 ≤ nums1.length, nums2.length ≤ 1000
0 ≤ nums1[i], nums2[i] ≤ 1000

Example

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2,2]

A brute-force approach would check each element of nums1 against nums2, removing matched elements to avoid duplicates, resulting in O(n*m) time complexity. The optimal approach uses a frequency map to count occurrences in nums1, then iterates through nums2 to collect common elements up to the minimum count. For example, nums1 has two '2's, nums2 has two '2's, so the intersection includes two '2's.

Approach

Straightforward Solution

A naive nested loop approach compares each element in nums1 with every element in nums2, removing matched elements to avoid duplicates. This approach is O(n*m) and inefficient for large inputs.

Core Observation

The intersection requires counting how many times each element appears in both arrays and including it in the result the minimum number of times it appears in either array.

Path to Optimal

Preview

Recognizing that counting frequencies is key, the problem transforms into a frequency comparison. Using a hash map (or Counter) to store counts of nums1 elements allows O(1) average lookup…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Build a frequency map of nums1 using a hash map. Iterate through nums2, and for each element, if it exists in the map with a positive count, append it to the result and decrement the count…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Building the frequency map takes O(n) time, iterating through nums2 takes O(m), and each hash map operation is O(1) on average, resulting in linear time relative to input sizes.

Space

O(n)

The frequency map stores counts for elements in nums1, which in the worst case can be all n elements. The output array space is not counted as auxiliary space.

Solution

Python

1from collections import Counter
2
3class Solution:
4    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
5        remaining_counts = Counter(nums1)
6        intersection = []
7
8        for num in nums2:
9            if remaining_counts[num] > 0:
10                intersection.append(num)
11                remaining_counts[num] -= 1
12
13        return intersection

Step-by-Step Solution

1

Build Frequency Map for First Array Elements

5remaining_counts = Counter(nums1)
6intersection = []

Objective

To count the occurrences of each element in nums1 using a hash map for efficient lookup.

Key Insight

Counting frequencies upfront transforms the problem from repeated searches to constant-time lookups. This precomputation enables efficient intersection detection by tracking how many times each element can still be matched.

Interview Quick-Check

Core Logic

Using a hash map to store frequencies allows O(1) average-time checks for whether an element from nums2 can be included in the intersection.

Common Pitfalls & Bugs

Failing to use a frequency map leads to inefficient nested loops and duplicate counting.

2

Iterate Through Second Array to Collect Intersection Elements

To traverse nums2 and append elements to the intersection list only if they appear in nums1 with remaining count.

3

Return the Computed Intersection List

To output the final list containing the intersection elements with correct counts.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

if remaining_counts[num] > 0:

Check if the current element from nums2 has a positive count in the frequency map.

This condition ensures that only elements present in nums1 and not yet fully matched are added to the intersection, preventing overcounting.

Line 5 Critical

remaining_counts = Counter(nums1)

Create a frequency map counting occurrences of each element in nums1.

This line sets up the essential data structure that enables constant-time frequency lookups, transforming the problem from repeated searches to efficient counting.

Full line-by-line criticality + rationale for all 7 lines available on Pro.

Test Your Understanding

Why do we decrement the count in the frequency map after adding an element to the intersection?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Intersection of Two Arrays II from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Intersection of Two Arrays II drill

or drill a free problem

1	`from collections import Counter`
2
3	`class Solution:`
4	`def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:`
5	`remaining_counts = Counter(nums1)`
6	`intersection = []`
7
8	`for num in nums2:`
9	`if remaining_counts[num] > 0:`
10	`intersection.append(num)`
11	`remaining_counts[num] -= 1`
12
13	`return intersection`