Back to solutions

Find the Difference of Two Arrays

EasyArrays

List values unique to each of two arrays.

Open problem
Constraints
  • 1 <= n1, n2 <= 1000
  • -1000 <= values <= 1000

Two hash sets

Time O(n1 + n2)Space O(n1 + n2)

Put each array into a set to drop duplicates and get O(1) membership. The first answer is every value in set A missing from set B; the second is every value in set B missing from set A.

Key terms
set difference:
The elements in one set that are not in another.
deduplicate:
Collapse repeated values so each appears once.
// onlyA = values in A not in B; onlyB = values in B not in A
for (int x : a) if (!b.count(x)) onlyA.push_back(x);
for (int x : b) if (!a.count(x)) onlyB.push_back(x);
Step by step
  1. Build set A from the first array and set B from the second.
  2. For the first list, keep each value of A that is not in B.
  3. For the second list, keep each value of B that is not in A.
  4. Output both lists (sorted here for a deterministic order).