Intersection of Two Arrays II

Difficulty: Easy | Acceptance: 59.90% | Paid: No Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

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.

• Examples
• Constraints
• Brute Force
• Hash Map
• Sorting + Two Pointers
• Binary Search

Examples

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

Brute Force

Intuition Iterate through each element of the first array and try to find a matching unused element in the second array.

Steps

• Create a result list and a boolean array to track used elements in nums2.
• Loop through each element x in nums1.
• For each x, loop through nums2 to find the first unused element equal to x.
• If found, add x to the result and mark the index in nums2 as used.
• Return the result list.

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        res = []
        used = [False] * len(nums2)
        for n1 in nums1:
            for i, n2 in enumerate(nums2):
                if not used[i] and n1 == n2:
                    res.append(n1)
                    used[i] = True
                    break
        return res

Complexity

• Time: O(n * m) where n and m are the lengths of the arrays.
• Space: O(m) to store the used array.
• Notes: Simple but inefficient for large inputs.

Hash Map

Intuition Count the frequency of each number in the first array using a hash map. Then iterate through the second array, decrementing the count in the map whenever a match is found.

Steps

• Create a hash map to store counts of elements in nums1.
• Iterate through nums2. If the current number exists in the map with a count > 0, add it to the result and decrement the count.
• Return the result list.

import collections

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        counts = collections.Counter(nums1)
        res = []
        for n in nums2:
            if counts.get(n, 0) > 0:
                res.append(n)
                counts[n] -= 1
        return res

Complexity

• Time: O(n + m)
• Space: O(min(n, m))
• Notes: Efficient time complexity, uses extra space for the hash map.

Sorting + Two Pointers

Intuition If both arrays are sorted, we can use two pointers to traverse them simultaneously, similar to the merge step in merge sort.

Steps

• Sort both arrays.
• Initialize two pointers i and j to 0.
• While both pointers are within bounds:
  • If nums1[i] < nums2[j], increment i.
  • If nums1[i] > nums2[j], increment j.
  • If they are equal, add the value to the result and increment both pointers.
• Return the result.

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        nums1.sort()
        nums2.sort()
        i = j = 0
        res = []
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                res.append(nums1[i])
                i += 1
                j += 1
        return res

Complexity

• Time: O(n log n + m log m) due to sorting.
• Space: O(1) if we ignore the space required for the output and sorting stack (O(log n) for sorting).
• Notes: Good if the input is already sorted or if space is limited.

Binary Search

Intuition If one array is significantly larger than the other, sort the smaller array and binary search for each element of the larger array within the smaller one.

Steps

• Ensure nums1 is the smaller array. If not, swap.
• Sort nums1.
• Iterate through nums2. For each element, perform a binary search in nums1.
• If found, add to result and remove that element from nums1 to handle duplicates.

import bisect

class Solution:
    def intersect(self, nums1: list[int], nums2: list[int]) -> list[int]:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        nums1.sort()
        res = []
        for n in nums2:
            i = bisect.bisect_left(nums1, n)
            if i < len(nums1) and nums1[i] == n:
                res.append(n)
                del nums1[i]
        return res

Complexity

• Time: O((n + m) log n) where n is the length of the smaller array.
• Space: O(1) (excluding result and sort space).
• Notes: Efficient when one array is much smaller than the other.