#350

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Intersection of Two Arrays II

Find the intersection of two arrays, accounting for multiple occurrences of the same number.

array hash table two pointers binary search sorting

Problem Statement

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 appears in both arrays, and the order of the result does not matter.

For example, for nums1 = [1,2,2,1] and nums2 = [2,2], the intersection would be [2,2], as 2 appears twice in both arrays. The task is to solve this in an optimal manner using array scanning and hash table techniques.

Examples

Example 1

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

Output: [2,2]

Example details omitted.

Example 2

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

Output: [4,9]

[9,4] is also accepted.

Constraints

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

Solution Approach

Hash Table Approach

The most efficient solution involves scanning nums1 and storing counts of each element in a hash table. Then, for each element in nums2, check if it exists in the hash table and if its count is greater than zero. If true, add it to the result and decrease its count.

Two Pointer Approach

If the arrays are sorted, you can use the two-pointer technique. First, sort both arrays, then iterate through them with two pointers to find common elements. This method avoids extra space usage by modifying the arrays in-place, but requires sorting them first.

Sorting and Binary Search

Another alternative is to sort both arrays and use binary search to check for elements from nums1 in nums2. While this method reduces the need for hash tables, the complexity of sorting and searching could result in slower performance for larger arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The hash table approach has a time complexity of O(n + m), where n and m are the lengths of nums1 and nums2, respectively. The two-pointer approach has a time complexity of O(n log n + m log m) due to sorting. The binary search method involves O(n log m) time complexity, where n is the length of nums1 and m is the length of nums2. The space complexity is O(min(n, m)) for the hash table approach and O(1) for the two-pointer approach if sorting is done in-place.

What Interviewers Usually Probe

Ability to implement hash table for counting frequencies efficiently.
Demonstrates understanding of time-space tradeoffs with different approaches.
Clear grasp of problem constraints and optimizations for large inputs.

Common Pitfalls or Variants

Common pitfalls

Not handling duplicates correctly, which can lead to incorrect results.
Using inefficient algorithms that result in high time complexity, especially with large input sizes.
Failure to optimize space usage, leading to unnecessary extra memory consumption.

Follow-up variants

Intersection of three arrays with similar constraints.
Finding the union of two arrays with the same frequency consideration.
Intersection problem in an unsorted list with missing elements.

FAQ

How does the intersection of two arrays work in this problem?

The problem asks you to find common elements between two arrays, with the constraint that each element in the result must appear as many times as it appears in both arrays.

What is the optimal approach for solving the Intersection of Two Arrays II?

The most optimal solution uses a hash table to store counts of elements from one array and then checks for these elements in the second array, ensuring efficient time and space usage.

What are some common mistakes when solving the Intersection of Two Arrays II?

Common mistakes include not handling duplicates properly, inefficient algorithms that lead to time complexity issues, and using too much memory by not optimizing the space usage.

How does sorting help in solving the Intersection of Two Arrays II?

Sorting allows you to apply the two-pointer technique, which is an efficient way to find common elements in sorted arrays without using extra space for hash tables.

Is the Intersection of Two Arrays II problem easy or hard?

This problem is considered easy as it can be solved with multiple approaches, but it requires careful consideration of time and space complexity to handle larger inputs.

terminal

Solution

Solution 1: Hash Table

We can use a hash table $\textit{cnt}$ to count the occurrences of each element in the array $\textit{nums1}$. Then, we iterate through the array $\textit{nums2}$. If an element $x$ is in $\textit{cnt}$ and the occurrence of $x$ is greater than $0$, we add $x$ to the answer and then decrement the occurrence of $x$ by one.

1

2

3

4

5

6

7

8

9

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        cnt = Counter(nums1)
        ans = []
        for x in nums2:
            if cnt[x]:
                ans.append(x)
                cnt[x] -= 1
        return ans

Continue Practicing

#349 intersection of two arrays #532 k diff pairs in an array #1346 check if n and its double exist