LeetCode 3132 - Find the Integer Added to Array II
We are given two integer arrays, nums1 and nums2. The array nums2 was created from nums1 using two operations: 1. Remove exactly two elements from nums1. 2. Add the same integer x to every remaining element.
Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Sorting, Enumeration
Solution
Problem Understanding
We are given two integer arrays, nums1 and nums2. The array nums2 was created from nums1 using two operations:
- Remove exactly two elements from
nums1. - Add the same integer
xto every remaining element.
After these operations, the resulting multiset of values becomes exactly equal to nums2. The order of elements does not matter, only the values and their frequencies matter.
Our task is to determine the minimum possible value of x.
The important detail is that two elements are removed before the addition operation. This means we are not trying to align every element from nums1 with nums2. Instead, we only need to find a subset of nums1 of size len(nums2) such that after adding some integer x, it matches nums2.
The constraints are relatively small:
nums1.length <= 200nums2.length == nums1.length - 2
Because the input size is small, we can afford some enumeration or quadratic checks. However, we still want a clean and efficient solution.
A few important observations come from the guarantees:
- The problem guarantees that at least one valid
xexists. - Duplicates may appear in both arrays.
xmay be negative.- The arrays are unordered, so sorting is extremely useful.
Potential edge cases include:
- Arrays containing many duplicate values.
- Negative values of
x. - Multiple possible valid values of
x, where we must return the minimum. - Situations where the removed elements are the smallest or largest values.
Approaches
Brute Force Approach
A straightforward brute force solution would try every possible pair of removed elements from nums1.
For each pair:
- Remove those two elements.
- Compare the remaining elements against
nums2. - Compute the required difference
x. - Verify whether every transformed element matches
nums2.
Since nums1 has at most 200 elements, there are:
$$\binom{200}{2} = 19900$$
possible removals.
For each removal, we may sort or compare arrays of size up to 198, giving a complexity around O(n^3 log n) depending on implementation.
This works for the constraints, but it is unnecessarily expensive and more complicated than needed.
Key Insight
After sorting both arrays, the smallest remaining element in nums1 must align with the smallest element in nums2.
Suppose:
ais the smallest surviving element fromnums1bis the smallest element innums2
Then:
$$x = b - a$$
Since exactly two elements are removed, the smallest surviving element in sorted nums1 must be one of:
nums1[0]nums1[1]nums1[2]
This is the critical observation.
Why only these three?
Because removing exactly two elements can eliminate at most the first two elements of the sorted array. Therefore, the first surviving element must appear within the first three positions.
So we only need to try three candidate values for x:
$$x = nums2[0] - nums1[i]$$
for i in {0,1,2}.
For each candidate x, we check whether we can transform nums1 into nums2 while skipping exactly two elements.
This dramatically reduces the search space.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n³ log n) | O(n) | Try every pair of removed elements |
| Optimal | O(n log n) | O(1) or O(log n) | Only three candidate values of x need checking |
Algorithm Walkthrough
Step 1: Sort both arrays
We sort nums1 and nums2.
Sorting allows us to compare elements in order and use a two pointer matching process.
Step 2: Generate candidate values of x
The smallest surviving element in nums1 must be one of the first three elements after sorting.
For each index i in [0, 1, 2]:
$$x = nums2[0] - nums1[i]$$
Each of these values is a possible answer.
Step 3: Validate a candidate x
For a chosen candidate x, we try to match elements from nums1 to nums2.
We use two pointers:
ifornums1jfornums2
We scan through nums1.
If:
$$nums1[i] + x = nums2[j]$$
then the element matches and both pointers move forward.
Otherwise, we treat nums1[i] as one of the removed elements and skip it.
We are allowed to skip at most two elements.
Step 4: Check whether matching succeeds
If we successfully match all elements of nums2, then the candidate x is valid.
Since we try candidates in increasing order, or simply take the minimum valid candidate, we obtain the answer.
Why it works
The key invariant is that after sorting, relative order is preserved between matching elements.
Because exactly two elements are removed, the smallest surviving element in nums1 must appear among the first three sorted elements. Therefore, every valid solution must produce one of the three candidate values of x.
The two pointer verification works because sorted order guarantees that if a transformed value does not match the current target value, that element must be removed. There is no advantage to matching it later.
Thus every valid transformation is correctly detected.
Python Solution
from typing import List
class Solution:
def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
nums1.sort()
nums2.sort()
def valid(x: int) -> bool:
i = 0
j = 0
removed = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] + x == nums2[j]:
i += 1
j += 1
else:
removed += 1
i += 1
if removed > 2:
return False
removed += len(nums1) - i
return removed == 2 and j == len(nums2)
answer = float("inf")
for i in range(3):
x = nums2[0] - nums1[i]
if valid(x):
answer = min(answer, x)
return answer
The implementation begins by sorting both arrays. This is essential because the matching logic relies on ordered traversal.
The helper function valid(x) determines whether a candidate value of x can produce nums2.
Inside this function, two pointers traverse the arrays simultaneously. Whenever a transformed element matches the current target element, both pointers advance. Otherwise, the current element from nums1 is treated as removed.
The variable removed tracks how many elements have been skipped. If more than two removals are needed, the candidate immediately fails.
After processing, we also count any remaining unused elements in nums1 as removed elements.
Finally, we test the three possible candidates derived from the first three sorted elements of nums1, keeping the minimum valid value.
Go Solution
package main
import (
"math"
"sort"
)
func minimumAddedInteger(nums1 []int, nums2 []int) int {
sort.Ints(nums1)
sort.Ints(nums2)
valid := func(x int) bool {
i := 0
j := 0
removed := 0
for i < len(nums1) && j < len(nums2) {
if nums1[i]+x == nums2[j] {
i++
j++
} else {
removed++
i++
if removed > 2 {
return false
}
}
}
removed += len(nums1) - i
return removed == 2 && j == len(nums2)
}
answer := math.MaxInt32
for i := 0; i < 3; i++ {
x := nums2[0] - nums1[i]
if valid(x) && x < answer {
answer = x
}
}
return answer
}
The Go implementation follows exactly the same algorithmic structure as the Python version.
A few Go specific details are worth noting:
sort.Intsis used for sorting slices in ascending order.- The helper function
validis implemented as a closure. math.MaxInt32initializes the answer with a very large integer.- Go slices are reference-like structures, so sorting modifies the original arrays directly.
No overflow concerns exist because values remain small under the given constraints.
Worked Examples
Example 1
Input:
nums1 = [4,20,16,12,8]
nums2 = [14,18,10]
After sorting:
nums1 = [4,8,12,16,20]
nums2 = [10,14,18]
We try candidates:
| i | nums1[i] | Candidate x |
|---|---|---|
| 0 | 4 | 10 - 4 = 6 |
| 1 | 8 | 10 - 8 = 2 |
| 2 | 12 | 10 - 12 = -2 |
Testing x = 6
| nums1[i] | nums1[i] + x | nums2[j] | Action |
|---|---|---|---|
| 4 | 10 | 10 | match |
| 8 | 14 | 14 | match |
| 12 | 18 | 18 | match |
We still have two unused elements, 16 and 20, so exactly two removals occur.
This is valid, but we continue searching for a smaller x.
Testing x = 2
Transformation:
[6,10,14,18,22]
Cannot match nums2 with only two removals.
Invalid.
Testing x = -2
Transformation:
[2,6,10,14,18]
Remove 2 and 6.
Remaining:
[10,14,18]
This matches nums2.
Answer:
-2
Example 2
Input:
nums1 = [3,5,5,3]
nums2 = [7,7]
After sorting:
nums1 = [3,3,5,5]
nums2 = [7,7]
Candidates:
| i | nums1[i] | Candidate x |
|---|---|---|
| 0 | 3 | 4 |
| 1 | 3 | 4 |
| 2 | 5 | 2 |
Testing x = 4
Transformation:
[7,7,9,9]
Need to remove two 9s.
Valid.
Testing x = 2
Transformation:
[5,5,7,7]
Remove two 5s.
Valid and smaller.
Answer:
2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | Sorting dominates the runtime |
| Space | O(1) or O(log n) | Only a few variables are used beyond sorting overhead |
The algorithm sorts both arrays once, which costs O(n log n).
After sorting, we test at most three candidate values of x. Each validation performs a linear scan through the arrays, costing O(n).
Therefore, the total complexity remains dominated by sorting.
Test Cases
from typing import List
class Solution:
def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
nums1.sort()
nums2.sort()
def valid(x: int) -> bool:
i = 0
j = 0
removed = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] + x == nums2[j]:
i += 1
j += 1
else:
removed += 1
i += 1
if removed > 2:
return False
removed += len(nums1) - i
return removed == 2 and j == len(nums2)
answer = float("inf")
for i in range(3):
x = nums2[0] - nums1[i]
if valid(x):
answer = min(answer, x)
return answer
sol = Solution()
assert sol.minimumAddedInteger([4,20,16,12,8], [14,18,10]) == -2 # provided example 1
assert sol.minimumAddedInteger([3,5,5,3], [7,7]) == 2 # provided example 2
assert sol.minimumAddedInteger([1,2,3], [3]) == 0 # remove two elements, no shift
assert sol.minimumAddedInteger([1,1,1,1], [2,2]) == 1 # duplicates
assert sol.minimumAddedInteger([10,20,30,40], [15,25]) == -5 # negative x
assert sol.minimumAddedInteger([0,0,0,0], [0,0]) == 0 # all equal
assert sol.minimumAddedInteger([5,6,7,8,9], [10,11,12]) == 3 # positive shift
assert sol.minimumAddedInteger([1000,1000,1000], [999]) == -1 # boundary values
assert sol.minimumAddedInteger([1,2,100,101], [3,4]) == 1 # remove largest values
assert sol.minimumAddedInteger([50,51,52,1,2], [53,54,55]) == 3 # remove smallest values
Test Case Summary
| Test | Why |
|---|---|
[4,20,16,12,8] -> [14,18,10] |
Validates negative shift |
[3,5,5,3] -> [7,7] |
Validates duplicates |
[1,2,3] -> [3] |
Smallest valid array sizes |
[1,1,1,1] -> [2,2] |
All duplicate values |
[10,20,30,40] -> [15,25] |
Negative x |
[0,0,0,0] -> [0,0] |
Zero shift |
[5,6,7,8,9] -> [10,11,12] |
Positive shift |
[1000,1000,1000] -> [999] |
Upper bound values |
[1,2,100,101] -> [3,4] |
Removing largest elements |
[50,51,52,1,2] -> [53,54,55] |
Removing smallest elements |
Edge Cases
One important edge case occurs when many duplicate values exist. In such situations, naive matching logic can accidentally pair the wrong occurrences together. Sorting and using a two pointer scan avoids this issue because equal values are processed consistently in order.
Another important case is when x is negative. Some implementations incorrectly assume values only increase. However, the problem explicitly allows decreasing values as well. Our implementation handles this naturally because x is computed as a difference and may be negative.
A third tricky case occurs when the two removed elements are the smallest elements in nums1. In this situation, the smallest surviving element becomes nums1[2]. This is precisely why the algorithm checks the first three positions when generating candidate values for x.
A final subtle case appears when transformed values partially match but require more than two removals. The helper validation function carefully tracks the number of skipped elements and immediately rejects invalid candidates once the limit exceeds two.