Find the Integer Added to Array II
Source: leetcode
Difficulty: Medium
Tags: array, two-pointers, sorting, enumeration

You are given two integer arrays `nums1` and `nums2`.


From `nums1` two elements have been removed, and all other elements have been increased (or decreased in the case of negative) by an integer, represented by the variable `x`.


As a result, `nums1` becomes **equal** to `nums2`. Two arrays are considered **equal** when they contain the same integers with the same frequencies.


Return the **minimum** possible integer`x`that achieves this equivalence.


 


**Example 1:**



**Input:** nums1 \= \[4,20,16,12,8], nums2 \= \[14,18,10]


**Output:** \-2


**Explanation:**


After removing elements at indices `[0,4]` and adding \-2, `nums1` becomes `[18,14,10]`.



**Example 2:**



**Input:** nums1 \= \[3,5,5,3], nums2 \= \[7,7]


**Output:** 2


**Explanation:**


After removing elements at indices `[0,3]` and adding 2, `nums1` becomes `[7,7]`.



 


**Constraints:**


- `3 <= nums1.length <= 200`
- `nums2.length == nums1.length - 2`
- `0 <= nums1[i], nums2[i] <= 1000`
- The test cases are generated in a way that there is an integer `x` such that `nums1` can become equal to `nums2` by removing two elements and adding `x` to each element of `nums1`.




C++ solution:
class Solution {
public:
    int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
        int m1 = 0, m2 = 0;
        unordered_map<int,int> mp1,mp2;
        for(int i:nums1){
            m1 = max(m1, i);
            mp1[i]++;
        }
        for(int i:nums2){
            m2 = max(m2, i);
            mp2[i]++;
        }

        int ans = max(m1,m2);

        for(int t=0;t<3;t++){
            int diff = m2-m1;
            bool flag = true;
            for(auto &x:mp2){
                if(mp1[x.first-diff]<x.second){
                    flag = false;
                    break;
                }
            }
            if(flag)
                ans = min(ans, diff);
            mp1[m1]--;
            m1 = 0;
            for(auto &x:mp1){
                if(x.second)
                    m1 = max(m1, x.first);
            }
        }
        return ans;
    }
};

Go solution:
func minimumAddedInteger(nums1 []int, nums2 []int) int {
    slices.Sort(nums1)
    slices.Sort(nums2)
    
    ans := math.MaxInt
    for i := 0; i <= 2; i++ {
        interval := nums2[0] - nums1[i]
        skiped := i
        
        for j := 0; j < len(nums2) && skiped <= 2; j++ {
            n1 := nums2[j] - interval
            
            if n1 != nums1[j + skiped] {
                skiped++
                j--
            }
        }
        
        if skiped <= 2 {
            ans = interval
        }
    }
    
    return ans
}

Java solution:
class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int n= nums1.length, ans = Integer.MAX_VALUE;
        int [] diffs = {nums2[0]-nums1[0],nums2[0]-nums1[1],nums2[0]-nums1[2]};
        for(int diff : diffs) {
            int j=0, deleted=0;
            for(int i=0;i<n && j<n-2 ;i++){
                if(nums2[j]-nums1[i] != diff){
                    deleted++;
                }
                else {
                    j++;
                }
                if( deleted>2 ){
                    break;
                }
            }
            if(j==n-2){
                ans = Math.min(ans,diff);
            }
        }
        return ans;
    }
}

JavaScript solution:
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minimumAddedInteger = function(nums1, nums2) {
    const m = nums1.length;
    const n = nums2.length;
    nums2.sort((a,b)=>a-b);
    nums1.sort((a,b)=>a-b);
    if(n===1) {
        return nums2[0] - nums1[m-1];
    }
    console.log(nums1, nums2);
    for(let i = 0; i<m; i++){
        for(let j = i+1; j<m; j++) {
            // delete i & j
            const first1 = i === 0 ? (j === 1 ? 2 : 1) : 0;
            const diff = nums2[0] - nums1[first1];
            // check
            let flag = true;
            let q = 0;
            for(let p = 0; p<m; p++) {
                if(p===j || p===i){
                    continue;
                }
                if(nums2[q] !== nums1[p]+diff) {
                    flag = false;
                    break;
                }
                q++;
            }
            if(flag) {
                return diff;
            }
        }
    }
};

Python solution:
class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        nums1, nums2 = sorted(nums1), sorted(nums2)
        diffs = [nums1[0] - nums2[0], nums1[1] - nums2[0], nums1[2] - nums2[0]]
        ret = float("-inf")
        for diff in diffs:
            cand = True
            lo = 0
            for num2 in nums2:
                num1 = num2 + diff
                idx = bisect.bisect_left(nums1, num1, lo=lo)
                if idx >= len(nums1) or nums1[idx] != num1:
                    cand = False
                    break
                lo = idx + 1
            if cand:
                ret = max(ret, diff)
        return -ret
        # time: O(nlgn)
        # space: O(n)

        # min2 = min(nums2)
        # c, b, a = [min2 - val for val in heapq.nsmallest(3, nums1)]
        # nums2 = Counter(nums2)
        # for x in (a, b, c):
        #     if nums2 <= Counter(val + x for val in nums1):
        #         return x
        # # time: O(n)
        # # space: O(n)

Ruby solution:
def minimum_added_integer(nums1, nums2)
    nums1 = nums1.sort
    nums2 = nums2.sort
    diffs = (0..2).map { |i| nums1[i] - nums2[0] }.uniq
    valid_diffs = []
    diffs.each do |diff|
        i = 0
        skipped = 0
        valid = true
        nums2.each do |num|
            target = num + diff
            while i < nums1.size && nums1[i] < target
                skipped += 1
                i += 1
            end
            if i < nums1.size && nums1[i] == target
                i += 1
            else
                valid = false
                break
            end
        end
        remaining = nums1.size - i
        total_skipped = skipped + remaining
        valid &&= total_skipped <= 2
        valid_diffs << diff if valid
    end
    valid_diffs.empty? ? 0 : -valid_diffs.max
end