#349

Easy

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Intersection of Two Arrays

Find the intersection of two arrays while ensuring unique elements using efficient array scanning and hash lookups.

array hash table two pointers binary search sorting

Problem Statement

You are given two integer arrays, nums1 and nums2. Your task is to return an array containing the intersection of the two arrays, where each element is unique. The order of elements in the result does not matter, but duplicates should be eliminated in the final output.

For example, given nums1 = [1,2,2,1] and nums2 = [2,2], the correct result is [2]. Elements may appear multiple times in the input arrays, but the output should only contain the unique common elements.

Examples

Example 1

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

Output: [2]

Example details omitted.

Example 2

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

Output: [9,4]

[4,9] is also accepted.

Constraints

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

Solution Approach

Array Scanning and Hash Table Lookup

Scan through one of the arrays (nums1), adding each element to a hash table. Then, iterate through the second array (nums2) and check if the element exists in the hash table. This allows for quick lookups to find common elements, ensuring uniqueness by adding only elements found in both arrays.

Using Set for Uniqueness

Use a set to store the common elements found during the array scanning. Since sets automatically handle uniqueness, they are ideal for ensuring that only distinct elements are included in the final result, regardless of duplicates in the original arrays.

Optimized Space and Time Complexity

The time complexity of this approach is O(n + m), where n and m are the lengths of nums1 and nums2 respectively. The space complexity is O(n) due to the storage required for the hash table or set. This makes the solution efficient for inputs with large arrays.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(n)

The time complexity is O(n + m) because we perform one pass through nums1 and nums2. The space complexity is O(n) due to the need to store unique elements from nums1 in a hash table or set, which depends on the size of the first array.

What Interviewers Usually Probe

A successful solution will efficiently scan through both arrays and utilize a hash table or set for fast lookups.
The candidate should avoid unnecessary sorting or complex operations, focusing instead on the linear scan and hash table approach.
Watch for the candidate using inefficient solutions that don't ensure uniqueness or have higher time complexity than O(n + m).

Common Pitfalls or Variants

Common pitfalls

Failing to remove duplicates from the result, leading to incorrect output.
Using an inefficient solution with a higher time complexity, such as sorting the arrays, which would make the solution O(n log n).
Not utilizing hash tables or sets to efficiently check for intersections and uniqueness.

Follow-up variants

What if the arrays are already sorted? In this case, the two-pointer technique could be used to find intersections more efficiently.
What if the arrays contain only unique elements? The problem becomes simpler as you only need to find the intersection without needing to handle duplicates.
How would this solution change if the arrays were much larger? You could explore further optimizations or techniques, but the hash lookup method will still be efficient.

FAQ

What is the primary pattern for solving the Intersection of Two Arrays problem?

The primary pattern is array scanning combined with hash lookup, ensuring efficient identification of common elements while maintaining uniqueness.

How can I ensure my solution handles duplicates correctly?

Using a hash table or set will automatically remove duplicates, ensuring that each common element appears only once in the result.

Can this problem be solved with sorting?

While sorting could be used, it would increase the time complexity to O(n log n). The optimal approach is to use hash lookups for a linear-time solution.

What if I need to handle arrays of different sizes?

The solution still works efficiently regardless of the array sizes, as long as you use the linear scan and hash lookup approach.

What is the best way to handle larger inputs?

For larger inputs, maintaining the O(n + m) time complexity with hash lookups ensures optimal performance, as opposed to using slower methods like sorting.

terminal

Solution

Solution 1: Hash Table or Array

First, we use a hash table or an array $s$ of length $1001$ to record the elements that appear in the array $nums1$. Then, we iterate through each element in the array $nums2$. If an element $x$ is in $s$, we add $x$ to the answer and remove $x$ from $s$.

1

2

3

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

Continue Practicing

#350 intersection of two arrays ii #532 k diff pairs in an array #1346 check if n and its double exist