O(n^2) --> O(n*logn) || C++
\n# Complexity\n- Time complexity: O(n^2)\n Add your time complexity here, e.g. O(n) \n\n- Space complexity: O(1)\n Add your space complexity here, e.g. O(n) \n
\n# Complexity\n- Time complexity: $$O(n^2)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    bool check(vector<int>& nums1, vector<int>& nums2, int k){\n        int count = 0, j = 0;\n        for(int i = 0; i < nums1.size() && j < nums2.size(); i++){\n            if(nums1[i] + k != nums2[j]) count++;\n            else j++;\n        }\n        if(count > 2) return 0;\n        return 1;\n    }\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        sort(nums1.begin(), nums1.end());\n        sort(nums2.begin(), nums2.end());\n        int minEle = INT_MAX;  \n        for(int i = 0; i < nums1.size(); i++){\n            int x = nums2[0] - nums1[i];\n            if(check(nums1, nums2, x)){\n                minEle = min(minEle, x);\n            }\n        }\n        return minEle;\n    }\n};\n```\n\n# Follow Up\n- Credits to $$@anishsingh0904$$\n- The code can be optimized further from $$O(n^2)$$ to $$O(nlogn)$$ by making a small change in the for loop.\n ```\nfor(int i = 0; i < 3; i++){\n    int x = nums2[0] - nums1[i];\n    if(check(nums1, nums2, x)){\n        minEle = min(minEle, x);\n    }    \n}\n```\n- We only have the possibility of choosing nums1[0], [1], or [2] because we can exclude any two of them.\n- Why can\'t we exclude more? Because if we were to choose nums1[3] or elements greater, then the **condition of obtaining identical vectors will be satisfied** but since `nums1[i + 1] > nums[i]` hence **the answer wouldn\'t be the *minimum* possible number as required in the problem.**\n- Hence we wouldn\'t be able to satisfy the mathematical requirements of nums2.
['Sorting', 'Simulation', 'C++']