Intersection of Two Arrays II

📋

Intersection of Two Arrays II

Edge cases:

</>

IDE

def intersect(nums1: list[int], nums2: list[int]) -> list[int]:public int[] intersect(int[] nums1, int[] nums2)vector<int> intersect(vector<int> nums1, vector<int> nums2)function intersect(nums1, nums2)

def intersect(nums1, nums2):
    # Write your solution here
    pass

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // Write your solution here
        return new int[0];
    }
}

#include <vector>
using namespace std;

vector<int> intersect(vector<int> nums1, vector<int> nums2) {
    // Write your solution here
    return {};
}

function intersect(nums1, nums2) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [2]Not counting duplicates properly; only one occurrence returned instead of two.✅ Decrement frequency count after each match and add element to result as many times as minimum frequency.

Wrong: [5, 5, 5]Returning all duplicates from one array ignoring the other array's counts.✅ Use frequency map to limit duplicates to minimum count in both arrays.

Wrong: [2, 2, 2]Greedy approach taking all duplicates from one array without limiting by the other array.✅ Limit duplicates by minimum frequency in both arrays using frequency map decrement.

Wrong: [1, 1, 1, 1]Confusing 0/1 occurrence with unbounded duplicates, returning more than minimum count.✅ Decrement frequency map count after each match to enforce correct counts.

Wrong: [1, 2, 3]Returning non-empty intersection when arrays have no common elements.✅ Check frequency map keys properly and return empty list if no matches.

✓

Test Cases

Try testing your solution with empty and single element arrays to catch base case bugs.

Consider tricky cases where duplicates and frequency counts cause wrong answers.

Think about the time complexity of your approach and how it scales with large inputs.

t1_01basic

Input{"nums1":[1,2,2,1],"nums2":[2,2]}

Expected[2,2]

⏱ Performance - must finish in 2000ms

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

💡 Use a frequency map to count elements in one array.

💡 Decrement counts when matching elements are found in the other array.

💡 Return all elements that appear in both arrays as many times as they appear in both.

Why it failed: Output missing duplicates or incorrect counts due to not decrementing frequency after match. Fix by decrementing frequency map count after adding element to result.

✓ Correctly counts and returns all common elements with duplicates.

t1_02basic

Input{"nums1":[4,9,5],"nums2":[9,4,9,8,4]}

Expected[4,9]

⏱ Performance - must finish in 2000ms

Intersection includes one '4' and one '9' as both appear in both arrays.

💡 Check frequency of elements in the smaller array first.

💡 Match elements from the other array and reduce counts accordingly.

💡 Return all matched elements respecting their minimum frequency in both arrays.

Why it failed: Incorrect output due to ignoring frequency or returning duplicates incorrectly. Fix by using frequency map and decrementing counts properly.

✓ Correctly handles intersection with different sized arrays and duplicates.

t2_01edge

Input{"nums1":[],"nums2":[1,2,3]}

Expected[]

⏱ Performance - must finish in 2000ms

Empty nums1 means no intersection possible.

💡 Consider what happens if one input array is empty.

💡 Intersection with empty array should always be empty.

💡 Return empty list immediately if either array is empty.

Why it failed: Fails to handle empty input arrays, returning non-empty or error. Fix by checking for empty arrays and returning empty list early.

✓ Correctly returns empty intersection when one array is empty.

t2_02edge

Input{"nums1":[7],"nums2":[7]}

Expected[7]

⏱ Performance - must finish in 2000ms

Single element arrays with the same element intersect at that element.

💡 Test with smallest non-empty arrays.

💡 Check if single elements match and return accordingly.

💡 Return single element if it appears in both arrays.

Why it failed: Fails single element intersection by returning empty or incorrect result. Fix by handling single element arrays correctly.

✓ Correctly returns intersection for single element arrays.

t2_03edge

Input{"nums1":[5,5,5],"nums2":[5,5]}

Expected[5,5]

⏱ Performance - must finish in 2000ms

Intersection includes two '5's, the minimum count in both arrays.

💡 Check frequency counts carefully when all elements are identical.

💡 Return the minimum count of duplicates present in both arrays.

💡 Use frequency map decrement to avoid overcounting duplicates.

Why it failed: Incorrectly returns all duplicates from one array ignoring the other. Fix by taking minimum frequency counts from both arrays.

✓ Correctly returns intersection with duplicates respecting minimum counts.

t2_04edge

Input{"nums1":[1000000000],"nums2":[1000000000]}

Expected[1000000000]

⏱ Performance - must finish in 2000ms

Handles large numbers correctly in intersection.

💡 Check that large values are handled without overflow.

💡 Frequency map keys should support large integers.

💡 Return intersection correctly even with large values.

Why it failed: Fails due to integer overflow or incorrect key handling. Fix by using appropriate data types for keys.

✓ Correctly handles large integer values.

t3_01corner

Input{"nums1":[1,2,2,1],"nums2":[2]}

Expected[2]

⏱ Performance - must finish in 2000ms

Intersection includes only one '2' because nums2 has one '2'.

💡 Beware of greedy approach that takes all duplicates from one array.

💡 Intersection count is limited by minimum frequency in both arrays.

💡 Use frequency map to limit duplicates to minimum count.

Why it failed: Greedy approach returns all duplicates from nums1 ignoring nums2 counts. Fix by limiting duplicates to minimum frequency in both arrays.

✓ Correctly limits duplicates to minimum frequency in both arrays.

t3_02corner

Input{"nums1":[1,1,1],"nums2":[1,1,1,1]}

Expected[1,1,1]

⏱ Performance - must finish in 2000ms

Intersection includes three '1's, limited by nums1 count.

💡 Check that intersection respects 0/1 occurrence per element per array.

💡 Do not treat problem as unbounded duplicates from either array.

💡 Use frequency map decrement to enforce 0/1 per element per occurrence.

Why it failed: Confuses 0/1 occurrence with unbounded duplicates, returning more than minimum count. Fix by decrementing frequency map after each match.

✓ Correctly enforces 0/1 occurrence per element per array.

t3_03corner

Input{"nums1":[1,2,3,4],"nums2":[5,6,7,8]}

Expected[]

⏱ Performance - must finish in 2000ms

No common elements, intersection is empty.

💡 Check for no overlap between arrays.

💡 Return empty list if no elements match.

💡 Verify frequency map keys against other array elements.

Why it failed: Returns non-empty intersection when arrays have no common elements. Fix by checking frequency map keys properly.

✓ Correctly returns empty intersection for disjoint arrays.

t4_01performance

