2657: Find-the-Prefix-Common-Array-of-Two-Arrays
Medium

table of contents

This question can be trivialised if you initialise a frequency array to keep track of which numbers have been seen in A and B.

My algorithm just initalises an array, frequency, of size n, and at every index, we increment frequency[A[i]-1] and frequency[B[i]-1]. If any value in frequency is equal to 2, then we know we have seen both copies of it, so we can increment the counter of common numbers present at or before index i.indexi

code

class Solution {
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        vector<int> frequency (A.size(), 0);
        vector<int> ans;
        ++frequency[A[0]-1];
        ++frequency[B[0]-1];
        if (frequency[A[0]-1] == 2) ans.push_back(1);
        else ans.push_back(0);

        for (int i = 1; i < A.size(); ++i) {
            int temp = ans[i-1];
            ++frequency[A[i]-1];
            if (frequency[A[i]-1]==2) ++temp;
            ++frequency[B[i]-1];
            if (frequency[B[i]-1]==2) ++temp;
            ans.push_back(temp);
        }
        return ans;
    }
};

complexity