Watch 6 video solutions for Find the Integer Added to Array II, a medium level problem involving Array, Two Pointers, Sorting. This walkthrough by Aryan Mittal has 4,139 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.Problem Overview: You receive two arrays nums1 and nums2. Array nums2 was created by removing exactly two elements from nums1 and then adding the same integer x to every remaining value. Your task is to determine the integer x.
Approach 1: Sorting and Two-Pointer Technique (O(n log n) time, O(1) extra space)
Sort both arrays first. After sorting, the smallest value in nums2 must correspond to one of the first three elements in nums1, because at most two numbers could have been removed before it. For each candidate index i in the first three elements of nums1, compute a potential shift x = nums2[0] - nums1[i]. Then scan both arrays using two pointers. Compare nums1[j] + x with nums2[k]; if they match, move both pointers. Otherwise treat the element in nums1 as one of the removed values and advance only that pointer. If more than two elements must be skipped, the candidate x is invalid. The smallest valid x is the answer. This approach relies on sorting and a linear two pointers verification pass.
Approach 2: Difference Enumeration with HashMap (O(n log n) time, O(n) space)
Sort both arrays and enumerate possible values of x by pairing early elements of nums1 with nums2[0]. For each candidate shift, build a frequency map of nums2. Iterate through nums1, compute value = nums1[i] + x, and check whether it exists in the map. If it exists, decrease its frequency; otherwise treat that element as one of the two removed numbers. If more than two elements fail to match, discard the candidate. This approach uses a hash-based frequency map to validate matches and works well when you want explicit counting instead of pointer alignment.
Recommended for interviews: The sorting + two-pointer method is typically expected. It shows you understand how ordering simplifies alignment problems and reduces validation to a single linear scan. Enumerating only three candidates for x keeps the search space tiny, and the two-pointer check clearly models the "remove two elements" constraint.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Two Pointers | O(n log n) | O(1) | Best general solution; simple validation after sorting |
| Difference Enumeration + HashMap | O(n log n) | O(n) | Useful when verifying matches using frequency counts |