# Find the Integer Added to Array I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-the-integer-added-to-array-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-integer-added-to-array-i
**Data structures:** Array
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## Problem
You are given two arrays of equal length, `nums1` and `nums2`.

Each element in `nums1` has 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 integer `x`.

**Example 1:**

**Input:** nums1 = \[2,6,4\], nums2 = \[9,7,5\]

**Output:** 3

**Explanation:**

The integer added to each element of `nums1` is 3.

**Example 2:**

**Input:** nums1 = \[10\], nums2 = \[5\]

**Output:** \-5

**Explanation:**

The integer added to each element of `nums1` is -5.

**Example 3:**

**Input:** nums1 = \[1,1,1,1\], nums2 = \[1,1,1,1\]

**Output:** 0

**Explanation:**

The integer added to each element of `nums1` is 0.

**Constraints:**

* `1 <= nums1.length == nums2.length <= 100`
* `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 adding `x` to each element of `nums1`.

# Approaches
## Brute Force with Verification
This approach involves a brute-force search for the integer `x`. It works by picking an element from `nums1` (e.g., `nums1[0]`) and assuming it corresponds to some element in `nums2`. This assumption gives a candidate value for `x`. The algorithm then verifies if adding this candidate `x` to all elements in `nums1` results in an array that is a permutation of `nums2`.
**Time:** O(N^2), where N is the length of the arrays. The outer loop runs N times. The `check` function inside the loop takes O(N) time (O(N) to build the map and O(N) to check against it). This results in a total complexity of N * O(N) = O(N^2). · **Space:** O(N), where N is the length of the arrays. This space is used to store the frequency map during the verification step.
**Pros:** Conceptually simple to understand as it directly models the problem of trying possibilities and verifying them.
**Cons:** Highly inefficient compared to other solutions, with a quadratic time complexity.; Performs a lot of redundant work by re-checking permutations for different candidate values of `x`.
### Explanation
The algorithm systematically tests every possible value for `x` that could arise from pairing `nums1[0]` with each element of `nums2`. For each potential `x`, it performs a full verification. The verification step involves checking if the multiset `{nums1[0]+x, nums1[1]+x, ...}` is identical to the multiset of `nums2`. A common way to check for multiset equality is by using frequency maps (or hash maps). We build a frequency map for `nums2`, then iterate through the transformed `nums1` elements, decrementing their counts in the map. If all elements match and the map becomes empty of positive counts, the `x` is valid.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int addedInteger(int[] nums1, int[] nums2) {
        // This is a brute-force approach for demonstration.
        // It's less efficient than other methods.
        for (int n2 : nums2) {
            int potentialX = n2 - nums1[0];
            if (check(nums1, nums2, potentialX)) {
                return potentialX;
            }
        }
        return -1; // Should not be reached based on problem constraints
    }

    private boolean check(int[] nums1, int[] nums2, int x) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums2) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }

        for (int num : nums1) {
            int target = num + x;
            if (!freq.containsKey(target) || freq.get(target) == 0) {
                return false;
            }
            freq.put(target, freq.get(target) - 1);
        }
        return true;
    }
}
```
### Algorithm
1. Iterate through each element `n2` in `nums2`.
2. For each `n2`, hypothesize that it corresponds to `nums1[0]`. Calculate a candidate difference `x = n2 - nums1[0]`.
3. Verify if this candidate `x` is the correct integer. To do this:
    a. Create a frequency map of the elements in `nums2`.
    b. Iterate through `nums1`. For each element `n1`, calculate the transformed value `n1 + x`.
    c. Check if this transformed value exists in the frequency map and decrement its count.
    d. If at any point a transformed value is not in the map or its count is zero, this candidate `x` is incorrect. Move to the next `n2`.
4. If the verification loop completes successfully for all elements of `nums1`, the candidate `x` is the correct answer. Return `x`.
5. Since a solution is guaranteed to exist, this process will find the answer.

