Intersection of Two Arrays II — Problem Statement & Solution Guide

HashingEasyFrequency Map

TimeO(n+m)

SpaceO(min(n,m))

Problem Description

You are tasked with processing two sequences of integer identifiers, representing distinct data streams. Your objective is to compute the intersection of these two sequences, where the result must reflect the multiplicity of elements present in both inputs. Specifically, if an integer appears k times in the first sequence and m times in the second sequence, it must appear exactly min(k, m) times in the resulting sequence.

The order of elements in the output sequence is not significant; any permutation of the valid intersection is acceptable. You are required to design an algorithm that efficiently determines these common elements while respecting their frequency constraints from both source arrays.

Given two integer arrays, nums1 and nums2, return an array containing the intersection of nums1 and nums2. Each element in the result must appear as many times as it shows in both arrays. The output can be in any order.

DSA Pattern Breakdown

"Intersection of Two Arrays II"

easy

WHY DOES IT MATTER?

Counting‑based intersection is a canonical example of frequency‑based hashing, a pattern that appears in duplicate removal, anagram checks, and inventory reconciliation, making it a staple for any engineer dealing with multisets.

OPTIMIZATION CHALLENGE

The key insight is to avoid the quadratic cross‑comparison by collapsing one array into a constant‑time lookup structure (hash map) and then performing a single linear pass over the other array, thereby achieving O(n+m) time.

REAL-WORLD CONNECTION

Think of a warehouse receiving two shipment manifests; the items that truly arrived are those whose counts appear in both manifests. The hash‑map acts like a ledger that records how many of each SKU were promised, and the second manifest decrements the ledger to reveal the common stock.

Always iterate over the smaller array to build the hash map; this minimizes auxiliary space and often improves cache locality, a subtle but impactful performance win in interviews.

COMPLEXITY AT A GLANCE

⏱ Time:O(n+m)

💾 Space:O(min(n,m))

Core Theory — Why This Approach?

The intersection‑of‑two‑arrays problem asks for each element that appears in both input multisets, respecting multiplicities. A naïve solution would compare every element of the first array against every element of the second, yielding O(n·m) time, which quickly becomes infeasible for large streams (e.g., millions of identifiers). The optimal paradigm leverages hashing: by counting occurrences of each value in one array using a hash map, we can then iterate the second array and emit an element whenever its count in the map is still positive, decrementing the count. This reduces the work to linear time relative to the total number of elements while using extra space proportional only to the distinct values of the smaller array. The approach also naturally handles negative numbers and zero because hash maps are value‑agnostic, making it a robust, language‑independent solution.

Interview Questions on This Problem

Q1How would you compute the intersection of two unsorted integer arrays when the arrays can contain duplicates?

Build a hash map of element frequencies from the smaller array, then scan the larger array, adding an element to the result each time it appears in the map with a positive count and decrementing that count. This runs in O(n+m) time and O(min(n,m)) extra space.

Q2What trade‑offs arise if you sort both arrays first and then use two‑pointer traversal instead of a hash map?

Sorting costs O(n log n + m log m) time but uses O(1) extra space (or O(n+m) if you count the sorted copies). The two‑pointer scan then runs in O(n+m). This can be preferable when memory is tight or when the input is already sorted.

Q3In a distributed system where each node streams a portion of a massive dataset, how can you compute the global intersection efficiently?

Each node can locally build a frequency map for its slice, then a central aggregator merges the maps by taking the minimum count for each key across nodes. Using map‑reduce style shuffling ensures linear work per node and O(k) space where k is the number of distinct identifiers globally.

Examples

Example 1

Input

nums1 = [4, 2, 4, 8, 1], nums2 = [2, 4, 4, 9, 8]

Output

[2, 4, 4, 8]

Explanation: 1. Count frequencies in nums1: {4:2, 2:1, 8:1, 1:1}. 2. Count frequencies in nums2: {2:1, 4:2, 9:1, 8:1}. 3. For each common key, take the minimum count: - 2: min(1, 1) = 1 - 4: min(2, 2) = 2 - 8: min(1, 1) = 1 4. Construct result: [2, 4, 4, 8]. Order may vary.

Example 2

Input

nums1 = [10, 20, 30], nums2 = [40, 50, 60]

Output

[]

Explanation: 1. Count frequencies in nums1: {10:1, 20:1, 30:1}. 2. Count frequencies in nums2: {40:1, 50:1, 60:1}. 3. No common keys exist between the two frequency maps. 4. Result is an empty array.

Example 3

Input

nums1 = [7, 7, 7, 7], nums2 = [7, 7]

Output

[7, 7]

