Skip to main content
DSA patterns

Intersection of Two Arrays

easyArrays and hashingCiscoPalo Alto NetworksDell

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

Hint 1: Checking whether a value from 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

  1. Build a set set1 from every value in nums1.
  2. Create an empty result set.
  3. For each value x in nums2, if x is in set1, add it to the result set.
  4. 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

  • nums2 is much smaller than nums1 and 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 m is small relative to n (for example, m = 10 and n = 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 in result appeared 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."