Intersection of Two Arrays II - Practice Coding Problems

Intersection of Two Arrays II - 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.

The intersection should preserve the frequency of elements - if an element appears 3 times in both arrays, it should appear 3 times in the result.

Input & Output

Example 1 — Basic Case

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

› Output: [2,1,2]

💡 Note: Element 2 appears twice in both arrays, so it appears twice in result. Element 1 appears twice in nums1 but only once in nums2, so it appears once in result.

Example 2 — Different Frequencies

$ Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

› Output: [4,9]

💡 Note: Element 4 appears once in nums1 and twice in nums2, so it appears once in result. Element 9 appears once in nums1 and twice in nums2, so it appears once in result.

Example 3 — No Common Elements

$ Input: nums1 = [1,2,3], nums2 = [4,5,6]

› Output: []

💡 Note: No elements are common between the two arrays, so the intersection is empty.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

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

Find Intersection

Match elements considering their frequencies

Result

Output: [2,1,2] (preserving frequencies)

Key Takeaway

🎯 Key Insight: Use frequency counting to handle duplicates - take minimum occurrence count from both arrays

Asked in

G Google 45 a Amazon 38 f Facebook 32 M Microsoft 28

The key insight is to track frequency of elements to handle duplicates correctly. Best approach is Hash Map frequency counting with Time: O(n+m), Space: O(n) for optimal balance of time and space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Nested Loops	O(n×m)	O(1)	For each element in nums1, search through nums2 to find matches
Hash Map Frequency Count	O(n+m)	O(n)	Count frequencies in one array, then check the other array against counts
Two Pointers (Sort First)	O(n log n + m log m)	O(1)	Sort both arrays then use two pointers to find intersection efficiently

Brute Force with Nested Loops — Algorithm Steps

Iterate through each element in nums1
For each element, search through nums2 for matches
When match found, add to result and mark as used

Visualization

Tap to expand

Step-by-Step Walkthrough

Check First Element

Look for nums1[0] in nums2

Mark and Continue

Mark found elements as used

Build Result

Collect all matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int* solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int* result = (int*)malloc(1000 * sizeof(int));
    int* used = (int*)calloc(nums2Size, sizeof(int));
    *returnSize = 0;
    
    for (int i = 0; i < nums1Size; i++) {
        for (int j = 0; j < nums2Size; j++) {
            if (!used[j] && nums1[i] == nums2[j]) {
                result[(*returnSize)++] = nums1[i];
                used[j] = 1;
                break;
            }
        }
    }
    
    free(used);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums1[1000], nums1Size = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    fgets(line, sizeof(line), stdin);
    int nums2[1000], nums2Size = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums1, nums1Size, nums2, nums2Size, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each element in nums1 (n), we search through nums2 (m)

✓ Linear Growth

Space Complexity

O(1)

Only using variables, modifying input array to mark used elements

✓ Linear Space

125.0K Views

High Frequency

~15 min Avg. Time

3.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Nested Loops — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler