MiddleCodeOccasionalNot answered yet
Common elements in every K-prefix of two arrays, in O(N)
Given two integer arrays of length N, for every K from 1 to N output the count of distinct values that appear in BOTH prefixes of length K. Duplicates within an array count once. Example: {1,2,3} and {2,1,3,1} → {0,1,2,3}.
Requirements:
- O(N) total time.
std::vector<int> commonInPrefixes(const std::vector<int>& a, const std::vector<int>& b) {
// your code here
}Write the implementation.
Advance both prefixes in lockstep with two hash sets seenA, seenB and a running common. When a new value from a is already in seenB, increment common; same for a new b value in seenA. Add it to its set. Record common after each step. One pass, O(N).
- ✗Rebuilding the prefix sets per K instead of extending them incrementally
- ✗Counting a duplicate value as a new intersection match more than once
- ✗Forgetting that the new element must be checked against the OTHER array's set
- →How does the answer change if intersection must respect multiplicity (min of counts)?
- →Why does the running counter stay correct when both prefixes grow together?
Contents
Task
For each K from 1 to N, count the distinct values common to both length-K prefixes.
Solution
std::vector<int> commonInPrefixes(const std::vector<int>& a, const std::vector<int>& b) {
std::unordered_set<int> seenA, seenB;
std::vector<int> result;
int common = 0;
for (size_t k = 0; k < a.size(); ++k) {
if (seenA.insert(a[k]).second && seenB.count(a[k])) ++common;
if (seenB.insert(b[k]).second && seenA.count(b[k])) ++common;
result.push_back(common);
}
return result;
}Key points
- Two sets and a
commoncounter grow with the prefixes. - A new element is checked against the other array's set, giving O(N).
insert(...).seconddiscards duplicates inside one array.
Contents
