Intersection of Multiple Arrays - Practice Coding Problems

Intersection of Multiple Arrays - Problem

Given a 2D integer array nums where nums[i] is a non-empty array of distinct positive integers, return the list of integers that are present in each array of nums sorted in ascending order.

Each sub-array contains only distinct positive integers, and we need to find the intersection of all arrays - the numbers that appear in every single array.

Input & Output

Example 1 — Basic Case

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

› Output: [3,4]

💡 Note: Numbers 3 and 4 appear in all three arrays: [3,1,2,4,5] contains 3,4; [1,2,3,4] contains 3,4; [3,4,5,6] contains 3,4

Example 2 — Single Element

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

› Output: []

💡 Note: No numbers appear in both arrays - first array has [1,2,3] and second has [4,5,6] with no overlap

Example 3 — All Same

$ Input: nums = [[1,2,3,4,5],[1,2,3,4,5]]

› Output: [1,2,3,4,5]

💡 Note: Both arrays are identical, so all elements [1,2,3,4,5] appear in every array

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i].length ≤ 1000
1 ≤ nums[i][j] ≤ 1000
All the values of nums[i] are unique

Visualization

Tap to expand

Understanding the Visualization

Input

Multiple arrays with distinct elements

Process

Find elements present in ALL arrays

Output

Sorted list of common elements

Key Takeaway

🎯 Key Insight: Count frequency of each number - elements in intersection appear exactly once per array

Asked in

a Amazon 25 f Facebook 18 G Google 12

The key insight is to count how many arrays each number appears in - numbers in the intersection must appear exactly as many times as there are arrays. Best approach is frequency counting with Time: O(n × k + r log r), Space: O(u) where n=number of arrays, k=average array size, r=result size, u=unique numbers.

Common Approaches

Approach	Time	Space	Notes
✓ Frequency Counting	O(n × k + r log r)	O(u)	Count frequency of each number across all arrays, include those appearing in all arrays
Set Intersection	O(n × k)	O(k)	Start with first array as set, progressively intersect with each subsequent array
Brute Force - Check Each Number	O(n × m × k)	O(1)	For each number in first array, check if it exists in all other arrays

Frequency Counting — Algorithm Steps

Create frequency counter
For each array, increment count for each unique number
Collect numbers with count equal to total arrays
Sort and return result

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Frequencies

Track how many arrays each number appears in

Filter Results

Select numbers appearing in all arrays

Sort Output

Return sorted intersection

Code -

solution.c — C

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

typedef struct {
    int key;
    int count;
} HashEntry;

int* solution(int** nums, int numsSize, int* numsColSize, int* returnSize) {
    *returnSize = 0;
    if (numsSize == 0) {
        return NULL;
    }
    
    HashEntry* hash = (HashEntry*)calloc(2000, sizeof(HashEntry));
    int hashSize = 2000;
    
    // Count frequency of each number across all arrays
    for (int i = 0; i < numsSize; i++) {
        for (int j = 0; j < numsColSize[i]; j++) {
            int num = nums[i][j];
            int index = num % hashSize;
            
            // Simple linear probing
            while (hash[index].count > 0 && hash[index].key != num) {
                index = (index + 1) % hashSize;
            }
            
            if (hash[index].count == 0) {
                hash[index].key = num;
            }
            hash[index].count++;
        }
    }
    
    // Collect numbers that appear in all arrays
    int* result = (int*)malloc(1000 * sizeof(int));
    int resultCount = 0;
    
    for (int i = 0; i < hashSize; i++) {
        if (hash[i].count == numsSize) {
            result[resultCount++] = hash[i].key;
        }
    }
    
    // Sort result
    for (int i = 0; i < resultCount - 1; i++) {
        for (int j = i + 1; j < resultCount; j++) {
            if (result[i] > result[j]) {
                int temp = result[i];
                result[i] = result[j];
                result[j] = temp;
            }
        }
    }
    
    *returnSize = resultCount;
    free(hash);
    return result;
}

int main() {
    int nums1[] = {3, 1, 2, 4, 5};
    int nums2[] = {1, 2, 3, 4};
    int nums3[] = {3, 4, 5, 6};
    
    int* nums[] = {nums1, nums2, nums3};
    int numsColSize[] = {5, 4, 4};
    int returnSize;
    
    int* result = solution(nums, 3, numsColSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k + r log r)

Visit each element once (n arrays × k average size) + sort result (r log r where r is result size)

⚡ Linearithmic

Space Complexity

O(u)

Hash map stores frequency for u unique numbers across all arrays

✓ Linear Space

23.4K Views

Medium Frequency

~15 min Avg. Time

892 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

Frequency Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler