Intersection of Two Arrays
Problem statement
You get two integer lists, nums1 and nums2. Return the values that appear in both lists, with no duplicates in the result. You can return the values in any order.
This is the same shape as comparing two inventories — for example, finding which hostnames or instance IDs show up in both a "currently running" list and a "should be running" list.
Examples
Example 1
Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: [2]
Explanation: The only value present in both lists is 2. Even though it repeats in each list, it appears only once in the result.
Example 2
Input: nums1 = [4, 9, 5], nums2 = [9, 4, 9, 8, 4]
Output: [4, 9]
Explanation: 4 and 9 both appear in nums1 and nums2; 5 and 8 don't appear in both lists. The order doesn't matter — [9, 4] is just as valid — the result below is shown sorted for a consistent, checkable output.
Hints
nums1 is anywhere in nums2 by scanning nums2 each time works, but how much total work is that if both lists are long?Approach
Optimal: Hash sets
Intuition
Turn one list into a set so "does this value exist in nums1?" becomes an instant check instead of a scan. Then walk through nums2 once: any value that's in the set is part of the intersection. Using a set for the result too takes care of duplicates automatically, since a set can never hold the same value twice.
This drops both the nested-loop cost of the brute force and the sorting cost of the two-pointer approach — the trade is extra memory for the sets, which is worth it whenever the lists are large or arrive unsorted.
Steps
- Build a set
set1from every value innums1. - Create an empty result set.
- For each value
xinnums2, ifxis inset1, add it to the result set. - Convert the result set to a list and return it.
Dry run
nums1 = [4, 9, 5] → set1 = {4, 9, 5}
nums2 = [9, 4, 9, 8, 4]
| x from nums2 | in set1? | result after |
|---|---|---|
| 9 | yes | {9} |
| 4 | yes | {9, 4} |
| 9 | yes (already in result) | {9, 4} |
| 8 | no | {9, 4} |
| 4 | yes (already in result) | {9, 4} |
Result: {9, 4} — shown sorted as [4, 9], though any order is valid.
Edge case: if nums1 is empty, set1 is empty, so nothing from nums2 can ever match — the result is correctly empty.
Complexity
Time O(n + m) - Building a set from `nums1` costs O(n); checking every value of `nums2` against that set costs O(m), since each lookup is O(1) on average.
Space O(n + m) - in the worst case — one set to hold the distinct values of `nums1`, plus a second set (or list) for the result, depending on how many shared values are found.
class Solution:
def intersection(self, nums1: list[int], nums2: list[int]) -> list[int]:
return list(set(nums1) & set(nums2))
if __name__ == "__main__":
print(sorted(Solution().intersection([1, 2, 2, 1], [2, 2]))) # [2]
print(sorted(Solution().intersection([4, 9, 5], [9, 4, 9, 8, 4]))) # [4, 9]RecapThe whole problem in a few lines, for the night before
- Spot it: values that appear in both arrays, each reported once
- Idea: put one array in a set, walk the other, and collect values found in the set (remove them so they are not repeated)
- Cost: O(n + m) time, O(n) space
- Trap: the result must hold unique values, so duplicates in the input must not repeat in the output
Interview follow-ups
nums2is much smaller thannums1and both are already sorted. Can you do better than O(n + m)?Yes — for each value in the smaller list, binary search for it in the larger one instead of walking both with two pointers. That costs O(m log n), which beats O(n + m) when
mis small relative ton(for example,m = 10andn = 1,000,000).What if you needed the intersection of three or more lists, not just two?
Build a set from the first list, then repeatedly intersect it with the set of each following list (
result &= set(next_list)). After processing all lists, whatever remains inresultappeared in every one of them. The total cost is proportional to the sum of all the lists' lengths.
Frequently asked questions
It avoids the O(n log n) and O(m log m) sorting cost entirely, dropping to a flat O(n + m). Sorting is still a reasonable answer, especially if you'd want the values in order anyway or memory for a second set is a real constraint, but hash sets are the faster general-purpose choice here.
Then the two-pointer approach becomes the natural choice — there's no sorting cost left to pay, so it's O(n + m) time and doesn't need to build any sets at all, only O(1) extra space beyond the result.
Every approach here uses a set — either directly (hash set) or indirectly (checking "already the last value added" in the sorted two-pointer walk, or a seen_result set in the brute force) — specifically to make sure each shared value is only recorded once, no matter how many times it repeats in either input list.
Comparing two lists for overlap is the backbone of reconciliation tasks: which hosts are in both the inventory and the monitoring system, which tags exist on both a resource and its policy, which packages are installed on two different machines. The hash-set version is usually exactly what's expected once the interviewer says "make it fast."