## Sorting Both Arrays
A more efficient approach relies on the property that adding a constant `x` to all elements of an array preserves their relative order. If we sort both arrays, the element at each index `i` in the sorted `nums1` corresponds to the element at the same index `i` in the sorted `nums2` after the addition of `x`.
**Time:** O(N log N), dominated by the time it takes to sort the two arrays. · **Space:** O(log N) or O(N), depending on the implementation of the sorting algorithm. In Java, `Arrays.sort` for primitive types uses a dual-pivot quicksort, which has an average space complexity of O(log N) for the recursion stack.
**Pros:** Significantly faster than the brute-force approach for larger N.; The logic is straightforward and easy to implement.; Guaranteed to work because the transformation `+x` is monotonic.
**Cons:** While efficient, it's not the most optimal solution as sorting does more work than necessary for this specific problem.; The space complexity can be O(N) or O(log N) depending on the sort implementation, which is higher than the O(1) space possible with the optimal approach.
### Explanation
The core idea is that if `nums1` is transformed into `nums2` by adding `x` to each element, then the smallest element of `nums1` plus `x` must equal the smallest element of `nums2`. The same logic applies to the second smallest elements, and so on. Therefore, we can find `x` by sorting both arrays and calculating the difference between any pair of corresponding elements. The simplest pair to use is the first one (the minimums).

```java
import java.util.Arrays;

class Solution {
    public int addedInteger(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        return nums2[0] - nums1[0];
    }
}
```
### Algorithm
1. Sort the `nums1` array in non-decreasing order.
2. Sort the `nums2` array in non-decreasing order.
3. The problem states that `sorted_nums1[i] + x = sorted_nums2[i]` for all `i`.
4. We can find `x` by picking any index `i`, for example `i=0`.
5. Calculate `x` using the first elements: `x = sorted_nums2[0] - sorted_nums1[0]`.
6. Return this value of `x`.

## Linear Scan to Find Minimums
The most efficient approach leverages the same property as the sorting method but avoids the cost of a full sort. Since adding `x` preserves the order of elements, the minimum element of `nums1` must correspond to the minimum element of `nums2` after the transformation. The same holds true for the maximum elements.
**Time:** O(N), where N is the length of the arrays. We perform two separate linear scans, one for each array, which takes O(N) + O(N) = O(N) time in total. · **Space:** O(1), as we only use a few variables to store the minimums, regardless of the input size.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1).; Very simple and efficient to implement.
**Cons:** There are no significant cons for this approach; it is optimal for this problem.
### Explanation
The transformation `num -> num + x` is monotonic. This means if `a < b`, then `a + x < b + x`. Consequently, the minimum value in the original `nums1` array, let's call it `min1`, will become `min1 + x` after the transformation. This new value must be the minimum value in the resulting array, which is a permutation of `nums2`. The minimum value in `nums2` is `min2`. Therefore, we have the equation: `min1 + x = min2`. We can solve for `x`: `x = min2 - min1`. The algorithm simply requires finding the minimum element in each array and calculating their difference.

```java
class Solution {
    public int addedInteger(int[] nums1, int[] nums2) {
        int min1 = nums1[0];
        for (int i = 1; i < nums1.length; i++) {
            if (nums1[i] < min1) {
                min1 = nums1[i];
            }
        }

        int min2 = nums2[0];
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] < min2) {
                min2 = nums2[i];
            }
        }

        return min2 - min1;
    }
}
```
### Algorithm
1. Find the minimum element in `nums1`. This can be done with a single pass through the array.
2. Find the minimum element in `nums2`. This also takes a single pass.
3. Calculate the difference: `x = min(nums2) - min(nums1)`.
4. Return `x`.

# Solutions
### Java

```java
class Solution {
public
  int addedInteger(int[] nums1, int[] nums2) {
    return Arrays.stream(nums2).min().getAsInt() -
           Arrays.stream(nums1).min().getAsInt();
  }
}

```

### CPP

```cpp
class Solution {
public:
  int addedInteger(vector<int> &nums1, vector<int> &nums2) {
    return *min_element(nums2.begin(), nums2.end()) -
           *min_element(nums1.begin(), nums1.end());
  }
};

```

### Python

```python
class Solution:
    def addedInteger(
        self, nums1: List[int], nums2: List[int]) -> int: return min(nums2) - min(nums1)

```