Freq Count & find first 3 min  with time O(n)||9ms Beats100%
Intuition\n Describe your first thoughts on how to solve this problem. \nLet min2=min(nums2), Let z0, z1, z2 be the first 3 min for nums1. The problem is to fin
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nLet `min2=min(nums2)`, Let z0, z1, z2 be the first 3 min for `nums1`. The problem is to find x. 3 cases to discuss: \n1. x=min2-z2.\n2. x=min2-z1.\n3. x=min2-z0.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Construct the arrays `freq1`, `freq2` to store the occurencies of the numbers in `nums1` & `nums2`. TC: O(n)\n2. Use nth_element partial sort to find the first 3 mins for `nums1`. TC=O(n)\n3. Begin with x=min2-z2 to check whether there is any missing. If not, the answer is x; otherwise to it must be either case of the following 2. TC=O(n)\n4. Suppose x=min2-z1. The answer is x $\\iff$ there is exactly 1 missing. Otherwise x=min2-z0. TC: O(n)\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n $$O(n)$$\n# Code||9ms Beats100%\n```\n#pragma GCC optimize("O3", "unroll-loops")\nclass Solution {\npublic:\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        int n=nums1.size(), freq1[1001]={0}, freq2[1001]={0};\n        int min2=INT_MAX;\n        for (int a : nums2){\n            min2=min(min2, a);\n            freq2[a]++;\n        }\n        for (int a : nums1) freq1[a]++;\n        nth_element(nums1.begin(), nums1.begin()+2, nums1.end());\n        if (nums1[0]>nums1[1]) swap(nums1[0], nums1[1]);\n    //    cout<<"min2="<<min2<<endl;\n\n        int missing=0, x=min2-nums1[2];\n        freq1[nums1[0]]--, freq1[nums1[1]]--;\n        for(int i=2; i<n; i++){\n            int y=nums1[i];\n            if (freq1[y]!=freq2[x+y]){\n            //    cout<<y<<",f2[x+y]="<<freq2[x+y]<<", f1[y]="<<freq1[y]<<endl;\n                missing++;\n                break;\n            }\n        }\n    //    cout<<"missing="<<missing<<", x="<<x<<"\\n----\\n";\n        if (missing==0) return x;\n        freq1[nums1[1]]++; // readding 1 nums1[1]\n        missing=0, x=min2-nums1[1];\n        for(int i=1; i<n; i++){\n            int y=nums1[i];\n            if (freq1[y]!=freq2[x+y]){\n            //    cout<<y<<",f2[x+y]="<<freq2[x+y]<<", f1[y]="<<freq1[y]<<endl;\n                freq1[y]--;// take 1 y away from nums1\n                missing++;\n                if(missing>1) break;\n            }\n        }\n    //    cout<<"missing="<<missing<<", x="<<x<<endl;\n        if (missing<=1) return x;\n        return min2-nums1[0];\n    }\n};\n\n\nauto init = []()\n{ \n    ios::sync_with_stdio(0);\n    cin.tie(0);\n    cout.tie(0);\n    return \'c\';\n}();\n```
['Array', 'C++']