# Find the Integer Added to Array II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-integer-added-to-array-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-the-integer-added-to-array-ii
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## 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.

**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 <= 200`
* `nums2.length == nums1.length - 2`
* `0 <= nums1[i], nums2[i] <= 1000`
* The 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`.

# Approaches
## Brute-force by Trying All Pairs to Remove
This approach systematically considers every possible pair of elements to remove from `nums1`. For each choice, it calculates the required integer `x` and verifies if this `x` transforms the remaining `n-2` elements of `nums1` into `nums2`. The minimum valid `x` found is the answer.
**Time:** O(n^3), where n is the length of `nums1`. Sorting takes O(n log n). The two nested loops iterate O(n^2) times. Inside the loops, creating the temporary list and checking the difference both take O(n) time, leading to a total of O(n^3). · **Space:** O(n), where n is the length of `nums1`. This is for storing the temporary list `temp` which has a size of `n-2`.
**Pros:** It is a straightforward and easy-to-understand implementation of the problem statement.; It is guaranteed to be correct as it explores the entire search space of removed elements.
**Cons:** The time complexity of O(n^3) is inefficient and may not pass for larger constraints, although it works for the given constraints (n <= 200).
### Explanation
The fundamental idea is to exhaust all possibilities. Since we know two elements are removed from `nums1`, we can try removing every unique pair of elements. To make the verification step easier, we first sort both `nums1` and `nums2`. Sorting ensures that if a valid transformation exists, the remaining `n-2` elements from `nums1` (after adding `x`) will match `nums2` in the same sorted order.

We use two nested loops to select two distinct indices, `i` and `j`, from `nums1`. We then construct a temporary array `temp` containing the elements of `nums1` that were *not* at indices `i` and `j`. With `temp` and `nums2` (both sorted and of the same length), we can determine the potential value of `x`. The difference `x = nums2[0] - temp[0]` must hold for all corresponding pairs of elements. We check this condition. If it holds, the calculated `x` is a valid candidate, and we update our minimum `x` found so far. By iterating through all `O(n^2)` pairs, we are guaranteed to find the correct transformation and thus the minimum `x`.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int n = nums1.length;
        int minX = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Create a temporary list of nums1 after removing elements at i and j
                List<Integer> temp = new ArrayList<>();
                for (int k = 0; k < n; k++) {
                    if (k != i && k != j) {
                        temp.add(nums1[k]);
                    }
                }

                // Check if this temporary list can be transformed into nums2
                int diff = nums2[0] - temp.get(0);
                boolean possible = true;
                for (int k = 1; k < nums2.length; k++) {
                    if (nums2[k] - temp.get(k) != diff) {
                        possible = false;
                        break;
                    }
                }

                if (possible) {
                    minX = Math.min(minX, diff);
                }
            }
        }
        return minX;
    }
}
```
### Algorithm
1. Sort both `nums1` and `nums2` arrays.
2. Initialize a variable `min_x` to a very large value to store the minimum possible `x`.
3. Use nested loops to iterate through every possible pair of indices `(i, j)` from `nums1`. These two indices represent the elements to be removed.
4. For each pair `(i, j)`:
    a. Create a temporary list, `temp`, containing all elements of `nums1` except for `nums1[i]` and `nums1[j]`.
    b. Since `nums1` was sorted, `temp` will also be sorted. Calculate a potential difference `x` by comparing the first elements: `x = nums2[0] - temp.get(0)`.
    c. Verify if this `x` is valid for all other elements. Iterate from `k = 1` to `nums2.length - 1` and check if `nums2[k] - temp.get(k)` is equal to `x`.
    d. If the difference is consistent for all elements, it means we have found a valid `x`. Update `min_x = min(min_x, x)`.
5. After checking all possible pairs to remove, return `min_x`.

## Optimized Approach with Sorting and Candidate Differences
This approach significantly improves efficiency by reducing the number of potential values for `x` that need to be checked. By sorting both arrays, we can deduce that the value of `x` must be one of only three possibilities. This is because the smallest element in `nums2` must correspond to one of the three smallest possible elements from the remaining subset of `nums1`.
**Time:** O(n log n), where n is the length of `nums1`. Sorting the arrays takes O(n log n). After that, we perform a constant number of checks (at most 3), and each check takes O(n) time. The sorting step dominates the complexity. · **Space:** O(log n) or O(n), depending on the space used by the sorting algorithm's implementation (e.g., for recursion stack or temporary storage).
**Pros:** Highly efficient, with a time complexity dominated by the initial sort.; Reduces the search space for `x` from potentially many values to just three candidates.; Simple and clean implementation once the main insight is understood.
**Cons:** The core logic relies on an insight about sorted arrays which might not be immediately obvious.
### Explanation
The key to optimizing this problem is to avoid checking every pair of removed elements. Instead, we focus on finding the possible values of `x`. After sorting both `nums1` and `nums2`, let's consider the smallest element of `nums2`, which is `nums2[0]`. This element must have been formed by adding `x` to some element `y` from `nums1` that was not removed. So, `nums2[0] = y + x`.

Since `y` is part of a sorted sequence, and `nums2[0]` is the smallest in its sequence, `y` must be the smallest element among the `n-2` elements of `nums1` that were kept. When we remove two elements from the sorted `nums1`, what could be the smallest remaining element? 
- If `nums1[0]` is not removed, it's `nums1[0]`.
- If `nums1[0]` is removed but `nums1[1]` is not, it's `nums1[1]`.
- If both `nums1[0]` and `nums1[1]` are removed, it's `nums1[2]`.

These are the only three possibilities. Therefore, `x` must be one of `nums2[0] - nums1[0]`, `nums2[0] - nums1[1]`, or `nums2[0] - nums1[2]`. We only need to test these three candidate values. For each candidate, we can verify its validity in O(n) time using a two-pointer scan over the sorted arrays, checking if we can match all elements of `nums2` while skipping exactly two elements from `nums1`. The minimum valid `x` is our answer.

```java
import java.util.Arrays;

