Java/C++ Clean Solution
Complexity\n- Time Complexity: O(n^2k)\n- Space Complexity: O(nn)\n\n\n# Code\nJava\nApproach-1\n\nclass Solution {\n    public int minimumAddedInteger(int[] nu
# Complexity\n- Time Complexity: $$O(n^2*k)$$\n- Space Complexity: $$O(n*n)$$\n\n\n# Code\n**Java**\n**`Approach-1`**\n```\nclass Solution {\n    public int minimumAddedInteger(int[] nums1, int[] nums2) {\n        Arrays.sort(nums1);\n        Arrays.sort(nums2);\n        int m = nums1.length;\n        int n = nums2.length;\n        int res = Integer.MAX_VALUE;\n        for(int i = 0; i<m;i++){\n            int diff = nums2[0] - nums1[i];\n            int count = 1, k = i+1, l=1;\n            while(k<m && l<n && (nums2[l] - nums1[k]) >= diff){\n                if(nums2[l] - nums1[k] == diff){\n                    count++;\n                    l++;\n                    k++;\n                }else{\n                    k++;\n                }\n            }\n            if(count == n){\n                res = Math.min(res,diff);\n            }\n        }\n        return res;\n    }\n}\n```\n**`Approach-2`**\n```\nclass Solution {\n\n    private boolean isPossibleMatch(int[] curr, int[] nums2) {\n        int i = 0, j = 0;\n        int step = 2;\n        while (i < curr.length && j < nums2.length) {\n            if (curr[i] == nums2[j]) {\n                i++;\n                j++;\n            } else {\n                i++;\n                step--;\n                if (step < 0) {\n                    return false;\n                }\n            }\n        }\n        return j == nums2.length && (i - j) <= 2;\n    }\n\n\n\n    public int minimumAddedInteger(int[] nums1, int[] nums2) {\n        Map<Integer, Integer> map = new HashMap<>();\n\n        Arrays.sort(nums1);\n        Arrays.sort(nums2);\n\n        for (int i = 0; i < nums1.length; i++) {\n            for (int j = 0; j < nums2.length; j++) {\n                int diff = nums2[j] - nums1[i];\n                map.put(diff, map.getOrDefault(diff, 0) + 1);\n            }\n        }\n\n        int res = Integer.MAX_VALUE;\n        for (int key : map.keySet()) {\n            int[] curr = new int[nums1.length];\n            for (int i = 0; i < nums1.length; i++) {\n                curr[i] = key + nums1[i];\n            }\n            Arrays.sort(curr);\n            if (isPossibleMatch(curr, nums2)) {\n                res = Math.min(res, key);\n            }\n        }\n        return res;\n    }\n}\n```\n**C++**\n```\nclass Solution {\n\n    private:\n        bool isPossibleMatch(vector<int>& nums1, vector<int>& nums2){\n            int i=0, j=0, step=2;\n            while(i<nums1.size() && j< nums2.size()){\n                if(nums1[i]==nums2[j]){\n                    i++;\n                    j++;\n                } else{\n                    i++;\n                    step--;\n                    if(step<0){\n                        return false;\n                    }\n                }\n            }\n            \n            return j==nums2.size() && (i-j)<=2;\n        }\n    \npublic:\n    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {\n        sort(nums1.begin(), nums1.end());\n        sort(nums2.begin(), nums2.end());\n        unordered_map<int, int> count;\n        int res = INT_MAX;\n        \n        for(int i=0; i<nums1.size(); i++){\n            for(int j=0; j<nums2.size(); j++){\n                int diff = nums2[j]-nums1[i];\n                count[diff]++;\n            }\n        }\n        \n        for(auto& [diff, cnt]:count){\n            vector<int> curr(nums1.size());\n            for(int i=0; i<nums1.size(); i++){\n                curr[i]=nums1[i]+diff;\n            }\n            sort(curr.begin(), curr.end());\n            if(isPossibleMatch(curr, nums2)){\n                res = min(res, diff);\n            }\n        }\n        return res;\n    }\n};\n```
['Array', 'Two Pointers', 'Prefix Sum', 'C++', 'Java']