Optimal Solution | Check Only 3 Differences | O(NlogN) | C++ | Java
Intuition\nSort both the arrays to match the smallest number\nSince only 2 elements are deleted from nums1, Its guaranteed that nums2[0] must match with one of 
# Intuition\nSort both the arrays to match the smallest number\nSince only 2 elements are deleted from `nums1`, Its guaranteed that `nums2[0]` must match with one of `nums1[0]` ,`nums1[1]` and `nums1[2]`.\nHence the possible differences we can have are\n1. `nums2[0]`-`nums1[0]`\n2. `nums2[0]`-`nums1[1]`\n3. `nums2[0]`-`nums1[2]`\n\n\n# Approach\n- Sort both `nums1` and `nums2`.\n- Computed the 3 possible `diffs` as per intuition.\n- Iterate through these 3 possible `diffs` we have computed  and check whether all elements have same diff with maximum of 2 elements not satisfying the `diff`.\n- Return the minimum of the valid `diff` \n\n# Complexity\n- Time complexity:\n$$O(sorting)$$\n\n- Space complexity:\n$$O(sorting)$$ \n\n\n```java []\nclass Solution {\n    public int minimumAddedInteger(int[] nums1, int[] nums2) {\n        Arrays.sort(nums1);\n        Arrays.sort(nums2);\n        int n= nums1.length, ans = Integer.MAX_VALUE;\n        int [] diffs = {nums2[0]-nums1[0],nums2[0]-nums1[1],nums2[0]-nums1[2]};\n        for(int diff : diffs) {\n            int j=0, deleted=0;\n            for(int i=0;i<n && j<n-2 ;i++){\n                if(nums2[j]-nums1[i] != diff){\n                    deleted++;\n                }\n                else {\n                    j++;\n                }\n                if( deleted>2 ){\n                    break;\n                }\n            }\n            if(j==n-2){\n                ans = Math.min(ans,diff);\n            }\n        }\n        return ans;\n    }\n}\n```\n```c++ []\nclass Solution {\npublic:\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        sort(nums1.begin(),nums1.end());\n        sort(nums2.begin(),nums2.end());\n        int n= nums1.size(), ans = INT_MAX;\n        vector<int>diffs = {nums2[0]-nums1[0],nums2[0]-nums1[1],nums2[0]-nums1[2]};\n        for(auto diff : diffs) {\n            int j=0, deleted=0;\n            for(int i=0;i<n && j<n-2 ;i++){\n                if(nums2[j]-nums1[i] != diff){\n                    deleted++;\n                }\n                else {\n                    j++;\n                }\n                if( deleted > 2 ){\n                    break;\n                }\n            }\n            if(j==n-2){\n                ans = min(ans,diff);\n            }\n        }\n        return ans;\n        \n    }\n};\n```\n\n
['Greedy', 'Sorting', 'C++', 'Java']