class Solution {
    public int minimumAddedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int minX = Integer.MAX_VALUE;

        // The smallest element in nums2 must correspond to one of the first three
        // smallest possible elements in the remaining nums1 subset.
        // These are nums1[0], nums1[1], or nums1[2].
        for (int i = 0; i <= 2; i++) {
            int diff = nums2[0] - nums1[i];
            if (isPossible(nums1, nums2, diff)) {
                minX = Math.min(minX, diff);
            }
        }
        return minX;
    }

    private boolean isPossible(int[] nums1, int[] nums2, int diff) {
        int p1 = 0; // pointer for nums1
        int p2 = 0; // pointer for nums2
        int removedCount = 0;

        while (p1 < nums1.length) {
            if (p2 < nums2.length && nums1[p1] + diff == nums2[p2]) {
                // Match found
                p1++;
                p2++;
            } else {
                // This element from nums1 must be removed
                removedCount++;
                p1++;
            }
        }

        // We must have found all elements of nums2 and removed exactly 2 elements.
        return p2 == nums2.length && removedCount == 2;
    }
}
```
### Algorithm
1. Sort both `nums1` and `nums2` in non-decreasing order.
2. Realize that the smallest element in the modified `nums1` must correspond to the smallest element in `nums2`. The smallest element in the modified `nums1` can only be `nums1[0]`, `nums1[1]`, or `nums1[2]` from the original sorted `nums1`.
3. This gives three candidate values for `x`: `nums2[0] - nums1[0]`, `nums2[0] - nums1[1]`, and `nums2[0] - nums1[2]`.
4. Initialize `min_x` to a very large value.
5. Iterate through these three candidate values for `x`.
6. For each candidate `x`, use a helper function `isPossible(x)` to check if it's a valid transformation.
7. The `isPossible(x)` function uses a two-pointer approach on the sorted arrays to check if `nums2` can be formed from `nums1` by adding `x` and removing exactly two elements. It returns `true` if possible, `false` otherwise.
8. If `isPossible(x)` returns `true`, update `min_x = min(min_x, x)`.
9. Return `min_x`.

# Solutions
### Java

```java
class Solution {
public
  int minimumAddedInteger(int[] nums1, int[] nums2) {
    Arrays.sort(nums1);
    Arrays.sort(nums2);
    int ans = 1 << 30;
    for (int i = 0; i < 3; ++i) {
      int x = nums2[0] - nums1[i];
      if (f(nums1, nums2, x)) {
        ans = Math.min(ans, x);
      }
    }
    return ans;
  }
private
  boolean f(int[] nums1, int[] nums2, int x) {
    int i = 0, j = 0, cnt = 0;
    while (i < nums1.length && j < nums2.length) {
      if (nums2[j] - nums1[i] != x) {
        ++cnt;
      } else {
        ++j;
      }
      ++i;
    }
    return cnt <= 2;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumAddedInteger(vector<int> &nums1, vector<int> &nums2) {
    sort(nums1.begin(), nums1.end());
    sort(nums2.begin(), nums2.end());
    int ans = 1 << 30;
    auto f = [&](int x) {
      int i = 0, j = 0, cnt = 0;
      while (i < nums1.size() && j < nums2.size()) {
        if (nums2[j] - nums1[i] != x) {
          ++cnt;
        } else {
          ++j;
        }
        ++i;
      }
      return cnt <= 2;
    };
    for (int i = 0; i < 3; ++i) {
      int x = nums2[0] - nums1[i];
      if (f(x)) {
        ans = min(ans, x);
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int: def f(x: int) -> bool: i = j = cnt = 0 while i < len(nums1) and j < len(nums2): if nums2[j] - nums1[i] != x: cnt += 1 else: j += 1 i += 1 return cnt <= 2 nums1 . sort() nums2 . sort() return min(x for x in (nums2[0] - nums1[0], nums2[0] - nums1[1], nums2[0] - nums1[2]) if f(x))

```