LeetCode 350: Intersection of Two Arrays II Solution in Python – A Step-by-Step Guide

What Is LeetCode 350: Intersection of Two Arrays II?

In LeetCode 350: Intersection of Two Arrays II, you’re given two integer arrays nums1 and nums2, and your task is to return an array of their intersection, where each element appears as many times as it does in both arrays (up to the minimum count). For example, with nums1 = [1,2,2,1] and nums2 = [2,2], the intersection is [2,2]. This problem tests your ability to handle frequency counts, extending LeetCode 349: Intersection of Two Arrays.

Problem Statement

• Input: Two integer arrays nums1 and nums2.
• Output: An array of integers common to both nums1 and nums2, with multiplicity.
• Rules:
• Each element appears min(count in nums1, count in nums2) times.
• Order of elements doesn’t matter.
• Elements must appear in both arrays.

Constraints

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

Examples

• Input: nums1 = [1,2,2,1], nums2 = [2,2]
• Output: [2,2] (2 appears twice in both)
• Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
• Output: [4,9] (4 once, 9 once)
• Input: nums1 = [1,2], nums2 = [1,1]
• Output: [1] (1 once, min of 1 and 2)

Understanding the Problem: Counting the Overlap

To solve LeetCode 350: Intersection of Two Arrays II in Python, we need to find elements common to nums1 and nums2, including duplicates up to their minimum frequency in both arrays. A naive approach—checking each element pairwise—is O(n*m), too slow for 1000 elements. Instead, we’ll use:

• Best Solution (Hash Map): O(n + m) time, O(min(n, m)) space—fast and efficient.
• Alternative Solution (Sorting): O(n log n + m log m) time, O(1) space—clear but less optimal.

Let’s start with the hash map solution, explained in a beginner-friendly way.

Best Solution: Hash Map Approach

Why This Is the Best Solution

The hash map approach is the top choice for LeetCode 350 because it’s efficient—O(n + m) time, O(min(n, m)) space—and handles multiplicity naturally. It counts frequencies in the smaller array and matches them against the larger one, ensuring exact overlap counts with minimal overhead. It’s like tallying votes with a quick lookup—smart and quick!

How It Works

Think of this as a frequency matcher:

• Step 1: Build Frequency Map:
• Use smaller array (e.g., nums1) to count occurrences in a hash map.
• Step 2: Find Intersection:
• Iterate larger array (e.g., nums2), add to result if in map, decrement count.
• Step 3: Return Result:
• List of common elements with correct multiplicity.
• Step 4: Why It Works:
• Hash map lookups are O(1).
• Minimizes space by using smaller array.

It’s like matching invites with a handy tally sheet!

Step-by-Step Example

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

• Step 1: Map (nums1) = {1:2, 2:2}
• Step 2: Result = []
• 2: in map, count=2, add 2, decrement to 1, Result = [2]
• 2: in map, count=1, add 2, decrement to 0, Result = [2, 2]
• Step 3: Return [2, 2]
• Result: [2, 2]

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

• Map (nums1): {4:1, 9:1, 5:1}
• Result:
• 9: add 9, count=0, [9]
• 4: add 4, count=0, [9, 4]
• 9: count=0, skip
• 8: not in map
• 4: count=0, skip
• Return: [9, 4]

Code with Detailed Line-by-Line Explanation

Copy codefrom collections import Counter

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Use smaller array for hash map to save space
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1

        # Count frequencies in smaller array
        count = Counter(nums1)

        # Build intersection
        result = []
        for num in nums2:
            if num in count and count[num] > 0:
                result.append(num)
                count[num] -= 1

        return result

• Lines 6-7: Swap if nums1 is larger, use smaller for map.
• Line 10: Build frequency map with Counter.
• Lines 13-16: Iterate nums2:
• If num in map and count > 0, add to result, decrement count.
• Time Complexity: O(n + m)—building map and checking.
• Space Complexity: O(min(n, m))—map size.

This is like an overlap-tallying pro—fast and sleek!

Alternative Solution: Sorting Approach

Why an Alternative Approach?

The sorting approach—O(n log n + m log m) time, O(1) space—sorts both arrays and uses two pointers to find matches, handling multiplicity by advancing pointers based on counts. It’s intuitive for ordered traversal but slower due to sorting. It’s like lining up lists and matching step-by-step—clear but less efficient!

How It Works

Sort and match:

• Step 1: Sort both arrays.
• Step 2: Use two pointers to find matches.
• Step 3: Include duplicates, build result.

Step-by-Step Example

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

• Sort: nums1 = [1,1,2,2], nums2 = [2,2]
• Pointers: i=0, j=0, result = []
• Step 1: 1<2, i=1
• Step 2: 1<2, i=2
• Step 3: 2=2, add 2, i=3, j=1
• Step 4: 2=2, add 2, i=4, j=2, done
• Result: [2, 2]

Code for Sorting Approach

Copy codeclass Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Sort arrays
        nums1.sort()
        nums2.sort()

        # Two pointers
        i = j = 0
        result = []

        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                result.append(nums1[i])
                i += 1
                j += 1
            elif nums1[i] < nums2[j]:
                i += 1
            else:
                j += 1

        return result

• Time Complexity: O(n log n + m log m)—sorting dominates.
• Space Complexity: O(1)—excluding output.

It’s a sorted overlap finder—vivid but slower!

Comparing the Two Solutions

• Hash Map (Best):
• Pros: O(n + m) time, O(min(n, m)) space, fast and simple.
• Cons: Uses extra space.
• Sorting (Alternative):
• Pros: O(n log n + m log m) time, O(1) space, space-efficient.
• Cons: Slower due to sorting.

Hash map wins for speed.

Additional Examples and Edge Cases

• [1], [1,1]: [1].
• [1,2], [3]: [].
• [2,2,2], [2,2]: [2, 2].

Both handle these, but hash map is faster.

Complexity Breakdown

• Hash Map: Time O(n + m), Space O(min(n, m)).
• Sorting: Time O(n log n + m log m), Space O(1).

Hash map is the clear choice.

Key Takeaways

• Hash Map: Count and match—fast!
• Sorting: Sort and scan—clear!
• Python: Counters and sorting shine—see [Python Basics](/python/basics).
• Intersection: Frequency matters here.

Final Thoughts: Count the Overlap

LeetCode 350: Intersection of Two Arrays II in Python is a fun twist on array intersection. The hash map solution offers speed and elegance, while sorting provides a tangible baseline. Want more array challenges? Try LeetCode 349: Intersection of Two Arrays or LeetCode 217: Contains Duplicate. Ready to intersect? Head to Solve LeetCode 350 on LeetCode and tally those overlaps today!