Intersection of Two Arrays II

easy

Last Updated - 08/09/2024

Problem Statement

You are tasked with finding the common elements between two integer arrays, nums1 and nums2. Specifically, you need to return an array containing the intersection of these two arrays, with each element appearing as many times as it occurs in both arrays.

Details:

Input: Two integer arrays, nums1 and nums2, where each array has a length between 1 and 1,000. The elements of these arrays are non-negative integers, each ranging from 0 to 1,000.
Output: An array of integers representing the intersection of nums1 and nums2. Each integer should appear in the result as many times as it appears in both arrays. The order of elements in the output does not need to match any specific order.

Example 1

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

Output: [2,2]

Constraints

The length of nums1 and nums2 is between 1 and 1,000.
Each element in nums1 and nums2 is between 0 and 1,000.

Follow-Up Questions:

What optimization techniques would you use if the given arrays are already sorted?
How would you approach the problem if nums1 is significantly smaller than nums2?
What strategies would you employ if the elements of nums2 are stored on disk and memory is limited, preventing you from loading all elements at once?

Solution 1: Hash Map Approach

function intersectHashMap(nums1, nums2) {
    const map = new Map();
    const result = [];

    for (const num of nums1) {
        map.set(num, (map.get(num) || 0) + 1);
    }

    for (const num of nums2) {
        if (map.get(num) > 0) {
            result.push(num);
            map.set(num, map.get(num) - 1);
        }
    }

    return result;
} 

const nums11 = [1,2,2,1];
const nums21 = [2,2];
intersectHashMap(nums11,nums21);  //output: [2,2]

Solution 2: Counting Elements Approach

function intersectCounting(nums1, nums2) {
    const countMap = {};
    const result = [];

    for (const num of nums1) {
        countMap[num] = (countMap[num] || 0) + 1;
    }

    for (const num of nums2) {
        if (countMap[num] > 0) {
            result.push(num);
            countMap[num]--;
        }
    }

    return result;
} 

const nums11 = [1,2,2,1];
const nums21 = [2,2];
intersectCounting(nums11,nums21);  //output: [2,2]

Solution 3: Using Frequency Count and Filtering

function intersectFrequencyCount(nums1, nums2) {
    const freq = nums1.reduce((acc, num) => {
        acc[num] = (acc[num] || 0) + 1;
        return acc;
    }, {});
    const result = nums2.filter(num => {
        if (freq[num]) {
            freq[num]--;
            return true;
        }
        return false;
    });

    return result;
} 

const nums11 = [1,2,2,1];
const nums21 = [2,2];
intersectFrequencyCount(nums11,nums21);  //output: [2,2]

Solution 4: Two Pointers

function intersectSortingTwoPointers(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);

    const result = [];
    let i = 0;
    let j = 0;

    while (i < nums1.length && j < nums2.length) {
        if (nums1[i] < nums2[j]) {
            i++;
        } else if (nums1[i] > nums2[j]) {
            j++;
        } else {
            result.push(nums1[i]);
            i++;
            j++;
        }
    }

    return result;
} 

const nums11 = [1,2,2,1];
const nums21 = [2,2];
intersectSortingTwoPointers(nums11,nums21);  //output: [2,2]