Find the Difference of Two Arrays
Problem
Given two arrays a and b, return a pair of lists: distinct values present in a but not in b, and distinct values present in b but not in a. Build a hash set from each array and filter against the other.
a = [1, 2, 3], b = [2, 4, 6][[1, 3], [4, 6]]def find_difference(a, b):
A, B = set(a), set(b)
only_a = list(A - B)
only_b = list(B - A)
return [only_a, only_b]function findDifference(a, b) {
const A = new Set(a), B = new Set(b);
const onlyA = [...A].filter(x => !B.has(x));
const onlyB = [...B].filter(x => !A.has(x));
return [onlyA, onlyB];
}class Solution {
public List<List<Integer>> findDifference(int[] a, int[] b) {
Set<Integer> A = new HashSet<>(), B = new HashSet<>();
for (int x : a) A.add(x);
for (int x : b) B.add(x);
List<Integer> onlyA = new ArrayList<>();
for (int x : A) if (!B.contains(x)) onlyA.add(x);
List<Integer> onlyB = new ArrayList<>();
for (int x : B) if (!A.contains(x)) onlyB.add(x);
return List.of(onlyA, onlyB);
}
}vector<vector<int>> findDifference(vector<int>& a, vector<int>& b) {
unordered_set<int> A(a.begin(), a.end()), B(b.begin(), b.end());
vector<int> onlyA;
for (int x : A) if (!B.count(x)) onlyA.push_back(x);
vector<int> onlyB;
for (int x : B) if (!A.count(x)) onlyB.push_back(x);
return { onlyA, onlyB };
}Explanation
We need two lists: the distinct values in a that are missing from b, and the distinct values in b that are missing from a. The word "distinct" is the hint to use hash sets.
First we turn each array into a set, A and B. Converting to a set both removes duplicates and gives us instant membership checks.
Then it is just two set differences. A - B keeps the values in A not present in B, and B - A keeps the values in B not present in A. We return them as a pair of lists.
Example: a = [1, 2, 3], b = [2, 4, 6]. The value 2 sits in both sets, so it is excluded from both halves. We get [[1, 3], [4, 6]].
Because every lookup against a set is constant time, the whole thing runs in time proportional to the combined size of the two arrays.