3132. Find the Integer Added to Array II
Description
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 thatnums1
can become equal tonums2
by removing two elements and addingx
to each element ofnums1
.
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|