Explanation: 1. Count frequencies in nums1: {7:4}. 2. Count frequencies in nums2: {7:2}. 3. Common key 7: min(4, 2) = 2. 4. Result contains two instances of 7: [7, 7].

Example 4

Input

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

Output

[1, 1, 2, 3]

Explanation: 1. Count frequencies in nums1: {1:2, 2:2, 3:1}. 2. Count frequencies in nums2: {1:2, 2:1, 3:3}. 3. Calculate min counts: - 1: min(2, 2) = 2 - 2: min(2, 1) = 1 - 3: min(1, 3) = 1 4. Result: [1, 1, 2, 3].

Constraints

1 <= nums1.length, nums2.length <= 10^5
-10^9 <= nums1[i], nums2[i] <= 10^9
The answer is guaranteed to fit into a 32-bit integer.

Optimal Approach & Strategy

Create a frequency hash map from the smaller array and iterate the larger array, emitting elements while decrementing the map counts, achieving O(n+m) time and O(min(n,m)) space.

Brute Force Approach

Compare each element of the first array with every element of the second, marking matches and handling duplicates manually, which leads to O(n·m) time.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n+m)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    // Ensure nums1 is the smaller array to optimize space
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1);
    }
    
    const countMap = new Map();
    for (const num of nums1) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    
    const result = [];
    for (const num of nums2) {
        if (countMap.has(num) && countMap.get(num) > 0) {
            result.push(num);
            countMap.set(num, countMap.get(num) - 1);
        }
    }
    
    return result;
};

// Driver code for testing
const nums1 = [4, 2, 4, 8, 1];
const nums2 = [2, 4, 4, 9, 8];
console.log(intersect(nums1, nums2));

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        // Ensure nums1 is the smaller array to optimize space
        if (nums1.size() > nums2.size()) {
            return intersect(nums2, nums1);
        }
        
        unordered_map<int, int> countMap;
        for (int num : nums1) {
            countMap[num]++;
        }
        
        vector<int> result;
        for (int num : nums2) {
            if (countMap[num] > 0) {
                result.push_back(num);
                countMap[num]--;
            }
        }
        
        return result;
    }
};

int main() {
    vector<int> nums1 = {4, 2, 4, 8, 1};
    vector<int> nums2 = {2, 4, 4, 9, 8};
    Solution sol;
    vector<int> result = sol.intersect(nums1, nums2);
    
    cout << "[";
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    
    return 0;
}

import java.util.*;

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // Ensure nums1 is the smaller array to optimize space
        if (nums1.length > nums2.length) {
            return intersect(nums2, nums1);
        }
        
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums1) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        
        List<Integer> result = new ArrayList<>();
        for (int num : nums2) {
            if (countMap.getOrDefault(num, 0) > 0) {
                result.add(num);
                countMap.put(num, countMap.get(num) - 1);
            }
        }
        
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            res[i] = result.get(i);
        }
        
        return res;
    }
    
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] nums1 = {4, 2, 4, 8, 1};
        int[] nums2 = {2, 4, 4, 9, 8};
        int[] result = sol.intersect(nums1, nums2);
        
        System.out.print("[");
        for (int i = 0; i < result.length; i++) {
            System.out.print(result[i]);
            if (i < result.length - 1) System.out.print(", ");
        }
        System.out.println("]");
    }
}

from typing import List
from collections import Counter

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Ensure nums1 is the smaller array to optimize space
        if len(nums1) > len(nums2):
            return self.intersect(nums2, nums1)
        
        count_map = Counter(nums1)
        result = []
        
        for num in nums2:
            if count_map[num] > 0:
                result.append(num)
                count_map[num] -= 1
        
        return result

# Driver code for testing
if __name__ == "__main__":
    sol = Solution()
    nums1 = [4, 2, 4, 8, 1]
    nums2 = [2, 4, 4, 9, 8]
    print(sol.intersect(nums1, nums2))

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    // Ensure nums1 is the smaller array to optimize space
    if (nums1.length > nums2.length) {
        return intersect(nums2, nums1);
    }
    
    const countMap = new Map();
    for (const num of nums1) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    
    const result = [];
    for (const num of nums2) {
        if (countMap.has(num) && countMap.get(num) > 0) {
            result.push(num);
            countMap.set(num, countMap.get(num) - 1);
        }
    }
    
    return result;
};

// Driver code for testing
const nums1 = [4, 2, 4, 8, 1];
const nums2 = [2, 4, 4, 9, 8];
console.log(intersect(nums1, nums2));

Asked in Top Tech Interviews

Swiggy

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Intersection of Two Arrays II Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Hashing

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Intersection of Two Arrays II — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor