Find the Integer Added to Array II — Problem & Solution
Find the Integer Added to Array II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Find the Integer Added to Array II is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Google and Adobe interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Two Pointers, Enumeration
- Asked at: Amazon, Google, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
nums1 holds exactly two more elements than nums2. Remove two elements from nums1 and then add the same integer x — possibly negative — to every remaining element. nums1 and nums2 are then equal when both are treated as multisets: the same values with the same counts, in any order.
Return the minimum possible x. The input guarantees at least one choice works.
Example 1
Input: nums1 = [4,20,16,12,8], nums2 = [14,18,10]
Output: -2
Explanation: Drop 4 and 8, then `12,16,20` shift down by 2.
Example 2
Input: nums1 = [3,5,5,3], nums2 = [7,7]
Output: 2
Explanation: Drop the two 3s and shift the 5s up by 2.
Example 3
Input: nums1 = [2,3,1], nums2 = [1]
Output: -2
Explanation: Keep only the 3 and shift it down by 2.
Constraints
3 <= nums1.length <= 200nums2.length == nums1.length - 20 <= nums1[i], nums2[i] <= 1000The test cases are generated in a way that there is an integer x such that nums1 can become equal to nums2 by removing two elements and adding x to each element of nums1.
Hints for Find the Integer Added to Array II
Hint 1
Sort both arrays. The smallest surviving element of
nums1must map to the smallest element ofnums2.Hint 2
Only two elements are dropped, so that survivor is one of the first three of the sorted
nums1.Hint 3
For each of those three candidates,
xis forced — then check it greedily with two pointers.
How to solve Find the Integer Added to Array II
Sort both arrays. Whatever two elements are dropped, the smallest survivor is among the first three of the sorted nums1, so there are only three candidate values of x — one per choice. Test each with a greedy two-pointer match and keep the smallest that works.
Approach
- Sort
nums1andnums2ascending. - For
iin 0, 1, 2: setx = nums2[0] - nums1[i]. - Walk
nums1left to right with a pointer intonums2, advancing it whenevernums1[t] + xequals the current target. - If the pointer reaches the end of
nums2, the candidate is valid; return the smallest validx.
Why it works
Sorting is what makes the greedy match correct: with both arrays ascending, matching each target against the earliest element that fits never blocks a later match, because any element that could serve a later target could also have served this one. And bounding the search to three candidates is the whole trick — only two elements are removed, so at most two can precede the smallest survivor.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
xmay be negative; do not assume the arrays only grow.- Testing only
nums2[0] - nums1[0]misses the cases where the smallest one or two elements are the ones dropped. - Duplicate values make a set-based comparison wrong — the match must respect multiplicities.
Reference solution
Python
from typing import List
def minimumAddedInteger(nums1: List[int], nums2: List[int]) -> int:
a = sorted(nums1)
b = sorted(nums2)
best = None
for i in range(3):
x = b[0] - a[i]
j = 0
for v in a:
if j < len(b) and v + x == b[j]:
j += 1
if j == len(b) and (best is None or x < best):
best = x
return bestJava
public static int minimumAddedInteger(int[] nums1, int[] nums2) {
int[] a = nums1.clone();
int[] b = nums2.clone();
Arrays.sort(a);
Arrays.sort(b);
int best = 0;
boolean found = false;
for (int i = 0; i < 3; i++) {
int x = b[0] - a[i];
int j = 0;
for (int t = 0; t < a.length && j < b.length; t++) {
if (a[t] + x == b[j]) j++;
}
if (j == b.length && (!found || x < best)) {
best = x;
found = true;
}
}
return best;
}C++
int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
vector<int> a = nums1, b = nums2;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int best = 0;
bool found = false;
for (int i = 0; i < 3; i++) {
int x = b[0] - a[i];
size_t j = 0;
for (size_t t = 0; t < a.size() && j < b.size(); t++) {
if (a[t] + x == b[j]) j++;
}
if (j == b.size() && (!found || x < best)) {
best = x;
found = true;
}
}
return best;
}JavaScript
var minimumAddedInteger = function(nums1, nums2) {
var a = nums1.slice().sort(function(p, q) { return p - q; });
var b = nums2.slice().sort(function(p, q) { return p - q; });
var best = 0, found = false;
for (var i = 0; i < 3; i++) {
var x = b[0] - a[i];
var j = 0;
for (var t = 0; t < a.length && j < b.length; t++) {
if (a[t] + x === b[j]) j++;
}
if (j === b.length && (!found || x < best)) { best = x; found = true; }
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms