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 integerxthat 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.
Solutions
Solution 1: Sorting + Enumeration + Two Pointers
First, we sort the arrays $nums1$ and $nums2$. Since we need to remove two elements from $nums1$, we only need to consider the first three elements of $nums1$, denoted as $a_1, a_2, a_3$. We can enumerate the first element $b_1$ of $nums2$, then we can get $x = b_1 - a_i$, where $i \in {1, 2, 3}$. Then we can use the two pointers method to determine whether there exists an integer $x$ that makes $nums1$ and $nums2$ equal, and take the smallest $x$ that satisfies the condition.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(\log n)$. Where $n$ is the length of the array.