[C++] O(n) solution
\nclass Solution {\npublic:\n    int minimumAddedInteger(vector<int>& a, vector<int>& b) {\n        int n = a.size();\n        vector<int> three(3, 1e9);\n     
```\nclass Solution {\npublic:\n    int minimumAddedInteger(vector<int>& a, vector<int>& b) {\n        int n = a.size();\n        vector<int> three(3, 1e9);\n        for(int i = 0; i < n; i++) {\n            if(a[i] < three[0]) {\n                three[2] = three[1];\n                three[1] = three[0];\n                three[0] = a[i];\n            } else if(a[i] < three[1]) {\n                three[2] = three[1];\n                three[1] = a[i];\n            } else if(a[i] < three[2]) {\n                three[2] = a[i];\n            }\n        }\n        \n        int mn = b[0];\n        for(int x : b) {\n            mn = min(mn, x);\n        }\n        \n        int ans = 1e9;\n        for(int i = 0; i < three.size(); i++) {\n            unordered_map<int, int> f;\n            for(int x : b) f[x]++;\n            \n            int diff = mn - three[i];\n            int count = 0;\n            for(int j = 0; j < a.size(); j++) {\n                if(f[a[j] + diff] == 0) count++;\n                else f[a[j] + diff]--;\n            }\n            if(count == 2) ans = min(ans, diff);\n        }\n        return ans;\n    }\n};\n```
[]