How do you solve Intersection of Two Arrays?

Convert nums1 to a set for O(1) membership checks. Iterate over the unique elements of nums2, and for each element, check if it exists in nums1's set. If yes, append it to the result list. Return the result list containing unique intersection elements.

What pattern does Intersection of Two Arrays use?

The Pattern: Hash Maps (Set Membership for Intersection) The Heuristic: Use a hash set to store one array's elements for O(1) membership queries, then iterate over the unique elements of the other array to efficiently build the intersection without duplicates.

Intersection of Two Arrays | Hash Maps

Q: What is the time complexity of Intersection of Two Arrays?

O(n + m). Converting nums1 to a set takes O(n), iterating over the unique elements of nums2 takes O(m), and each membership check is O(1) on average, resulting in O(n + m) total time.

Problem

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.

1 ≤ nums1.length, nums2.length ≤ 10⁴
−10⁹ ≤ nums1[i], nums2[i] ≤ 10⁹

Example

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

Output: [2]

A brute-force approach would check every element in nums1 against every element in nums2, resulting in O(n*m) time complexity. Instead, by converting nums1 to a set, we enable O(1) average-time membership checks. Iterating over the unique elements of nums2 and checking membership in nums1's set allows us to build the intersection efficiently. The critical moment is when the algorithm encounters '2' in nums2's unique set and confirms it exists in nums1's set, adding it to the result. This approach guarantees uniqueness and avoids duplicates naturally.

Approach

Straightforward Solution

A naive approach uses nested loops to check each element of nums1 against every element of nums2, resulting in O(n*m) time complexity, which is inefficient for large inputs.

Core Observation

The intersection requires identifying elements common to both arrays, but only once each. Sets provide O(1) average-time membership checks and inherently store unique elements, making them ideal for this problem.

Path to Optimal

Preview

Recognizing that uniqueness and membership checks are central, converting nums1 to a set allows constant-time lookups. Iterating over the unique elements of nums2 (also converted to a set) and checking for membership in nums1's set yields the intersection elements efficiently…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Convert nums1 to a set for O(1) membership checks. Iterate over the unique elements of nums2, and for each element, check if it exists in nums1's set…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n + m)

Converting nums1 to a set takes O(n), iterating over the unique elements of nums2 takes O(m), and each membership check is O(1) on average, resulting in O(n + m) total time.

Space

O(n)

The set storing nums1's elements requires O(n) auxiliary space, proportional to the size of nums1. The output list uses space proportional to the intersection size, which is unavoidable.

Solution

Python

1class Solution:
  def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
      nums1_set = set(nums1)
      unique_intersection = []

      for num in set(nums2):
          if num in nums1_set:
              unique_intersection.append(num)

      return unique_intersection

Step-by-Step Solution

1

Build a Set from the First Array to Enable Fast Membership Checks

3nums1_set = set(nums1)
4unique_intersection = []

Objective

To create a hash set from nums1 that allows constant-time membership queries.

Key Insight

Converting nums1 into a set removes duplicates and enables O(1) average-time membership checks. This transforms the problem from a costly nested search into a simple lookup operation, which is the foundation for an efficient intersection algorithm.

Interview Quick-Check

Core Logic

Using a set for nums1 allows the algorithm to check if an element from nums2 exists in nums1 in constant time.

Common Pitfalls & Bugs

Failing to convert nums1 to a set results in O(n*m) time complexity due to repeated linear searches.

2

Iterate Over Unique Elements of the Second Array to Collect Intersection

To iterate through the unique elements of nums2 and collect those present in nums1's set.

3

Return the List of Unique Intersection Elements

To return the collected list of unique intersection elements as the final result.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 7 Critical

if num in nums1_set:

Check if the current element from nums2 exists in nums1's set.

This membership check filters only elements common to both arrays, which is the fundamental operation for computing the intersection.

Line 3 Critical

nums1_set = set(nums1)

Convert nums1 into a set to enable O(1) membership checks.

This conversion is the key optimization that transforms membership queries from O(n) linear scans to O(1) average-time lookups, drastically improving efficiency.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does converting nums1 to a set improve the efficiency of finding the intersection?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Intersection of Two Arrays from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Intersection of Two Arrays drill

or drill a free problem

1	`class Solution:`
2	`def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:`
3	`nums1_set = set(nums1)`
4	`unique_intersection = []`
5
6	`for num in set(nums2):`
7	`if num in nums1_set:`
8	`unique_intersection.append(num)`
9
10	`return unique_intersection`