Intersection of Two Arrays

Difficulty: Easy | Acceptance: 77.70% | 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 be unique and you may return the result in any order.

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

Examples

Example 1

Input:

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

Output:

[2]

Example 2

Input:

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

Output:

[9,4]

Explanation: [4,9] is also accepted.

Constraints

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

Hash Set

Intuition Use hash sets to store unique elements from both arrays, then find their intersection using set operations.

Steps

• Convert both arrays to sets to remove duplicates
• Find the intersection of both sets
• Convert the result back to an array

from typing import List

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

Complexity

• Time: O(n + m) where n and m are the lengths of the arrays
• Space: O(n + m) for storing both sets
• Notes: Most intuitive approach with optimal time complexity

Sorting + Two Pointers

Intuition Sort both arrays and use two pointers to traverse them simultaneously, finding common elements while skipping duplicates.

Steps

• Sort both arrays in ascending order
• Use two pointers starting at the beginning of each array
• Move the pointer pointing to the smaller value
• When values match, add to result if not already added
• Skip duplicates by checking the last element in result

from typing import List

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        nums1.sort()
        nums2.sort()
        
        i, j = 0, 0
        result = []
        
        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 result or result[-1] != nums1[i]:
                    result.append(nums1[i])
                i += 1
                j += 1
        
        return result

Complexity

• Time: O(n log n + m log m) for sorting
• Space: O(1) extra space (excluding result array)
• Notes: Good when space is constrained, but modifies input arrays

Binary Search

Intuition Sort the smaller array and use binary search to check if each element of the larger array exists in the sorted array.

Steps

• Sort the smaller array for binary search
• For each unique element in the larger array, binary search in the sorted array
• Use a set to track already found elements to avoid duplicates

from typing import List

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        if len(nums1) > len(nums2):
            nums1, nums2 = nums2, nums1
        
        nums1.sort()
        nums2_set = set()
        result = []
        
        for num in nums2:
            if num not in nums2_set and self.binarySearch(nums1, num):
                result.append(num)
                nums2_set.add(num)
        
        return result
    
    def binarySearch(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return False

Complexity

• Time: O(min(n, m) log min(n, m) + max(n, m)) for sorting and searching
• Space: O(min(n, m)) for the sorted array and seen set
• Notes: Efficient when one array is significantly smaller than the other

Brute Force

Intuition For each element in the first array, check if it exists in the second array using nested loops.

Steps

• Iterate through each element in nums1
• For each element, search through nums2
• If found and not already in result, add it
• Use a set to track already added elements

from typing import List

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
        result = []
        seen = set()
        
        for num in nums1:
            if num not in seen:
                for target in nums2:
                    if num == target:
                        result.append(num)
                        seen.add(num)
                        break
        
        return result

Complexity

• Time: O(n × m) where n and m are the lengths of the arrays
• Space: O(min(n, m)) for the result and seen set
• Notes: Simple but inefficient for large arrays, useful for understanding the problem