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

What Is LeetCode 349: Intersection of Two Arrays?

In LeetCode 349: Intersection of Two Arrays, you’re given two integer arrays nums1 and nums2, and your task is to return an array of their intersection—each element in the result must be unique and appear in both arrays. For example, with nums1 = [1,2,2,1] and nums2 = [2,2], the intersection is [2]. This problem tests your ability to handle duplicates and find common elements efficiently, connecting to basics in Python Basics and preparing for LeetCode 350: Intersection of Two Arrays II.

Problem Statement

• Input: Two integer arrays nums1 and nums2.
• Output: An array of unique integers present in both nums1 and nums2.
• Rules:
• Each element in the result must be unique.
• 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 is common, unique)
• Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
• Output: [9,4] (9 and 4 are common, unique)
• Input: nums1 = [1], nums2 = [2]
• Output: [] (No common elements)

Understanding the Problem: Finding the Overlap

To solve LeetCode 349: Intersection of Two Arrays in Python, we need to find the unique elements common to nums1 and nums2. A naive approach—checking each element of one array against the other—is O(n*m), where n and m are array lengths, too slow for 1000 elements. Instead, we’ll use:

• Best Solution (Set-Based): O(n + m) time, O(n) 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 set-based solution, explained in a beginner-friendly way.

Best Solution: Set-Based Approach

Why This Is the Best Solution

The set-based approach is the top choice for LeetCode 349 because it’s efficient—O(n + m) time, O(n) space—and leverages Python’s built-in set operations to find the intersection in a snap. It converts one array to a set for O(1) lookups and checks the other array against it, ensuring uniqueness automatically. It’s like using a guest list lookup table—quick and sleek!

How It Works

Think of this as a list matcher:

• Step 1: Create Set:
• Convert nums1 to a set (removes duplicates).
• Step 2: Find Intersection:
• Check each unique element in nums2 against the set.
• Add matches to a result set (ensures uniqueness).
• Step 3: Return Result:
• Convert result set to list.
• Step 4: Why It Works:
• Set lookups are O(1).
• Single pass through each array.

It’s like matching names with a super-fast checklist!

Step-by-Step Example

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

• Step 1: Set1 = {1, 2} (from nums1, duplicates removed)
• Step 2: Result = set()
• Check 2: in Set1, add 2, Result = {2}
• Check 2: in Set1, already added (skip)
• Step 3: Return [2]
• Result: [2]

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

• Set1: {4, 9, 5}
• Result:
• 9: add 9, {9}
• 4: add 4, {9, 4}
• 9: skip (duplicate)
• 8: not in Set1
• 4: skip (duplicate)
• Return: [9, 4]

Code with Detailed Line-by-Line Explanation

Copy codeclass Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        # Convert nums1 to set for O(1) lookup
        set1 = set(nums1)

        # Find intersection
        result = set()
        for num in nums2:
            if num in set1:
                result.add(num)

        # Convert to list
        return list(result)

• Line 3: Create set from nums1 (removes duplicates).
• Lines 6-9: Iterate nums2:
• If num in set1, add to result set (unique).
• Line 12: Return result as list.
• Time Complexity: O(n + m)—building set and checking.
• Space Complexity: O(n)—set1 and result set.

This is like an overlap-spotting 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 common elements, avoiding extra space beyond the output. It’s more intuitive for understanding intersection via ordered traversal but slower due to sorting. It’s like lining up two lists and matching as you go—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: Skip 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, skip (duplicate), j=2, done
• Result: [2]

Code for Sorting Approach

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

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

        while i < len(nums1) and j < len(nums2):
            if nums1[i] == nums2[j]:
                if prev != nums1[i]:  # Avoid duplicates
                    result.append(nums1[i])
                    prev = 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 matcher—vivid but slower!

Comparing the Two Solutions

• Set-Based (Best):
• Pros: O(n + m) time, O(n) 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.

Set-based wins for speed.

Additional Examples and Edge Cases

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

Both handle these, but set-based is faster.

Complexity Breakdown

• Set-Based: Time O(n + m), Space O(n).
• Sorting: Time O(n log n + m log m), Space O(1).

Set-based is the clear choice.

Key Takeaways

• Set-Based: Lookup magic—fast!
• Sorting: Line up and match—clear!
• Python: Sets and sorting shine—see [Python Basics](/python/basics).
• Intersection: Sets beat sorting here.

Final Thoughts: Find the Overlap

LeetCode 349: Intersection of Two Arrays in Python is a foundational array challenge. The set-based solution offers speed and elegance, while sorting provides a tangible baseline. Want more array fun? Try LeetCode 350: Intersection of Two Arrays II or LeetCode 217: Contains Duplicate. Ready to intersect? Head to Solve LeetCode 349 on LeetCode and spot those common elements today!