How do you solve Intersection of Two Arrays on LeetCode?

Intersection of Two Arrays (LeetCode #349) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Using a set allows for efficient lookups.

What is the brute force solution for Intersection of Two Arrays?

The brute force approach for Intersection of Two Arrays is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each element of the first array against every element of the second array. If an element from the first array is found in the second array, we add it to the result, ensuring uniqueness. The optimal Optimal Solution approach improves this to O(n).

What are the interview tips for Intersection of Two Arrays?

Always consider edge cases, like empty arrays. Explain your thought process clearly during the interview. Practice writing clean and efficient code.

What are common mistakes when solving Intersection of Two Arrays?

Not checking for uniqueness before adding to the result. Confusing the use of arrays and sets.

#349

Intersection of Two Arrays

Easy

ArrayHash TableTwo PointersBinary SearchSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

Using a set allows us to efficiently track unique elements from both arrays. By converting one of the arrays to a set, we can check for intersections in constant time.

⚙️

Algorithm

4 steps

1Step 1: Convert nums1 into a set to eliminate duplicates.
2Step 2: Initialize an empty result list.
3Step 3: For each element in nums2, check if it exists in the set created from nums1.
4Step 4: If it exists, add it to the result list.

solution.py7 lines

1def intersection(nums1, nums2):
2    set_nums1 = set(nums1)
3    result = []
4    for num in nums2:
5        if num in set_nums1 and num not in result:
6            result.append(num)
7    return result

ℹ

Complexity note: The time complexity is O(n) because we traverse nums1 to create a set and then traverse nums2 to find intersections. The space complexity is O(n) due to the storage of the set.

1Using a set allows for efficient lookups.
2Ensuring uniqueness in the result can be done with a set.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.