JuniorCodeCommonNot answered yet
Find elements present in only one of two arrays (symmetric difference) using STL
Given two integer arrays, return the elements that appear in exactly one of them (the symmetric difference). Use the STL.
Requirements:
- Solve it with standard-library algorithms, not a hand-rolled comparison loop.
- Returned values should be unique with respect to set membership.
#include <vector>
std::vector<int> symmetricDifference(std::vector<int> a, std::vector<int> b) {
// your code here
}Write the implementation.
Sort both arrays, then use std::set_symmetric_difference to get elements that appear in exactly one of the two arrays. Alternatively, insert one array into an unordered_set and check the other — O(n+m) average with O(n) extra space.
- ✗Forgetting that
std::set_symmetric_differencerequires sorted input - ✗Not using
std::back_inserteras the output iterator - ✗Confusing symmetric difference (in exactly one) with difference (in first but not second)
- →What is the time complexity of
std::set_symmetric_difference? - →How would you find the intersection of two arrays using STL?
Contents
Task
Find elements that exist in exactly one of two arrays (symmetric difference).
Solution
// STL approach
std::vector<int> symmDiff(std::vector<int> a, std::vector<int> b) {
std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end());
std::vector<int> result;
std::set_symmetric_difference(a.begin(), a.end(), b.begin(), b.end(),
std::back_inserter(result));
return result;
}Key points
std::set_symmetric_differencerequires sorted input.- Hash-set approach is O(n+m) average but unordered output.
Contents
