A and B up to and including index i.

Approach

We can use sets to keep track of the numbers we have encountered so far in both permutations.
For each index i, we check how many elements in the current prefix of A are also in the current prefix of B.
This can be efficiently done using set intersection.

Code

[{"language":"Java","code":"class Solution {\n    public int[] findThePrefixCommonArray(int[] A, int[] B) {\n        int n = A.length;\n        int[] ans = new int[n];\n        Set<Integer> setA = new HashSet<>();\n        Set<Integer> setB = new HashSet<>();\n        \n        for (int i = 0; i < n; i++) {\n            setA.add(A[i]);\n            setB.add(B[i]);\n            int common = 0;\n            for (int a : setA) {\n                if (setB.contains(a)) {\n                    common++;\n                }\n            }\n            ans[i] = common;\n        }\n        return ans;\n    }\n}","lang":"java","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    public</span><span style=\"color:#D73A49;--shiki-dark:#F97583\"> int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">findThePrefixCommonArray</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">A</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">, </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">[] </span><span style=\"color:#E36209;--shiki-dark:#FFAB70\">B</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> n </span><span style=\"color:#D73A49;--shiki-dark:#F97583\">=</span><span style=\"co

Related Tags