Intersection of Two Arrays II

🎯

Intersection of Two Arrays II

easyHASH_MAPAmazonFacebookGoogle

Imagine you have two lists of items purchased by two customers, and you want to find which items they both bought, including duplicates.

💡 This problem is about finding common elements between two lists, including duplicates. Beginners often struggle because they might only find unique intersections or forget to account for the frequency of elements.

📋

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.

1 ≤ nums1.length, nums2.length ≤ 10^50 ≤ nums1[i], nums2[i] ≤ 10^9

💡

Example

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

Output[2,2]

Both arrays have two '2's, so the intersection includes two '2's.

Input"nums1 = [4,9,5], nums2 = [9,4,9,8,4]"

Output[4,9]

The intersection includes one '4' and one '9' because those appear in both arrays.

• One or both arrays empty → output is empty array
• Arrays with no common elements → output is empty array
• Arrays where all elements are the same → output is the smaller array
• Arrays with large numbers and duplicates → output includes correct counts

⚠️

Common Mistakes

Not accounting for duplicates properly

Output misses repeated elements or includes too many

✅ Use frequency counts or remove matched elements carefully

Modifying input arrays directly

Unexpected side effects or errors in later code

✅ Work on copies of arrays when removing elements

Using 'in' or 'contains' without considering performance

Code runs slowly on large inputs

✅ Use hash maps for O(1) lookups instead of linear searches

Not sorting arrays before two-pointer approach

Incorrect results or infinite loops

✅ Always sort arrays before applying two-pointer technique

Returning intersection in wrong order

Fails tests expecting any order or specific order

✅ Clarify output order requirements; usually any order is acceptable

🧠

Brute Force (Nested Loops)

💡 This approach exists to build intuition by directly comparing elements, even though it's inefficient. It helps beginners understand the problem deeply before optimizing.

Intuition

Check every element in the first array against every element in the second array to find matches, removing matched elements to avoid duplicates.

Algorithm

1. Initialize an empty list to store the intersection.
2. For each element in the first array, iterate through the second array.
3. If a matching element is found in the second array, add it to the intersection and remove it from the second array to avoid reuse.
4. Return the intersection list.

💡 The nested loops make it easy to understand but hard to scale; removing matched elements ensures duplicates are counted correctly.

</>

Code

def intersect(nums1, nums2):
    intersection = []
    nums2_copy = nums2.copy()
    for num in nums1:
        if num in nums2_copy:
            intersection.append(num)
            nums2_copy.remove(num)
    return intersection

# Driver code
if __name__ == '__main__':
    print(intersect([1,2,2,1], [2,2]))  # Output: [2,2]

Line Notes

intersection = []Initialize list to store common elements

nums2_copy = nums2.copy()Copy nums2 to safely remove elements without affecting original

for num in nums1:Iterate over each element in nums1 to check for matches

if num in nums2_copy:Check if current element exists in nums2_copy

intersection.append(num)Add matched element to result

nums2_copy.remove(num)Remove matched element to avoid counting duplicates multiple times

import java.util.*;
public class Solution {
    public static int[] intersect(int[] nums1, int[] nums2) {
        List<Integer> intersection = new ArrayList<>();
        List<Integer> nums2List = new ArrayList<>();
        for (int num : nums2) nums2List.add(num);
        for (int num : nums1) {
            if (nums2List.contains(num)) {
                intersection.add(num);
                nums2List.remove(Integer.valueOf(num));
            }
        }
        int[] result = new int[intersection.size()];
        for (int i = 0; i < intersection.size(); i++) result[i] = intersection.get(i);
        return result;
    }

    public static void main(String[] args) {
        int[] res = intersect(new int[]{1,2,2,1}, new int[]{2,2});
        System.out.println(Arrays.toString(res)); // Output: [2, 2]
    }
}

Line Notes

List<Integer> intersection = new ArrayList<>();Store intersection elements dynamically

List<Integer> nums2List = new ArrayList<>();Convert nums2 array to list for easy removal

for (int num : nums2) nums2List.add(num);Populate list from nums2

if (nums2List.contains(num)) {Check if nums2List contains current num

intersection.add(num);Add matched element to intersection

nums2List.remove(Integer.valueOf(num));Remove matched element to avoid duplicates

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    vector<int> intersection;
    vector<int> nums2_copy = nums2;
    for (int num : nums1) {
        auto it = find(nums2_copy.begin(), nums2_copy.end(), num);
        if (it != nums2_copy.end()) {
            intersection.push_back(num);
            nums2_copy.erase(it);
        }
    }
    return intersection;
}

int main() {
    vector<int> nums1 = {1,2,2,1};
    vector<int> nums2 = {2,2};
    vector<int> res = intersect(nums1, nums2);
    for (int num : res) cout << num << ' '; // Output: 2 2
    cout << endl;
    return 0;
}

Line Notes

vector<int> intersection;Initialize vector to store intersection

vector<int> nums2_copy = nums2;Copy nums2 to safely remove elements

for (int num : nums1) {Iterate over nums1 elements

auto it = find(nums2_copy.begin(), nums2_copy.end(), num);Search for num in nums2_copy

if (it != nums2_copy.end()) {Check if found

intersection.push_back(num);Add matched element

nums2_copy.erase(it);Remove matched element to avoid duplicates

function intersect(nums1, nums2) {
    const intersection = [];
    const nums2Copy = nums2.slice();
    for (const num of nums1) {
        const index = nums2Copy.indexOf(num);
        if (index !== -1) {
            intersection.push(num);
            nums2Copy.splice(index, 1);
        }
    }
    return intersection;
}

// Test
console.log(intersect([1,2,2,1], [2,2])); // Output: [2, 2]

Line Notes

const intersection = [];Initialize array to store intersection

const nums2Copy = nums2.slice();Copy nums2 to safely remove elements

for (const num of nums1) {Iterate over nums1 elements

const index = nums2Copy.indexOf(num);Find index of num in nums2Copy

if (index !== -1) {Check if num exists in nums2Copy

intersection.push(num);Add matched element

nums2Copy.splice(index, 1);Remove matched element to avoid duplicates

⏱

Complexity

TimeO(m * n)

SpaceO(n)

For each element in nums1 (m), we search nums2 (n) for a match, removing matched elements which is O(n) per removal.

💡 If both arrays have 100 elements, this means up to 10,000 comparisons, which is inefficient for large inputs.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem before optimizing.

🧠

Hash Map Frequency Counting

💡 This approach uses a hash map to count frequencies, which is a common and efficient technique to handle duplicates and membership checks.

Intuition

Count the frequency of each element in one array, then iterate over the second array to find common elements by checking and decrementing counts.

Algorithm

1. Create a hash map to store frequencies of elements in nums1.
2. Iterate over nums1 and increment counts in the hash map.
3. Initialize an empty list for the intersection.
4. Iterate over nums2, and for each element, check if it exists in the hash map with count > 0.
5. If yes, append the element to the intersection and decrement its count in the hash map.
6. Return the intersection list.

💡 Using a hash map avoids nested loops and efficiently tracks how many times each element can be matched.

</>

Code

def intersect(nums1, nums2):
    counts = {}
    for num in nums1:
        counts[num] = counts.get(num, 0) + 1
    intersection = []
    for num in nums2:
        if counts.get(num, 0) > 0:
            intersection.append(num)
            counts[num] -= 1
    return intersection

# Driver code
if __name__ == '__main__':
    print(intersect([1,2,2,1], [2,2]))  # Output: [2, 2]

Line Notes

counts = {}Initialize dictionary to count frequencies

for num in nums1:Count each element's frequency in nums1

counts[num] = counts.get(num, 0) + 1Increment count or initialize to 1

intersection = []Prepare list to store intersection

for num in nums2:Check each element in nums2 against counts

if counts.get(num, 0) > 0:Only add if element is still available

intersection.append(num)Add matched element

counts[num] -= 1Decrement count to avoid overcounting

import java.util.*;
public class Solution {
    public static int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int num : nums1) counts.put(num, counts.getOrDefault(num, 0) + 1);
        List<Integer> intersection = new ArrayList<>();
        for (int num : nums2) {
            if (counts.getOrDefault(num, 0) > 0) {
                intersection.add(num);
                counts.put(num, counts.get(num) - 1);
            }
        }
        int[] result = new int[intersection.size()];
        for (int i = 0; i < intersection.size(); i++) result[i] = intersection.get(i);
        return result;
    }

    public static void main(String[] args) {
        int[] res = intersect(new int[]{1,2,2,1}, new int[]{2,2});
        System.out.println(Arrays.toString(res)); // Output: [2, 2]
    }
}

Line Notes

Map<Integer, Integer> counts = new HashMap<>();Create map to count frequencies

for (int num : nums1) counts.put(num, counts.getOrDefault(num, 0) + 1);Count frequencies in nums1

List<Integer> intersection = new ArrayList<>();List to store intersection

if (counts.getOrDefault(num, 0) > 0) {Check if element available to match

intersection.add(num);Add matched element

counts.put(num, counts.get(num) - 1);Decrement count to avoid duplicates

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> counts;
    for (int num : nums1) counts[num]++;
    vector<int> intersection;
    for (int num : nums2) {
        if (counts[num] > 0) {
            intersection.push_back(num);
            counts[num]--;
        }
    }
    return intersection;
}

int main() {
    vector<int> nums1 = {1,2,2,1};
    vector<int> nums2 = {2,2};
    vector<int> res = intersect(nums1, nums2);
    for (int num : res) cout << num << ' '; // Output: 2 2
    cout << endl;
    return 0;
}

Line Notes

unordered_map<int, int> counts;Hash map to store frequencies

for (int num : nums1) counts[num]++;Count frequencies in nums1

vector<int> intersection;Vector to store intersection

if (counts[num] > 0) {Check if element available to match

intersection.push_back(num);Add matched element

counts[num]--;Decrement count to avoid duplicates

function intersect(nums1, nums2) {
    const counts = new Map();
    for (const num of nums1) {
        counts.set(num, (counts.get(num) || 0) + 1);
    }
    const intersection = [];
    for (const num of nums2) {
        if ((counts.get(num) || 0) > 0) {
            intersection.push(num);
            counts.set(num, counts.get(num) - 1);
        }
    }
    return intersection;
}

// Test
console.log(intersect([1,2,2,1], [2,2])); // Output: [2, 2]

Line Notes

const counts = new Map();Initialize map to count frequencies

for (const num of nums1) {Count frequencies in nums1

counts.set(num, (counts.get(num) || 0) + 1);Increment count or initialize to 1

const intersection = [];Array to store intersection

if ((counts.get(num) || 0) > 0) {Check if element available to match

intersection.push(num);Add matched element

counts.set(num, counts.get(num) - 1);Decrement count to avoid duplicates

⏱

Complexity

TimeO(m + n)

SpaceO(min(m, n))

Counting frequencies takes O(m), iterating nums2 takes O(n). Space depends on smaller array for frequency map.

💡 For arrays of size 100, this means about 200 operations, much faster than brute force.

Interview Verdict: Accepted / Optimal for most cases

This approach is efficient and commonly accepted in interviews.

🧠

Sorting + Two Pointers

💡 This approach leverages sorting and two pointers to find intersections without extra space for hash maps, useful when memory is constrained.

Intuition

Sort both arrays, then use two pointers to traverse them simultaneously, adding common elements to the result.

Algorithm

1. Sort both nums1 and nums2.
2. Initialize two pointers at the start of each array.
3. While both pointers are within array bounds, compare elements.
4. If elements are equal, add to intersection and move both pointers.
5. If element in nums1 is smaller, move pointer in nums1.
6. If element in nums2 is smaller, move pointer in nums2.
7. Return the intersection list.

💡 Sorting enables linear traversal to find matches efficiently without extra space.

</>

Code

def intersect(nums1, nums2):
    nums1.sort()
    nums2.sort()
    i, j = 0, 0
    intersection = []
    while i < len(nums1) and j < len(nums2):
        if nums1[i] == nums2[j]:
            intersection.append(nums1[i])
            i += 1
            j += 1
        elif nums1[i] < nums2[j]:
            i += 1
        else:
            j += 1
    return intersection

# Driver code
if __name__ == '__main__':
    print(intersect([1,2,2,1], [2,2]))  # Output: [2, 2]

Line Notes

nums1.sort()Sort first array to enable two-pointer traversal

nums2.sort()Sort second array similarly

i, j = 0, 0Initialize pointers for both arrays

while i < len(nums1) and j < len(nums2):Traverse both arrays until one ends

if nums1[i] == nums2[j]:Found common element

intersection.append(nums1[i])Add to result

i += 1; j += 1Move both pointers forward

elif nums1[i] < nums2[j]:Advance pointer in nums1 if smaller

else: j += 1Advance pointer in nums2 if smaller

import java.util.*;
public class Solution {
    public static int[] intersect(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> intersection = new ArrayList<>();
        int i = 0, j = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] == nums2[j]) {
                intersection.add(nums1[i]);
                i++;
                j++;
            } else if (nums1[i] < nums2[j]) {
                i++;
            } else {
                j++;
            }
        }
        int[] result = new int[intersection.size()];
        for (int k = 0; k < intersection.size(); k++) result[k] = intersection.get(k);
        return result;
    }

    public static void main(String[] args) {
        int[] res = intersect(new int[]{1,2,2,1}, new int[]{2,2});
        System.out.println(Arrays.toString(res)); // Output: [2, 2]
    }
}

Line Notes

Arrays.sort(nums1);Sort first array

Arrays.sort(nums2);Sort second array

int i = 0, j = 0;Initialize pointers

while (i < nums1.length && j < nums2.length) {Traverse arrays simultaneously

if (nums1[i] == nums2[j]) {Check for common element

intersection.add(nums1[i]);Add to intersection

i++; j++;Move both pointers forward

else if (nums1[i] < nums2[j]) {Advance pointer in nums1 if smaller

else { j++; }Advance pointer in nums2 if smaller

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    vector<int> intersection;
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] == nums2[j]) {
            intersection.push_back(nums1[i]);
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return intersection;
}

int main() {
    vector<int> nums1 = {1,2,2,1};
    vector<int> nums2 = {2,2};
    vector<int> res = intersect(nums1, nums2);
    for (int num : res) cout << num << ' '; // Output: 2 2
    cout << endl;
    return 0;
}

Line Notes

sort(nums1.begin(), nums1.end());Sort first array

sort(nums2.begin(), nums2.end());Sort second array

int i = 0, j = 0;Initialize pointers

while (i < nums1.size() && j < nums2.size()) {Traverse arrays simultaneously

if (nums1[i] == nums2[j]) {Check for common element

intersection.push_back(nums1[i]);Add to intersection

i++; j++;Move both pointers forward

else if (nums1[i] < nums2[j]) {Advance pointer in nums1 if smaller

else { j++; }Advance pointer in nums2 if smaller

function intersect(nums1, nums2) {
    nums1.sort((a,b) => a - b);
    nums2.sort((a,b) => a - b);
    const intersection = [];
    let i = 0, j = 0;
    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] === nums2[j]) {
            intersection.push(nums1[i]);
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    return intersection;
}

// Test
console.log(intersect([1,2,2,1], [2,2])); // Output: [2, 2]

Line Notes

nums1.sort((a,b) => a - b);Sort first array numerically

nums2.sort((a,b) => a - b);Sort second array numerically

let i = 0, j = 0;Initialize pointers

while (i < nums1.length && j < nums2.length) {Traverse arrays simultaneously

if (nums1[i] === nums2[j]) {Check for common element

intersection.push(nums1[i]);Add to intersection

i++; j++;Move both pointers forward

else if (nums1[i] < nums2[j]) {Advance pointer in nums1 if smaller

else { j++; }Advance pointer in nums2 if smaller

⏱

Complexity

TimeO(m log m + n log n)

SpaceO(min(m, n))

Sorting takes O(m log m) and O(n log n), then linear traversal is O(m + n). Space for intersection depends on smaller array.

💡 For arrays of size 100, sorting takes about 700 operations each, plus 200 for traversal, still efficient.

Interview Verdict: Accepted / Good alternative

This approach is efficient and useful when hash maps are not preferred or allowed.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the hash map approach in 95% of interviews for best balance of speed and simplicity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(m * n)	O(n)	No	N/A	Mention only - never code
2. Hash Map Frequency Counting	O(m + n)	O(min(m, n))	No	N/A	Code this approach
3. Sorting + Two Pointers	O(m log m + n log n)	O(min(m, n))	No	N/A	Good alternative if hash maps disallowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare for common interview questions.

How to Present

Step 1: Clarify the problem and ask about duplicates and output order.Step 2: Describe the brute force approach to show understanding.Step 3: Introduce the hash map frequency counting as an optimization.Step 4: Mention sorting + two pointers as an alternative.Step 5: Code the chosen approach and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Interviewer tests your problem understanding, ability to optimize, handle duplicates correctly, and write clean code.

Common Follow-ups

• What if the arrays are already sorted? → Use two pointers approach.
• What if nums1 is much smaller than nums2? → Build frequency map on smaller array to save space.

💡 These follow-ups test your adaptability and understanding of trade-offs in different scenarios.

🔍

Pattern Recognition

When to Use

1) Asked to find common elements between two arrays; 2) Duplicates matter; 3) Order of output not strict; 4) Efficient membership checks needed.

Signature Phrases

return an array of their intersectioneach element must appear as many times as it shows in both arrays

NOT This Pattern When

Problems asking for unique intersections only or subsets without duplicates.

Similar Problems

Intersection of Two Arrays - simpler version without duplicatesTwo Sum - uses hash maps for membership and frequencyFind All Duplicates in an Array - frequency counting pattern

Practice

1. You are given a binary array and need to find the length of the longest contiguous subarray with an equal number of 0s and 1s. Which algorithmic approach guarantees an optimal O(n) time solution?

easy

A. Brute force nested loops checking all subarrays for equal 0s and 1s

B. Prefix sum combined with a hash map to track first occurrences of prefix sums

C. Dynamic programming storing counts of 0s and 1s separately for all subarrays

D. Greedy approach expanding subarrays while counts of 0s and 1s remain equal

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest contiguous subarray with equal 0s and 1s efficiently.

2. Step 2: Identify algorithmic pattern

   Using prefix sums transformed by treating 0 as -1, and a hash map to store earliest prefix sum indices, allows O(n) time detection of subarrays with zero sum difference.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Prefix sum + hash map is classic for equal 0/1 subarray [OK]

Hint: Prefix sums + hash map track equal 0s and 1s efficiently [OK]

Common Mistakes:

• Thinking greedy can find longest equal 0/1 subarray
• Using DP that tracks counts separately is inefficient
• Brute force is correct but not optimal

2. What is the worst-case time complexity of the optimal hash set approach to detect duplicates in an array of length n?

medium

A. O(n) average, but O(n²) worst-case if many hash collisions occur

B. O(n log n) due to sorting inside the hash set

C. O(n²) because each insertion checks all existing elements

D. O(n) guaranteed due to constant-time hash set operations

Solution

1. Step 1: Understand average case

   Hash set operations (insert, lookup) are O(1) average, so iterating n elements is O(n) average.

2. Step 2: Consider worst-case scenario

   If many hash collisions occur, hash set operations degrade to O(n) each, making total O(n²) in worst case.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash collisions cause worst-case quadratic time, though rare in practice [OK]

Hint: Hash collisions can degrade hash set to O(n²) worst-case [OK]

Common Mistakes:

• Assuming guaranteed O(n) time
• Confusing sorting complexity with hashing
• Thinking insertion checks all elements explicitly

3. What is the time complexity of the optimal prefix sum + hash map solution for checking if a continuous subarray sum is a multiple of k, given an input array of length n and integer k?

medium

A. O(n * k)

B. O(n^2)

C. O(n)

D. O(k)

Solution

1. Step 1: Analyze the main loop over n elements

   The algorithm iterates once over the array, performing O(1) operations per element.

2. Step 2: Consider hash map operations and modulo computations

   Hash map lookups and insertions are average O(1), modulo operations are O(1), so total is O(n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Single pass with constant-time map ops -> O(n) [OK]

Hint: Hash map lookups are O(1) average, so linear time [OK]

Common Mistakes:

• Confusing with brute force O(n^2)
• Assuming modulo k affects complexity multiplicatively
• Thinking hash map size depends on k linearly

4. What is the time and space complexity of the optimal solution using prefix sums and a hash map (or array) for the longest subarray with sum divisible by k problem, given an input array of length n and integer k?

medium

A. Time: O(n log n), Space: O(n)

B. Time: O(n), Space: O(k)

C. Time: O(n * k), Space: O(n)

D. Time: O(n^2), Space: O(1)

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates once over the array (length n), performing O(1) operations per element, so time is O(n).

2. Step 2: Analyze space complexity

   We store earliest indices for each remainder modulo k, so space is O(k), independent of n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Linear time and space proportional to k [OK]

Hint: Prefix sums + hash map -> O(n) time, O(k) space [OK]

Common Mistakes:

• Confusing nested loops complexity with prefix sum approach
• Assuming space is O(n) due to prefix sums stored
• Thinking time is O(n*k) due to modulo operations

5. The following code attempts to count subarrays summing to k. Which line contains a subtle bug that causes incorrect counts for subarrays starting at index 0?

medium

A. Line 7: if prefix_sum - k in prefix_counts (wrong condition)

B. Line 5: prefix_sum += num (incorrect accumulation)

C. Line 3: prefix_counts = {} (missing initialization with {0:1})

D. Line 9: prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1 (incorrect update)

Solution

1. Step 1: Identify initialization of prefix_counts

   prefix_counts must start with {0:1} to count subarrays starting at index 0 correctly.

2. Step 2: Check other lines

   Accumulation, condition, and update lines are correct; only initialization is missing the base case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing {0:1} causes missed counts for subarrays from start [OK]

Hint: Always initialize prefix_counts with {0:1} to handle subarrays from index 0 [OK]

Common Mistakes:

• Not initializing prefix_counts with {0:1}
• Misplacing prefix_sum updates
• Incorrect condition checks