Is Intersection of Two Arrays II easy or hard?

Intersection of Two Arrays II is classified as an Easy problem. The main challenge is recognizing that duplicates require frequency tracking rather than simple set intersection. Once you apply a hash map or sorting with two pointers, the implementation becomes straightforward.

Intersection of Two Arrays II Python/Java solution

In Python, use a dictionary or collections.Counter to track frequencies and build the result list. In Java, use a HashMap to store counts and iterate through the second array to form the intersection. Both implementations follow the same O(n + m) hash map strategy.

How to solve Intersection of Two Arrays II in O(n)?

Use a hash map to store frequencies from one array. Then scan the second array and check if the current element exists in the map with a remaining count. If it does, append it to the result and decrement the count. This processes both arrays once, resulting in O(n + m) time.

What is the best approach for Intersection of Two Arrays II?

The hash map frequency approach is typically the best solution. Store counts of elements from one array in a map, then iterate through the second array and decrease counts when matches are found. This achieves O(n + m) time complexity with O(min(n, m)) extra space.

Is Intersection of Two Arrays II asked at Google/Amazon/Meta?

Intersection-style array problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations often test hash maps, two pointers, or sorting techniques. The problem checks whether you can efficiently handle duplicates and frequency counting.

What data structure is used in Intersection of Two Arrays II?

The most common data structure used is a hash map (or dictionary) to track element frequencies. Another approach relies on sorting both arrays and applying the two pointers technique. Both methods are standard tools for array comparison problems.

What is the time complexity of Intersection of Two Arrays II?

The optimal solution using a hash map runs in O(n + m) time, where n and m are the lengths of the two arrays. Each element is processed once and hash lookups take constant time on average. The sorting approach takes O(n log n + m log m) due to the sorting step.

Description Solution Video 15:31

350. Intersection of Two Arrays II

Easy60.4% acceptance9 companies

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must appear as many times as it shows in both arrays and you may return the result in any order.

Example 1:

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

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Explanation: [9,4] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?