Log inSign up
easyLeetCodeNot Started

Intersection of Two Arrays II

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Arrays
Solve on LeetCode
Lesson

Problem Statement

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.

Example 1 · Standard Duplicated Overlap:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2, 2]
Explanation: The number 2 appears twice in nums1 and twice in nums2. Therefore, 2 appears twice in the intersection.

Example 2 · Multiple Elements with Varied Frequencies:

Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [4, 9]
Explanation: 4 appears once in nums1 and twice in nums2 -> min count is 1. 9 appears once in nums1 and twice in nums2 -> min count is 1. [9, 4] is also valid.

Example 3 · No Common Elements:

Input: nums1 = [1, 2, 3], nums2 = [4, 5, 6]
Output: []
Explanation: There are no common elements between the two arrays.

Constraints:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

Prerequisites

Before attempting this problem, you should be comfortable with:

  • Hash Map / Frequency tables
  • Two Pointers technique on sorted collections
  • Understanding multi-set intersection vs. standard set intersection

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Distinguish between unique set intersection (Intersection I) and multi-set frequency intersection (Intersection II).
  • Utilize Hash Maps to track and decrement available frequencies in O(N + M) time.
  • Implement the Two-Pointer sorted array approach for memory-constrained environments.
  • Write production-grade solutions across C++, Java, Python, and JavaScript.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Problem requires intersection where duplicate elements are preserved based on common counts.
  • Multi-set intersection / frequency intersection keyword.
  • Unsorted arrays that can be tracked using a frequency map or sorted for two-pointer matching.

Algorithmic Decision Tree:

  • If arrays are unsorted: Count frequencies of the smaller array in a Hash Map, then decrement while scanning the other array (O(N + M) time, O(min(N, M)) space).
  • If arrays are already sorted or memory is constrained: Traverse both arrays simultaneously with Two Pointers (O(N + M) time, O(1) space).

Connected Patterns:

Two PointersSliding WindowPrefix Sum

1. Brute Force — Nested Search with Visited Array

Intuition

For each element in nums1, scan nums2 to find an unvisited match. Mark matched elements in nums2 as visited to prevent reusing them.

Algorithm

  1. Create a boolean array visited of size nums2.length initialized to false.
  2. Initialize an empty list result.
  3. For each element x in nums1:
  4. Loop through j from 0 to nums2.length - 1:
  5. If !visited[j] and nums2[j] == x:
  6. Mark visited[j] = true.
  7. Append x to result.
  8. Break out of inner loop.
  9. Return result.

Match and Mark Visited (O(M*N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Value 1 is not in nums2
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1
2
2
0
↑ i=0
1
2
Hash map state
Execution state
result[]
visitedN2[]
No match for 1. Continue.
Variables at this step
result
[]
visitedN2
[]
Check / comparison
nums1[0] = 1: search nums2 for unvisited 1
Decision / next transition
No match for 1. Continue.
Why this step matters

Value 1 is not in nums2.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3using namespace std;
4
5// Brute Force: Scan with visited boolean array
6vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
7 vector<int> result;
8 vector<bool> visited(nums2.size(), false);
9
10 for (int x : nums1) {
11 for (size_t j = 0; j < nums2.size(); j++) {
12 if (!visited[j] && nums2[j] == x) {
13 visited[j] = true;
14 result.push_back(x);
15 break; // Move to next element in nums1
16 }
17 }
18 }
19
20 return result;
21}
22
23int main() {
24 vector<int> nums1 = {1, 2, 2, 1};
25 vector<int> nums2 = {2, 2};
26 vector<int> res = intersect(nums1, nums2);
27
28 cout << "Output: [";
29 for (size_t i = 0; i < res.size(); i++) {
30 cout << res[i] << (i + 1 < res.size() ? ", " : "");
31 }
32 cout << "]" << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N^2) — Time complexity for Approach 1: Brute Force — Nested Search with Visited Array.
  • Space complexity: O(1) — Space complexity for Approach 1: Brute Force — Nested Search with Visited Array.

Why Brute Force Doesn't Scale:

For N = 105, quadratic O(N2) approaches require ~1010 operations, exceeding the standard 1-second CPU budget.

The optimal approach processes N elements in a single or logarithmic pass, completing in under 10ms with minimal memory footprint.

2. Better — Sort Both Arrays + Two Pointers

Intuition

Sort both arrays and step through them with two pointers; whenever elements match, record the element and advance both pointers.

Algorithm

  1. Sort nums1 and nums2 in ascending order.
  2. Set i = 0, j = 0, and initialize empty list result.
  3. While i < nums1.length and j < nums2.length:
  4. If nums1[i] == nums2[j]:
  5. Append nums1[i] to result.
  6. Increment i++ and j++.
  7. Else if nums1[i] < nums2[j], increment i++.
  8. Else, increment j++.
  9. Return result.

Sort Both + Two Pointers (O(M log M + N log N) Time)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Skip smaller value
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1
2
0
↑ i
1
↑ j
Hash map state
Execution state
i0
j0
result[]
Advance i to 1.
Variables at this step
i
0
j
0
result
[]
Check / comparison
Sorted nums1: [1, 1, 2, 2], nums2: [2, 2]. nums1[0] (1) < nums2[0] (2)
Decision / next transition
Advance i to 1.
Why this step matters

Skip smaller value.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <algorithm>
2#include <iostream>
3#include <vector>
4using namespace std;
5
6// Two Pointers on sorted arrays
7vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
8 sort(nums1.begin(), nums1.end());
9 sort(nums2.begin(), nums2.end());
10
11 vector<int> result;
12 int i = 0, j = 0;
13 int n = nums1.size(), m = nums2.size();
14
15 while (i < n && j < m) {
16 if (nums1[i] == nums2[j]) {
17 result.push_back(nums1[i]);
18 i++;
19 j++;
20 } else if (nums1[i] < nums2[j]) {
21 i++;
22 } else {
23 j++;
24 }
25 }
26
27 return result;
28}
29
30int main() {
31 vector<int> nums1 = {4, 9, 5};
32 vector<int> nums2 = {9, 4, 9, 8, 4};
33 vector<int> res = intersect(nums1, nums2);
34
35 cout << "Output: [";
36 for (size_t k = 0; k < res.size(); k++) {
37 cout << res[k] << (k + 1 < res.size() ? ", " : "");
38 }
39 cout << "]" << endl;
40 return 0;
41}

Time & Space Complexity

  • Time complexity: O(N log N) — Time complexity for Approach 2: Better — Sort Both Arrays + Two Pointers.
  • Space complexity: O(N) — Space complexity for Approach 2: Better — Sort Both Arrays + Two Pointers.

3. Optimal — Frequency Hash Map (Linear Time)

Intuition

Count the frequency of each number in the smaller array using a hash map, then decrement frequencies as matches are found in the other array.

Algorithm

  1. If nums1.length > nums2.length, swap arguments to ensure smaller map size.
  2. Create a hash map freq to count occurrences of each element in nums1.
  3. Initialize an empty list result.
  4. For each element x in nums2:
  5. If freq.get(x) > 0:
  6. Append x to result.
  7. Decrement freq[x] by 1.
  8. Return result.

Hash Map Frequency Counting (O(M + N) Time, O(min(M, N)) Space)

2 of 2 questions left today
Step 1 / 6
Trace timeline17% explored
Current operationSTEP 1 OF 6
Precomputation takes O(M) time
Visual state
Values and pointers at this exact step
hashmap
Input array
S
1: 2
2: 2
0
↑ map
1
Hash map state
2 stored entries
key
1
maps to index
2
key
2
maps to index
2
Each key stores remaining available matches.
Variables at this step
map state
1: 2, 2: 2
result
[]
Check / comparison
Build frequency map for nums1: { 1: 2, 2: 2 }
Decision / next transition
Each key stores remaining available matches.
Why this step matters

Precomputation takes O(M) time.

Step 1 / 6
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <unordered_map>
3#include <vector>
4using namespace std;
5
6// Optimal: Frequency Map for O(N + M) time and O(min(N, M)) space
7vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
8 // Ensure nums1 is smaller to minimize map size
9 if (nums1.size() > nums2.size()) {
10 return intersect(nums2, nums1);
11 }
12
13 unordered_map<int, int> freq;
14 for (int num : nums1) {
15 freq[num]++;
16 }
17
18 vector<int> result;
19 for (int num : nums2) {
20 if (freq[num] > 0) {
21 result.push_back(num);
22 freq[num]--;
23 }
24 }
25
26 return result;
27}
28
29int main() {
30 vector<int> nums1 = {1, 2, 2, 1};
31 vector<int> nums2 = {2, 2};
32 vector<int> res = intersect(nums1, nums2);
33
34 cout << "Output: [";
35 for (size_t i = 0; i < res.size(); i++) {
36 cout << res[i] << (i + 1 < res.size() ? ", " : "");
37 }
38 cout << "]" << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N) — Time complexity for Approach 3: Optimal — Frequency Hash Map (Linear Time).
  • Space complexity: O(1) — Space complexity for Approach 3: Optimal — Frequency Hash Map (Linear Time).

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force (Visited Array)O(N * M)O(M)Easy to grasp, no hash map overhead.Baseline only.
2.Sort + Two PointersO(N log N + M log M)O(1) auxiliaryIdeal when arrays are already sorted; runs in O(N + M) without extra map space.Essential follow-up solution when data is pre-sorted or stream-based.
3.Frequency Hash MapOptimalO(N + M)O(min(N, M))Optimal linear time, works on unsorted inputs directly.Top choice in interviews.

Common Pitfalls & Crucial Edge Cases

Off-by-One Errors

Incorrect boundary indexing when adjusting pointers or array slices.

Integer Overflow

Using 32-bit signed integer types when accumulative operations exceed 231 - 1 in C++/Java.

Unnecessary Memory Allocation

Allocating large auxiliary arrays or objects inside inner loops causing GC overhead.

Failing to Reset Loop State

Not re-initializing state variables or counters between iterations or subproblems.

Crucial Edge Cases to Validate:

  • Unequal Duplicate Frequencies — Input: nums1 = [1, 2, 2, 2, 3], nums2 = [2, 2], Expected: [2, 2] — Number 2 appears 3 times in nums1 and 2 times in nums2 -> output should contain 2 exactly min(3, 2) = 2 times.
  • Completely Disjoint Arrays — Input: nums1 = [1, 2, 3], nums2 = [4, 5, 6], Expected: [] — No common elements exist; return an empty array.
  • Identical Arrays with Duplicates — Input: nums1 = [7, 7, 7], nums2 = [7, 7, 7], Expected: [7, 7, 7] — All 3 occurrences of 7 must appear in the result.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Follow-up 1: Already Sorted — If the interviewer asks: 'What if the given array is already sorted? How would you optimize your algorithm?' Answer: 'Use Two Pointers! It achieves O(N + M) time and O(1) extra space without any hash maps.'
  2. Follow-up 2: Memory Constraint (N << M) — If nums1 is very small compared to nums2: 'Build the hash map on nums1 to use O(nums1.length) space, or sort nums1 and binary search each element in nums2.'
  3. Follow-up 3: Disk / Stream — If elements of nums2 are stored on disk and memory is limited: 'Load nums1 into a hash map in memory, then stream chunks of nums2 from disk sequentially.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the optimal time and auxiliary space complexity for Intersection of Two Arrays II?

2.Why is the brute force approach suboptimal for large inputs in Intersection of Two Arrays II?

3.Which data structure or technique enables the optimal solution for Intersection of Two Arrays II?

Back to DSA Sheet