Find the Integer Added to Array II — Medium Problem & Solution

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…

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 <= 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.

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 nums1 and nums2 ascending.
For i in 0, 1, 2: set x = nums2[0] - nums1[i].
Walk nums1 left to right with a pointer into nums2, advancing it whenever nums1[t] + x equals the current target.
If the pointer reaches the end of nums2, the candidate is valid; return the smallest valid x.

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

x may 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 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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue