Find the Integer Added to Array II
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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] <= 1000- The test cases are generated in a way that there is an integer
xsuch thatnums1can become equal tonums2by removing two elements and addingxto each element ofnums1.
Solution
Method 1 – Sorting and Two-Pointers
Intuition
If we sort both arrays, the only difference between nums1 and nums2 is that two elements are missing from nums1 (before adding x). By trying all possible pairs of elements to remove from nums1, and checking what value of x would make the remaining elements match nums2, we can find the minimum possible x.
Approach
- Sort both
nums1andnums2. - For every pair of indices
(i, j)innums1(wherei < j), remove those two elements. - For the remaining elements, calculate the difference between each element and the corresponding element in
nums2. - If all differences are the same, that value is a candidate for
x. - Track the minimum such
xfound. - Return the minimum
x.
Code
C++
class Solution {
public:
int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int n = nums1.size(), m = nums2.size();
int ans = INT_MAX;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
vector<int> v;
for (int k = 0; k < n; ++k) {
if (k != i && k != j) v.push_back(nums1[k]);
}
int x = nums2[0] - v[0];
bool ok = true;
for (int k = 0; k < m; ++k) {
if (nums2[k] - v[k] != x) {
ok = false;
break;
}
}
if (ok) ans = min(ans, x);
}
}
return ans;
}
};
Go
func minimumAddedInteger(nums1 []int, nums2 []int) int {
sort.Ints(nums1)
sort.Ints(nums2)
n, m := len(nums1), len(nums2)
ans := math.MaxInt32
for i := 0; i < n; i++ {
for j := i+1; j < n; j++ {
v := []int{}
for k := 0; k < n; k++ {
if k != i && k != j {
v = append(v, nums1[k])
}
}
x := nums2[0] - v[0]
ok := true
for k := 0; k < m; k++ {
if nums2[k] - v[k] != x {
ok = false
break
}
}
if ok && x < ans {
ans = x
}
}
}
return ans
}
Java
class Solution {
public int minimumAddedInteger(int[] nums1, int[] nums2) {
Arrays.sort(nums1);
Arrays.sort(nums2);
int n = nums1.length, m = nums2.length, ans = Integer.MAX_VALUE;
for (int i = 0; i < n; ++i) {
for (int j = i+1; j < n; ++j) {
List<Integer> v = new ArrayList<>();
for (int k = 0; k < n; ++k) {
if (k != i && k != j) v.add(nums1[k]);
}
int x = nums2[0] - v.get(0);
boolean ok = true;
for (int k = 0; k < m; ++k) {
if (nums2[k] - v.get(k) != x) {
ok = false;
break;
}
}
if (ok) ans = Math.min(ans, x);
}
}
return ans;
}
}
Kotlin
class Solution {
fun minimumAddedInteger(nums1: IntArray, nums2: IntArray): Int {
nums1.sort()
nums2.sort()
val n = nums1.size
val m = nums2.size
var ans = Int.MAX_VALUE
for (i in 0 until n) {
for (j in i+1 until n) {
val v = mutableListOf<Int>()
for (k in 0 until n) {
if (k != i && k != j) v.add(nums1[k])
}
val x = nums2[0] - v[0]
var ok = true
for (k in 0 until m) {
if (nums2[k] - v[k] != x) {
ok = false
break
}
}
if (ok) ans = minOf(ans, x)
}
}
return ans
}
}
Python
class Solution:
def minimumAddedInteger(self, nums1: list[int], nums2: list[int]) -> int:
nums1.sort()
nums2.sort()
n, m = len(nums1), len(nums2)
ans = float('inf')
for i in range(n):
for j in range(i+1, n):
v = [nums1[k] for k in range(n) if k != i and k != j]
x = nums2[0] - v[0]
if all(nums2[k] - v[k] == x for k in range(m)):
ans = min(ans, x)
return ans
Rust
impl Solution {
pub fn minimum_added_integer(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let mut nums1 = nums1.clone();
let mut nums2 = nums2.clone();
nums1.sort();
nums2.sort();
let n = nums1.len();
let m = nums2.len();
let mut ans = i32::MAX;
for i in 0..n {
for j in (i+1)..n {
let v: Vec<i32> = (0..n).filter(|&k| k != i && k != j).map(|k| nums1[k]).collect();
let x = nums2[0] - v[0];
if (0..m).all(|k| nums2[k] - v[k] == x) {
ans = ans.min(x);
}
}
}
ans
}
}
TypeScript
class Solution {
minimumAddedInteger(nums1: number[], nums2: number[]): number {
nums1.sort((a, b) => a - b);
nums2.sort((a, b) => a - b);
const n = nums1.length, m = nums2.length;
let ans = Infinity;
for (let i = 0; i < n; ++i) {
for (let j = i+1; j < n; ++j) {
const v = [];
for (let k = 0; k < n; ++k) {
if (k !== i && k !== j) v.push(nums1[k]);
}
const x = nums2[0] - v[0];
let ok = true;
for (let k = 0; k < m; ++k) {
if (nums2[k] - v[k] !== x) {
ok = false;
break;
}
}
if (ok) ans = Math.min(ans, x);
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^3), because for each pair of indices to remove (O(n^2)), we compare the remaining arrays (O(n)). - 🧺 Space complexity:
O(n), for storing the temporary array after removing two elements.