Intersection of Two Arrays

Find the intersection of two arrays and return the result as an array.

Language Selection

Choose your preferred programming language

Showing: Python

Intersection of Two Arrays

Problem Statement

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Explanation: The intersection contains only unique elements.

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4] or [4,9]
Explanation: Both arrays contain 4 and 9.

Constraints

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

Approach 1: Hash Set (Optimal)

Algorithm

Use a hash set to store elements from one array, then check which elements from the second array exist in the set.

Steps:

Create a hash set from the smaller array
Iterate through the larger array
If element exists in set, add to result and remove from set (to avoid duplicates)
Return the result array

Implementation

Python:

def intersection(nums1, nums2):
    """
    Find intersection using hash set
    Time: O(m + n)
    Space: O(min(m, n))
    """
    # Use the smaller array for the set to optimize space
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1
    
    # Create set from smaller array
    nums1_set = set(nums1)
    result = []
    
    # Check elements in larger array
    for num in nums2:
        if num in nums1_set:
            result.append(num)
            nums1_set.remove(num)  # Remove to avoid duplicates
    
    return result

Java:

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        // Use the smaller array for the set to optimize space
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        
        Set<Integer> nums1Set = new HashSet<>();
        for (int num : nums1) {
            nums1Set.add(num);
        }
        
        List<Integer> result = new ArrayList<>();
        for (int num : nums2) {
            if (nums1Set.contains(num)) {
                result.add(num);
                nums1Set.remove(num);  // Remove to avoid duplicates
            }
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
}

Go:

func intersection(nums1 []int, nums2 []int) []int {
    // Use the smaller array for the set to optimize space
    if len(nums1) > len(nums2) {
        nums1, nums2 = nums2, nums1
    }
    
    // Create set from smaller array
    nums1Set := make(map[int]bool)
    for _, num := range nums1 {
        nums1Set[num] = true
    }
    
    var result []int
    // Check elements in larger array
    for _, num := range nums2 {
        if nums1Set[num] {
            result = append(result, num)
            delete(nums1Set, num)  // Remove to avoid duplicates
        }
    }
    
    return result
}

JavaScript:

function intersection(nums1, nums2) {
    // Use the smaller array for the set to optimize space
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }
    
    // Create set from smaller array
    const nums1Set = new Set(nums1);
    const result = [];
    
    // Check elements in larger array
    for (const num of nums2) {
        if (nums1Set.has(num)) {
            result.push(num);
            nums1Set.delete(num);  // Remove to avoid duplicates
        }
    }
    
    return result;
}

C#:

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        // Use the smaller array for the set to optimize space
        if (nums1.Length > nums2.Length) {
            (nums1, nums2) = (nums2, nums1);
        }
        
        var nums1Set = new HashSet<int>(nums1);
        var result = new List<int>();
        
        foreach (int num in nums2) {
            if (nums1Set.Contains(num)) {
                result.Add(num);
                nums1Set.Remove(num);  // Remove to avoid duplicates
            }
        }
        
        return result.ToArray();
    }
}

Complexity Analysis

Time Complexity: O(m + n) where m and n are the lengths of the arrays
Space Complexity: O(min(m, n)) for the hash set

Key Insights

Hash Set Approach: Most efficient for unsorted arrays with O(m + n) time complexity
Space Optimization: Use the smaller array for the hash set to minimize space usage
Duplicate Handling: Remove elements from set after adding to result to avoid duplicates
Set Operations: Built-in set intersection operations can simplify the code

Edge Cases

No Intersection: [1,2,3] and [4,5,6] → []
Complete Intersection: [1,2,3] and [1,2,3] → [1,2,3]
One Array Empty: [] and [1,2,3] → []
Duplicates: [1,2,2,1] and [2,2] → [2]

Follow-up Questions

Intersection with Duplicates: What if we want to keep duplicates in the result?
Multiple Arrays: How would you find intersection of k arrays?
Union: How would you find the union of two arrays?
Sorted Arrays: What if the arrays are already sorted?

Common Mistakes

Not Handling Duplicates: Forgetting to remove elements from set after adding
Wrong Space Optimization: Not using the smaller array for the set
Index Out of Bounds: Not checking array bounds properly

Interview Tips

Clarify Requirements: Ask about duplicates and order requirements
Discuss Approaches: Mention both hash set and two-pointer approaches
Optimize Space: Always consider using the smaller array for the set
Handle Edge Cases: Discuss empty arrays and no intersection cases