Intersection of Two Arrays II

Easy
182.

Intersection of Two Arrays II

Intersection of Two Arrays II is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Meta, Bloomberg and Databricks interviews.

Given two integer arrays nums1 and nums2, return their intersection including multiplicity: each value appears as many times as it shows in both arrays. Return the result in increasing order.

Example 1

Input
nums1 = [1,2,2,1], nums2 = [2,2]
Output
[2,2]
Explanation
2 appears twice in each array, so it appears twice in the answer.

Example 2

Input
nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output
[4,9]

Example 3

Input
nums1 = [1,2], nums2 = [3,4]
Output
[]

Constraints

  • 1 <= nums1.length, nums2.length <= 30
  • 0 <= nums1[i], nums2[i] <= 60

Follow-up: What if the arrays were already sorted? What if one of them was far larger than the other?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var intersect = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Intersection of Two Arrays II — Problem & Solution

Intersection of Two Arrays II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Intersection of Two Arrays II is an easy coding problem on arrays, hash table and sorting, asked in Amazon, Meta, Bloomberg and Databricks interviews.

Problem statement

Given two integer arrays nums1 and nums2, return their intersection including multiplicity: each value appears as many times as it shows in both arrays. Return the result in increasing order.

Example 1

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Explanation: 2 appears twice in each array, so it appears twice in the answer.

Example 2

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

Example 3

Input: nums1 = [1,2], nums2 = [3,4]
Output: []

Constraints

  • 1 <= nums1.length, nums2.length <= 30
  • 0 <= nums1[i], nums2[i] <= 60

Follow-up: What if the arrays were already sorted? What if one of them was far larger than the other?

Hints for Intersection of Two Arrays II

  1. Hint 1

    A plain set loses the counts. Use a map from value to how many copies remain.

  2. Hint 2

    Build the map from one array, then walk the other and take a copy whenever the remaining count is positive.

  3. Hint 3

    Decrement the count as you take, so a value is never taken more often than it occurs.

How to solve Intersection of Two Arrays II

Multiplicity means a set is not enough. Count the first array, then walk the second and take a value only while its remaining count is positive.

Approach

  1. Build count[value] from nums1.
  2. For each x in nums2, if count[x] > 0, append x and decrement.
  3. Sort the collected values.

Why it works

Each take decrements the budget for that value, so it is emitted min(count1, count2) times — the multiset intersection.

Complexity

  • Time — O(n + m + k log k)
  • Space — O(n)

Pitfalls

  • Count the smaller array if memory matters; the logic is symmetric.
  • If both arrays are already sorted, two pointers do it with no map.

Reference solution

Python

def intersect(nums1, nums2):
    count = {}
    for x in nums1:
        count[x] = count.get(x, 0) + 1
    out = []
    for x in nums2:
        if count.get(x, 0) > 0:
            out.append(x)
            count[x] -= 1
    out.sort()
    return out

Java

public static int[] intersect(int[] nums1, int[] nums2) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums1) count.put(x, count.getOrDefault(x, 0) + 1);
    List<Integer> out = new ArrayList<>();
    for (int x : nums2) {
        int c = count.getOrDefault(x, 0);
        if (c > 0) {
            out.add(x);
            count.put(x, c - 1);
        }
    }
    Collections.sort(out);
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    unordered_map<int, int> count;
    for (int x : nums1) count[x]++;
    vector<int> out;
    for (int x : nums2) {
        if (count[x] > 0) {
            out.push_back(x);
            count[x]--;
        }
    }
    sort(out.begin(), out.end());
    return out;
}

JavaScript

var intersect = function(nums1, nums2) {
    const count = new Map();
    for (let i = 0; i < nums1.length; i++) {
        count.set(nums1[i], (count.get(nums1[i]) || 0) + 1);
    }
    const out = [];
    for (let i = 0; i < nums2.length; i++) {
        const c = count.get(nums2[i]) || 0;
        if (c > 0) {
            out.push(nums2[i]);
            count.set(nums2[i], c - 1);
        }
    }
    return out.sort(function(a, b) { return a - b; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets