Skip to main content
Ace Hired
All coding problems

Intersection of Two Arrays

Easyarrays hashingHash setarraysetintersection

Maintained by Vikas D, software engineer

You receive two arrays of integers, nums1 and nums2. Your job is to find every value that is present in both arrays and report it.

The answer is a set of values, not a multiset. Even if a shared value appears many times across either input, it belongs in the result exactly once.

Any ordering of the result is accepted. A checker that ignores order will treat your answer as correct as long as the collection of distinct shared values matches.

An empty result is valid: when the two arrays share nothing, you return an empty array.

Examples

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

Only the value 2 lives in both arrays. The duplicate 2s collapse to a single entry in the answer.

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

9 and 4 appear in both arrays; 5, 8 do not. Order is free, so [4,9] would be equally valid.

Input: nums1 = [1,2,3], nums2 = [4,5,6]
Output: []

The two arrays have no value in common, so the intersection is empty.

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
  • Each value in the returned array must be unique
  • The result may be returned in any order

Visible test cases

  • intersection([1,2,2,1], [2,2]) == [2]
  • intersection([4,9,5], [9,4,9,8,4]) == [9,4]
  • intersection([1,2,3], [4,5,6]) == []
  • intersection([1,1,1], [1,1,1]) == [1]
  • intersection([7], [7]) == [7]

Hints

Hint 1

Membership testing is the core operation. What data structure answers 'is x in here?' in constant time?

Hint 2

Build a set from the first array. Then walk the second array and keep the values that the set contains.

Hint 3

To avoid emitting the same value twice, either dedupe the second array first or track which shared values you have already added.

Loading the editor...

Approaches

Brute force scan

Time O(n * m) where n and m are the two array lengths · Space O(min(n, m)) for the result and the added-value tracker

For every value in the first array, scan the entire second array to check whether it appears, then guard against adding a value more than once.

  1. Create an empty result and a structure to remember which values you already added.
  2. For each value v in nums1, linearly search nums2 for v.
  3. If found and v has not been added yet, append v and mark it as added.
  4. Return the collected values.

Hash set membership

Time O(n + m) · Space O(n + m) for the two sets in the worst case

Put the first array into a set so membership checks are constant time, then iterate the second array once, collecting each shared value the first time you see it.

  1. Build a set from nums1.
  2. Keep a second set, seen, to record values already placed in the result.
  3. Walk nums2; for each value, if it is in the first set and not yet in seen, add it to the result and to seen.
  4. Return the result.

Common mistakes

  • Returning duplicates: if a shared value repeats in nums2, a naive pass will emit it multiple times. Track what you have already added.
  • Including 0: zero is a valid value here, so do not treat a falsy element as 'missing' when checking membership.
  • Converting only one array to a set and forgetting the dedupe on the iteration side, which reintroduces repeats.
  • Mutating the input arrays in place when sorting for a two-pointer variant, which can surprise the caller if the originals are reused.

Follow-up variations

  • What if you must keep duplicates so the count of each shared value equals the smaller of its two frequencies (the 'Intersection II' variant)?
  • Both arrays are already sorted. Can you intersect them with O(1) extra space using two pointers?
  • One array is tiny and the other is enormous and streamed from disk. Which array do you load into the set, and why?
  • Generalize to k arrays: return values present in all of them.

Recommended problems

Build the rest of your prep