10. Find Intersection of Two Arrays

Difficulty:EasyPattern:Hash Set LookupTime:O(n + m)Space:O(n)

Given two integer arrays nums1 and nums2, return an array of their unique intersection elements.

How It Works & Algorithmic Design

This problem uses Hash Set Intersection Filtering:

Set Population: Convert nums1 into a Hash Set set1. Hash Sets store only unique elements and provide $O(1)$ membership checks.
Filtering: Initialize a second empty result set resultSet.
Intersection Pass: Iterate through elements in nums2. For every number $x$, if set1.has(x), insert $x$ into resultSet.
Return: Convert resultSet back into an array list.

Why This Approach Works Best

Checking every element of nums2 against nums1 using nested loops takes $O(n \times m)$ time. Using a Hash Set reduces total execution time to linear $O(n + m)$ where $n$ and $m$ are the lengths of the two arrays.

Example Walkthrough

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

Arrays with duplicate entries.

Set 1 Construction: { 1, 2 }

Unique values from nums1.

Intersection Check: 2 in Set 1? Yes -> Add 2 to result.

Result set ensures uniqueness.

Output: [2]

Unique common elements.

Answer: Array intersection using Hash Sets

function intersection(nums1, nums2) {
  const set1 = new Set(nums1);
  const result = new Set();
  for (const num of nums2) {
    if (set1.has(num)) result.add(num);
  }
  return Array.from(result);
}

💡 Use Hash Sets to find common elements in linear time.

Key Takeaways

Hash Sets eliminate duplicate results automatically.
Linear time performance $O(n + m)$ using $O(1)$ set membership checks.
Space complexity is proportional to unique elements stored in memory ($O(n)$).