💬 Discord
Sign In
NeetCode #83LC-349EasyArrays & Hashing
← Back to All Problems

#83 · #349 · Intersection of Two Arrays(两个数组的交集)

📌 Problem Statement & Constraints

Given two integer arrays nums1 and nums2, return an array of their intersection: each element must be unique and may appear in any order. Constraints: 1 <= nums1.length, nums2.length <= 1000, 0 <= nums[i] <= 1000.

💡 Core Algorithmic Approaches

  1. Because the result must contain each element only once, a set is the natural output container.
  2. Convert both arrays to sets and take the intersection.
  3. Python's & operator or set.intersection expresses this directly.
  4. An alternative for large inputs is to sort both arrays and use two pointers, which is O(n log n) with O(1) extra space.

💻 Benchmark Python3 Implementation

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        return list(set(nums1) & set(nums2))


# Two-pointer variant: O(n log n) time, O(1) extra space beyond the output
class Solution2:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        res = []
        i = j = 0
        while i < len(nums1) and j < len(nums2):
            if nums1[i] < nums2[j]:
                i += 1
            elif nums1[i] > nums2[j]:
                j += 1
            else:
                if not res or res[-1] != nums1[i]:   # deduplicate
                    res.append(nums1[i])
                i += 1
                j += 1
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n + m) for the set-based version (amortised), O(n log n + m log m) for the two-pointer version.
💾 Space Complexity
O(n + m) for the sets; O(1) extra for the two-pointer version (excluding the output).

⚠️ Interview Pitfalls & Follow-ups

  • Returning duplicates: the result must contain each element once, which the set-based version guarantees automatically. The two-pointer version needs an explicit deduplication check.
  • Using a list for membership tests: O(n) per lookup, giving O(n * m).
  • Returning [1, 1] for nums1 = [1,1], nums2 = [1,1]: the deduplication requirement is easy to miss.