Input{"nums1":[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99],"nums2":[99,98,97,96,95,94,93,92,91,90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,0]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100, O(m+n) expected with hash map frequency counting to complete within 2s.

💡 Use hash map frequency counting for O(m+n) time complexity.

💡 Avoid nested loops which cause O(m*n) time and TLE.

💡 Efficiently decrement counts to avoid extra overhead.

Why it failed: TLE due to nested loops or inefficient frequency counting. Fix by using hash map frequency counting with O(m+n) complexity.

✓ Algorithm runs within time limit using O(m+n) frequency counting.

Practice

1. Given the following code, what is the return value when the input string is "aabc"?

easy

A. 2

B. 1

C. -1

D. 0

Solution

1. Step 1: Trace frequency and first_index dictionaries

   For "aabc": freq={'a':2, 'b':1, 'c':1}, first_index={'a':0, 'b':2, 'c':3}

2. Step 2: Find minimum index with frequency 1

   Characters with count 1 are 'b' at index 2 and 'c' at index 3; minimum is 2.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   First unique char is 'b' at index 2 [OK]

Hint: Check frequency and first occurrence carefully [OK]

Common Mistakes:

• Returning character instead of index
• Off-by-one index errors
• Ignoring multiple unique chars

2. Consider the following Python code implementing the optimal bucket sort approach for top K frequent elements. What is the value of res just before the function returns when called with nums = [1,2,2,3] and k = 2?

easy

A. [1, 2]

B. [2, 1]

C. [2, 3]

D. [3, 2]

Solution

1. Step 1: Calculate frequency map for nums=[1,2,2,3]

   freq = {1:1, 2:2, 3:1}, max_freq = 2

2. Step 2: Fill buckets and collect top k=2 elements

   buckets = [[], [1,3], [2]]; iterate from freq=2 down: add 2, then freq=1 add 1; res = [2,1]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Order depends on bucket insertion; here 2 appears before 1 [OK]

Hint: Trace buckets from highest frequency down [OK]

Common Mistakes:

• Confusing order of elements in buckets
• Assuming sorted order inside buckets
• Off-by-one in frequency indexing

3. Consider the following Python code implementing the Two Sum problem using sorting and two pointers. What is the output when calling two_sum([3, 2, 4], 6)?

easy

A. [1, 0]

B. [0, 2]

C. [2, 1]

D. [1, 2]

Solution

1. Step 1: Sort nums with indices

   nums_with_index = [(0,3), (1,2), (2,4)] sorted by value -> [(1,2), (0,3), (2,4)]

2. Step 2: Two pointers check sums

   left=0 (value=2), right=2 (value=4), sum=6 equals target -> return indices [1, 2]

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sum found at indices 1 and 2 matching target 6 [OK]

Hint: Sort with indices, then two pointers find correct pair [OK]

Common Mistakes:

• Returning values instead of indices
• Mixing up left and right indices
• Off-by-one errors in pointer movement

4. Suppose the problem changes: now you want to detect if any number appears at least twice, but the array is extremely large and cannot fit into memory. Which approach is best suited to handle this scenario?

hard

A. Sort the array externally (external sort) and then scan for duplicates in a streaming fashion.

B. Use a hash set in memory as before, but process the array in chunks and merge results.

C. Use a bloom filter to probabilistically detect duplicates with limited memory.

D. Use nested loops on the entire array since it requires no extra space.

Solution

1. Step 1: Understand memory constraints

   The array is too large to fit in memory, so hash sets or sorting in memory are infeasible.

2. Step 2: Evaluate options

   External sorting is possible and practical for large data sets that cannot fit into memory. Bloom filters provide probabilistic detection but can yield false positives, which may not be acceptable depending on requirements. Nested loops are impractical due to O(n²) time complexity.

3. Step 3: Choose external sorting

   External sorting allows sorting data on disk and then scanning sequentially for duplicates, which is efficient and exact.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   External sorting handles large data sets with limited memory and provides exact duplicate detection [OK]

Hint: External sorting enables exact duplicate detection on large data sets [OK]

Common Mistakes:

• Assuming hash sets can handle huge data
• Ignoring external sorting costs
• Choosing nested loops despite inefficiency
• Overlooking bloom filter false positives

5. Suppose the array nums can contain negative numbers and you want to count subarrays summing to k. Which modification to the prefix sum + hash map approach correctly handles this scenario?

hard

A. Keep the prefix sum + hash map approach unchanged, as it already handles negative numbers correctly.

B. Sort the array first, then use two pointers to find subarrays summing to k.

C. Use a sliding window approach since negative numbers allow shrinking the window arbitrarily.

D. Use nested loops to check all subarrays because prefix sums fail with negative numbers.

Solution

1. Step 1: Understand sliding window limitations

   Sliding window fails with negative numbers because sums can decrease unpredictably.

2. Step 2: Verify prefix sum + hash map suitability

   Prefix sums with hash map count frequencies and handle negative numbers naturally without sorting.

3. Step 3: Evaluate other options

   Sorting breaks subarray continuity; nested loops are correct but inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Prefix sum + hash map is the robust solution for negatives [OK]

Hint: Prefix sums + hash map handles negatives; sliding window does not [OK]

Common Mistakes:

• Trying sliding window with negatives
• Sorting array breaks subarray continuity
• Assuming prefix sums fail with negatives