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

1
2
3
4

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

1
2
3
4

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.

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

  1. Sort both nums1 and nums2.
  2. For every pair of indices (i, j) in nums1 (where i < j), remove those two elements.
  3. For the remaining elements, calculate the difference between each element and the corresponding element in nums2.
  4. If all differences are the same, that value is a candidate for x.
  5. Track the minimum such x found.
  6. Return the minimum x.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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.