Simple O(n log(n)) C++ solution
Intuition\nIf we sorted both arrays, we would find that for every element in nums2 with index i, its coresponding element in nums1 for the optimal solution is e
# Intuition\nIf we sorted both arrays, we would find that for every element in `nums2` with index i, its coresponding element in `nums1` for the optimal solution is either at index i, i+1 or i+2.\nThis because there are only two extra numbers in `nums1`.\n\n# Approach\n- 1- We sort both arrays in ascending order.\n- 2- We evaluate 3 possible solutions x1, x2 and x3 by getting the  difference between `nums2[0]` and ( `nums1[0]`, `nums1[1]` and `nums1[2]` )\nrespectively.\n\n- 3- We check the validity of each solution.\n\n- 4- We return the least valid solution as our optimal solution.\n\n# Complexity\n- Time complexity: `O(nlog(n))`\n\n- Space complexity: `O(1)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```cpp []\nclass Solution {\n    bool valid(vector<int>& nums1, vector<int>& nums2, int x)\n    {\n        int i{}, skip{};\n\n        while(i<nums2.size())\n        {\n            if(skip==3)\n                return false;\n            \n            if(nums2[i]==nums1[i+skip]+x)\n            {\n                ++i;\n            }\n            else\n            {\n                ++skip;\n            }\n \n        }\n\n        return true;\n    }\npublic:\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        sort(nums1.begin(), nums1.end());\n        sort(nums2.begin(), nums2.end());\n\n        int x1=(valid(nums1,nums2,nums2[0]-nums1[0]))?nums2[0]-nums1[0]:INT_MAX;\n\n        int x2=(valid(nums1,nums2,nums2[0]-nums1[1]))?nums2[0]-nums1[1]:INT_MAX;\n\n        int x3=(valid(nums1,nums2,nums2[0]-nums1[2]))?nums2[0]-nums1[2]:INT_MAX;\n\n\n        return min(x1,min(x2,x3));\n    }\n};\n```
['C++']