MiddleCodeCommonNot answered yet
Elements of one sorted list not present in another
Given two non-decreasing integer sequences, return all elements of the first that do NOT appear in the second. filter([1,2,3], [3,4]) → [1,2]; filter([1,2,2], [2]) → [1].
Requirements:
- O(n + m) time, O(1) extra space beyond the output — a two-pointer merge, no binary search.
std::vector<int> filterSorted(const std::vector<int>& a, const std::vector<int>& b) {
// your code here
}Write the implementation.
Two-pointer merge: when a[i] < b[j], a[i] is absent from b, so emit it and advance i. When a[i] == b[j], skip a[i] (it is present). When a[i] > b[j], advance j. After b is exhausted, emit the rest of a. O(n + m), O(1).
- ✗Mishandling duplicates, e.g. dropping both copies of a value present once in b
- ✗Forgetting to emit the tail of a once b is exhausted
- ✗Failing to advance a pointer on equality, causing an infinite loop
- →How does duplicate handling change if b can contain repeated values?
- →Why is the two-pointer merge preferable to a hash set when both inputs are already sorted?
Contents
Task
Return the elements of the first sorted list absent from the second, by merge, in O(n + m).
Solution
std::vector<int> filterSorted(const std::vector<int>& a, const std::vector<int>& b) {
std::vector<int> out;
size_t i = 0, j = 0;
while (i < a.size()) {
if (j >= b.size() || a[i] < b[j]) out.push_back(a[i++]); // not in b
else if (a[i] == b[j]) ++i; // present in b
else ++j; // a[i] > b[j]
}
return out;
}Key points
- Comparing the fronts decides: emit, skip, or advance
j. - On equality advance only
i— otherwise duplicates break or it hangs. - O(n + m), no hashing or binary search.
Contents
