Intersection of Two Arrays - Practice Coding Problems

Intersection of Two Arrays - Problem

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

The intersection contains elements that appear in both arrays, with no duplicates in the final result.

Input & Output

Example 1 — Basic Case

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

› Output: [2]

💡 Note: The number 2 appears in both arrays. Even though 2 appears multiple times, we only include it once in the result.

Example 2 — Multiple Intersections

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

› Output: [4,9]

💡 Note: Both 4 and 9 appear in both arrays. The order in the result doesn't matter, so [9,4] would also be correct.

Example 3 — No Intersection

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

› Output: []

💡 Note: No elements appear in both 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

Two integer arrays with possible duplicates

Process

Find elements that appear in both arrays

Output

Array of unique common elements

Key Takeaway

🎯 Key Insight: Hash sets turn O(n×m) nested loops into O(n+m) single pass by providing O(1) lookups

Asked in

G Google 42 a Amazon 38 M Microsoft 25 F Facebook 22

The key insight is using hash sets for O(1) lookups instead of nested loops. Convert one array to a hash set, then check each element of the second array. Best approach is hash set with Time: O(n+m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers (Sorted Arrays)	O(n log n + m log m)	O(1)	Sort both arrays first, then use two pointers to find common elements
Brute Force - Nested Loops	O(n×m)	O(min(n,m))	For each element in nums1, check if it exists in nums2
Hash Set - Single Pass	O(n+m)	O(n)	Convert one array to hash set, then check the other array against it

Two Pointers (Sorted Arrays) — Algorithm Steps

Sort both arrays
Use two pointers, one for each array
If values equal, add to result and move both pointers
If values differ, move the pointer with smaller value

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort both arrays first

Compare

Compare elements at both pointers

Advance

Move pointer(s) based on comparison

Code -

solution.c — C

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

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

int* solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    qsort(nums1, nums1Size, sizeof(int), compare);
    qsort(nums2, nums2Size, sizeof(int), compare);
    
    int* result = (int*)malloc(1000 * sizeof(int));
    int resultSize = 0;
    int i = 0, j = 0;
    
    while (i < nums1Size && j < nums2Size) {
        if (nums1[i] == nums2[j]) {
            if (resultSize == 0 || result[resultSize - 1] != nums1[i]) {
                result[resultSize++] = nums1[i];
            }
            i++;
            j++;
        } else if (nums1[i] < nums2[j]) {
            i++;
        } else {
            j++;
        }
    }
    
    *returnSize = resultSize;
    return result;
}

int main() {
    char line1[10000], line2[10000];
    fgets(line1, sizeof(line1), stdin);
    fgets(line2, sizeof(line2), stdin);
    
    int nums1[1000], nums2[1000];
    int nums1Size = 0, nums2Size = 0;
    
    char* token = strtok(line1, "[,]\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums1[nums1Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    token = strtok(line2, "[,]\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            nums2[nums2Size++] = atoi(token);
        }
        token = strtok(NULL, "[,]\n");
    }
    
    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 log n + m log m)

O(n log n) and O(m log m) for sorting, then O(n+m) for two-pointer traversal

⚡ Linearithmic

Space Complexity

O(1)

Only uses constant extra space for pointers and variables (excluding result storage)

✓ Linear Space

78.5K Views

High Frequency

~15 min Avg. Time

2.8K 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

Two Pointers (Sorted Arrays) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler