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 <= 200nums2.length == nums1.length - 20 <= nums1[i], nums2[i] <= 1000x such that nums1 can become equal to nums2 by removing two elements and adding x to each element of nums1.In #3132 Find the Integer Added to Array II, the goal is to determine the integer x that was added to elements of nums1 after removing exactly two elements so that the transformed array matches nums2. A key observation is that after sorting both arrays, the relative ordering of remaining elements must stay consistent.
A practical strategy is to sort both arrays and try possible alignments between the smallest elements. Because only two elements are removed from nums1, the first element of nums2 could correspond to one of the first few elements of nums1. For each candidate alignment, compute a potential value of x, then verify it using a two-pointer comparison while allowing up to two skipped elements in nums1.
If all remaining elements match after adding x, that candidate is valid. This approach efficiently prunes possibilities and avoids brute force enumeration.
The main cost comes from sorting and a linear verification pass.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Enumeration + Two Pointers | O(n log n) | O(1) |
| Verification Pass for Each Candidate | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Try all possibilities to remove 2 elements from <code>nums1</code>.
<code>x</code> should be equal to <code>min(nums2) - min(nums1)</code>, check it naively.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Sorting ensures both arrays can be compared in order, preserving relative differences. This allows a two-pointer technique to efficiently validate whether a single integer shift aligns the arrays after removing two elements.
Yes, problems like this are common in coding interviews because they test reasoning with sorting, pointer techniques, and edge case handling. Variants often appear in interviews at companies that emphasize algorithmic problem solving.
The optimal approach sorts both arrays and enumerates a few possible alignments for the first element. For each candidate difference value, a two-pointer check verifies whether the arrays can match after skipping two elements from nums1.
Arrays combined with sorting and two-pointer traversal are sufficient for this problem. No advanced data structures are required since the main task is alignment and verification of ordered elements.