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.
Sort both arrays. With `nums1` being larger, try removing all combinations of two elements from `nums1`. Use a two-pointer technique to check if all elements align by adjusting all `nums1` elements by an integer `x`.
Sort `nums1` and `nums2`. Consider each potential element `x` as making the first of `nums2` equal to `nums1[i]`. This strategy helps find the required increment or decrement amount.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if in-place sorting is considered.
Use hashmaps to determine frequency differences between the elements of `nums1` and `nums2`. Calculate required changes per each element. The minimal `x` can be derived from aligning these differences.
Count each integer's frequency in both arrays using arrays as hashmaps. Compute potential `x` based on imbalances in frequencies.
Time Complexity: O(n).
Space Complexity: O(k), where k is the range of possible element values.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sorting and Two-Pointer Technique | Time Complexity: O(n log n) due to sorting. |
| Difference and Hashmap | Time Complexity: O(n). |
| Sorting + Enumeration + Two Pointers | — |
| 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 |
3132 & 3131 Find the Integer Added to Array II | 3131. Find the Integer Added to Array I • Aryan Mittal • 4,139 views views
Watch 5 more video solutions →Practice Find the Integer Added to Array II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor