Find the Integer Added to Array II

Medium
1009.

Find the Integer Added to Array II

Find the Integer Added to Array II is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Google and Adobe interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var minimumAddedInteger = function(nums1, nums2) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the Integer Added to Array II — Problem & Solution

Find the Integer Added to Array II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find the Integer Added to Array II is a medium coding problem on arrays, sorting and two pointers, asked in Amazon, Google and Adobe interviews.

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.

Hints for Find the Integer Added to Array II

  1. Hint 1

    Sort both arrays. The smallest surviving element of nums1 must map to the smallest element of nums2.

  2. Hint 2

    Only two elements are dropped, so that survivor is one of the first three of the sorted nums1.

  3. Hint 3

    For each of those three candidates, x is forced — then check it greedily with two pointers.

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

  1. Sort nums1 and nums2 ascending.
  2. For i in 0, 1, 2: set x = nums2[0] - nums1[i].
  3. Walk nums1 left to right with a pointer into nums2, advancing it whenever nums1[t] + x equals the current target.
  4. 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

Java

public static int minimumAddedInteger(int[] nums1, int[] nums2) {
    int[] a = nums1.clone();
    int[] b = nums2.clone();
    Arrays.sort(a);
    Arrays.sort(b);
    int best = 0;
    boolean found = false;
    for (int i = 0; i < 3; i++) {
        int x = b[0] - a[i];
        int j = 0;
        for (int 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;
}

C++

int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
    vector<int> a = nums1, b = nums2;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    int best = 0;
    bool found = false;
    for (int i = 0; i < 3; i++) {
        int x = b[0] - a[i];
        size_t j = 0;
        for (size_t t = 0; t < a.size() && j < b.size(); t++) {
            if (a[t] + x == b[j]) j++;
        }
        if (j == b.size() && (!found || x < best)) {
            best = x;
            found = true;
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms