3132. Find the Integer Added to Array II - Solution

Q: Is Find the Integer Added to Array II easy or hard?

Find the Integer Added to Array II is classified as a Medium problem. The challenge comes from recognizing that only three candidates for the added integer need to be tested and implementing a clean validation step that allows skipping exactly two elements.

Q: Find the Integer Added to Array II Python/Java solution

Most implementations follow the same logic across languages: sort nums1 and nums2, enumerate up to three candidate values for x, and validate each using two pointers or a hashmap. The algorithm translates cleanly to Python, Java, C++, C#, and JavaScript with identical O(n log n) complexity.

Q: How to solve Find the Integer Added to Array II in O(n)?

A strict O(n) solution is difficult because ordering simplifies the matching process after removing two elements. Most practical implementations sort the arrays first, leading to O(n log n) complexity. After sorting, candidate values for x are tested using a single linear pass with two pointers.

Q: What is the best approach for Find the Integer Added to Array II?

The most efficient and commonly expected solution is sorting combined with a two-pointer validation. After sorting both arrays, try up to three candidates for the added integer x based on aligning nums2[0] with the first three elements of nums1. Each candidate is validated with a linear scan while skipping at most two elements from nums1. The overall complexity is O(n log n) due to sorting and O(1) extra space.

Q: Is Find the Integer Added to Array II asked at Google/Amazon/Meta?

Array alignment and difference-enumeration problems appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. Variants that involve sorting, removing elements, or validating transformations with two pointers are common in mid-level algorithm interviews.

Q: What data structure is used in Find the Integer Added to Array II?

The problem primarily uses arrays with sorting and a two-pointer scanning technique. An alternative approach uses a hash map (frequency map) to count occurrences in nums2 and verify matches after applying the candidate integer shift.

Q: What is the time complexity of Find the Integer Added to Array II?

The optimal solution runs in O(n log n) time because both arrays are sorted before validation. After sorting, only three candidate values of x are checked, and each check scans the arrays once in O(n). The space complexity can be O(1) if the two-pointer technique is used.

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

Approach overview

Problem Overview: You receive two arrays nums1 and nums2. Array nums2 was created by removing exactly two elements from nums1 and then adding the same integer x to every remaining value. Your task is to determine the integer x.

Approach 1: Sorting and Two-Pointer Technique (O(n log n) time, O(1) extra space)

Sort both arrays first. After sorting, the smallest value in nums2 must correspond to one of the first three elements in nums1, because at most two numbers could have been removed before it. For each candidate index i in the first three elements of nums1, compute a potential shift x = nums2[0] - nums1[i]. Then scan both arrays using two pointers. Compare nums1[j] + x with nums2[k]; if they match, move both pointers. Otherwise treat the element in nums1 as one of the removed values and advance only that pointer. If more than two elements must be skipped, the candidate x is invalid. The smallest valid x is the answer. This approach relies on sorting and a linear two pointers verification pass.

Approach 2: Difference Enumeration with HashMap (O(n log n) time, O(n) space)

Sort both arrays and enumerate possible values of x by pairing early elements of nums1 with nums2[0]. For each candidate shift, build a frequency map of nums2. Iterate through nums1, compute value = nums1[i] + x, and check whether it exists in the map. If it exists, decrease its frequency; otherwise treat that element as one of the two removed numbers. If more than two elements fail to match, discard the candidate. This approach uses a hash-based frequency map to validate matches and works well when you want explicit counting instead of pointer alignment.

Recommended for interviews: The sorting + two-pointer method is typically expected. It shows you understand how ordering simplifies alignment problems and reduces validation to a single linear scan. Enumerating only three candidates for x keeps the search space tiny, and the two-pointer check clearly models the "remove two elements" constraint.

Approach 1: Sorting and Two-Pointer Technique

Sort both arrays. With `nums1` being larger, try removing all combinations of two elements from `nums1`. Use a two-pointer technique to check if all elements align by adjusting all `nums1` elements by an integer `x`.

Python

def minX(nums1, nums2):
    nums1.sort()
    nums2.sort()
    min_possible_x = nums2[0] - nums1[2]
    for i in range(2, len(nums1)):
        x = nums2[0] - nums1[i]
        min_possible_x = min(min_possible_x, x)
    return min_possible_x

nums1 = [4, 20, 16, 12, 8]
nums2 = [14, 18, 10]
print("Minimum x:", minX(nums1, nums2))

Java

import java.util.Arrays;

public class Solution {
    public int minX(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        int minPossibleX = nums2[0] - nums1[2];
        for (int i = 2; i < nums1.length; i++) {
            int x = nums2[0] - nums1[i];
            minPossibleX = Math.min(minPossibleX, x);
        }
        return minPossibleX;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {4, 20, 16, 12, 8};
        int[] nums2 = {14, 18, 10};
        System.out.println("Minimum x: " + solution.minX(nums1, nums2));
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>

int minX(std::vector<int>& nums1, std::vector<int>& nums2) {
    std::sort(nums1.begin(), nums1.end());
    std::sort(nums2.begin(), nums2.end());
    int minPossibleX = nums2[0] - nums1[2];
    for (int i = 2; i < nums1.size(); ++i) {
        int x = nums2[0] - nums1[i];
        minPossibleX = std::min(minPossibleX, x);
    }
    return minPossibleX;
}

int main() {
    std::vector<int> nums1 = {4, 20, 16, 12, 8};
    std::vector<int> nums2 = {14, 18, 10};
    int x = minX(nums1, nums2);
    std::cout << "Minimum x: " << x << std::endl;
    return 0;
}

JavaScript

function minX(nums1, nums2) {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    let minPossibleX = nums2[0] - nums1[2];
    for (let i = 2; i < nums1.length; i++) {
        let x = nums2[0] - nums1[i];
        minPossibleX = Math.min(minPossibleX, x);
    }
    return minPossibleX;
}

let nums1 = [4, 20, 16, 12, 8];
let nums2 = [14, 18, 10];
console.log("Minimum x:", minX(nums1, nums2));

#include <stdio.h>
#include <stdlib.h>

int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

// Function to find the minimum integer x
int minX(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    qsort(nums1, nums1Size, sizeof(int), compare);
    qsort(nums2, nums2Size, sizeof(int), compare);

    int minPossibleX = nums2[0] - nums1[2]; // Initial x
    for (int i = 2; i < nums1Size; ++i) {
        int x = nums2[0] - nums1[i];
        if (x < minPossibleX)
            minPossibleX = x;
    }
    return minPossibleX;
}

int main() {
    int nums1[] = {4, 20, 16, 12, 8};
    int nums2[] = {14, 18, 10};
    int x = minX(nums1, 5, nums2, 3);
    printf("Minimum x: %d\n", x);
    return 0;
}

using System;

class Solution {
    static int MinX(int[] nums1, int[] nums2) {
        Array.Sort(nums1);
        Array.Sort(nums2);
        int minPossibleX = nums2[0] - nums1[2];
        for (int i = 2; i < nums1.Length; i++) {
            int x = nums2[0] - nums1[i];
            minPossibleX = Math.Min(minPossibleX, x);
        }
        return minPossibleX;
    }

    static void Main() {
        int[] nums1 = {4, 20, 16, 12, 8};
        int[] nums2 = {14, 18, 10};
        Console.WriteLine("Minimum x: " + MinX(nums1, nums2));
    }
}

This Python version sorts both arrays and calculates the smallest `x` required to equalize them by evaluating potential offsets derived from the first element of `nums2`.

Complexity

Time Complexity: O(n log n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Difference and Hashmap

Use hashmaps to determine frequency differences between the elements of `nums1` and `nums2`. Calculate required changes per each element. The minimal `x` can be derived from aligning these differences.

Python

from collections import Counter

def minX(nums1, nums2):
    freq1 = Counter(nums1)
    freq2 = Counter(nums2)
    min_possible_x = float('inf')
    for key in freq2.keys():
        if freq1[key] < freq2[key]:
            min_possible_x = key
    return min_possible_x

nums1 = [4, 20, 16, 12, 8]
nums2 = [14, 18, 10]
print("Minimum x:", minX(nums1, nums2))

Java

import java.util.HashMap;

public class Solution {
    public int minX(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> freq1 = new HashMap<>();
        HashMap<Integer, Integer> freq2 = new HashMap<>();
        for (int num : nums1) {
            freq1.put(num, freq1.getOrDefault(num, 0) + 1);
        }
        for (int num : nums2) {
            freq2.put(num, freq2.getOrDefault(num, 0) + 1);
        }
        int minX = Integer.MAX_VALUE;
        for (int num : freq2.keySet()) {
            if (freq1.getOrDefault(num, 0) < freq2.get(num)) {
                minX = num;
            }
        }
        return minX;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {4, 20, 16, 12, 8};
        int[] nums2 = {14, 18, 10};
        System.out.println("Minimum x: " + solution.minX(nums1, nums2));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>

int minX(const std::vector<int>& nums1, const std::vector<int>& nums2) {
    std::unordered_map<int, int> freq1, freq2;
    for (int num : nums1) {
        freq1[num]++;
    }
    for (int num : nums2) {
        freq2[num]++;
    }
    int minX = INT_MAX;
    for (auto& [num, count] : freq2) {
        if (freq1[num] < count) {
            minX = num;
        }
    }
    return minX;
}

int main() {
    std::vector<int> nums1 = {4, 20, 16, 12, 8};
    std::vector<int> nums2 = {14, 18, 10};
    int x = minX(nums1, nums2);
    std::cout << "Minimum x: " << x << std::endl;
    return 0;
}

JavaScript

function minX(nums1, nums2) {
    const freq1 = new Map();
    const freq2 = new Map();
    nums1.forEach(num => freq1.set(num, (freq1.get(num) || 0) + 1));
    nums2.forEach(num => freq2.set(num, (freq2.get(num) || 0) + 1));
    let minPossibleX = Infinity;
    for (let [num, count] of freq2.entries()) {
        if ((freq1.get(num) || 0) < count) {
            minPossibleX = num;
        }
    }
    return minPossibleX;
}

const nums1 = [4, 20, 16, 12, 8];
const nums2 = [14, 18, 10];
console.log("Minimum x:", minX(nums1, nums2));

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Helper to calculate frequency
void frequency(int* arr, int size, int* freq) {
    for (int i = 0; i < size; i++) {
        freq[arr[i]]++;
    }
}

int minX(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int freq1[1001] = {0};
    int freq2[1001] = {0};
    frequency(nums1, nums1Size, freq1);
    frequency(nums2, nums2Size, freq2);
    int minX = INT_MAX;
    for (int i = 0; i <= 1000; i++) {
        if (freq1[i] < freq2[i]) {
            minX = i;
        }
    }
    return minX;
}

int main() {
    int nums1[] = {4, 20, 16, 12, 8};
    int nums2[] = {14, 18, 10};
    int x = minX(nums1, 5, nums2, 3);
    printf("Minimum x: %d\n", x);
    return 0;
}

using System;
using System.Collections.Generic;

class Solution {
    public static int MinX(int[] nums1, int[] nums2) {
        Dictionary<int, int> freq1 = new Dictionary<int, int>();
        Dictionary<int, int> freq2 = new Dictionary<int, int>();
        foreach (int num in nums1) {
            if (!freq1.ContainsKey(num)) freq1[num] = 0;
            freq1[num]++;
        }
        foreach (int num in nums2) {
            if (!freq2.ContainsKey(num)) freq2[num] = 0;
            freq2[num]++;
        }
        int minX = int.MaxValue;
        foreach (var kvp in freq2) {
            int num = kvp.Key;
            if (!freq1.ContainsKey(num) || freq1[num] < freq2[num]) {
                minX = Math.Min(minX, num);
            }
        }
        return minX;
    }

    static void Main() {
        int[] nums1 = {4, 20, 16, 12, 8};
        int[] nums2 = {14, 18, 10};
        Console.WriteLine("Minimum x: " + MinX(nums1, nums2));
    }
}

Utilize Python's Counter to count occurrences. Compare counts to align them using candidate adjustments.

Complexity

Time Complexity: O(n).
Space Complexity: O(k).

Try this approach in the editor

Approach 3: Sorting + Enumeration + Two Pointers

First, we sort the arrays nums1 and nums2. Since we need to remove two elements from nums1, we only need to consider the first three elements of nums1, denoted as a_1, a_2, a_3. We can enumerate the first element b_1 of nums2, then we can get x = b_1 - a_i, where i \in {1, 2, 3}. Then we can use the two pointers method to determine whether there exists an integer x that makes nums1 and nums2 equal, and take the smallest x that satisfies the condition.

The time complexity is O(n times log n), and the space complexity is O(log n). Where n is the length of the array.

TypeScript

function minimumAddedInteger(nums1: number[], nums2: number[]): number {
    nums1.sort((a, b) => a - b);
    nums2.sort((a, b) => a - b);
    const f = (x: number): boolean => {
        let [i, j, cnt] = [0, 0, 0];
        while (i < nums1.length && j < nums2.length) {
            if (nums2[j] - nums1[i] !== x) {
                ++cnt;
            } else {
                ++j;
            }
            ++i;
        }
        return cnt <= 2;
    };
    let ans = Infinity;
    for (let i = 0; i < 3; ++i) {
        const x = nums2[0] - nums1[i];
        if (f(x)) {
            ans = Math.min(ans, x);
        }
    }
    return ans;
}

func minimumAddedInteger(nums1 []int, nums2 []int) int {
	sort.Ints(nums1)
	sort.Ints(nums2)
	ans := 1 << 30
	f := func(x int) bool {
		i, j, cnt := 0, 0, 0
		for i < len(nums1) && j < len(nums2) {
			if nums2[j]-nums1[i] != x {
				cnt++
			} else {
				j++
			}
			i++
		}
		return cnt <= 2
	}
	for _, a := range nums1[:3] {
		x := nums2[0] - a
		if f(x) {
			ans = min(ans, x)
		}
	}
	return ans
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Sorting and Two-Pointer Technique	Time Complexity: O(n log n). Space Complexity: O(1).
Difference and Hashmap	Time Complexity: O(n). Space Complexity: O(k).
Sorting + Enumeration + Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Sorting + Two Pointers	O(n log n)	O(1)	Best general solution; simple validation after sorting
Difference Enumeration + HashMap	O(n log n)	O(n)	Useful when verifying matches using frequency counts

Frequently asked questions

Is Find the Integer Added to Array II easy or hard?

Find the Integer Added to Array II is classified as a Medium problem. The challenge comes from recognizing that only three candidates for the added integer need to be tested and implementing a clean validation step that allows skipping exactly two elements.

Find the Integer Added to Array II Python/Java solution

Most implementations follow the same logic across languages: sort nums1 and nums2, enumerate up to three candidate values for x, and validate each using two pointers or a hashmap. The algorithm translates cleanly to Python, Java, C++, C#, and JavaScript with identical O(n log n) complexity.

How to solve Find the Integer Added to Array II in O(n)?

A strict O(n) solution is difficult because ordering simplifies the matching process after removing two elements. Most practical implementations sort the arrays first, leading to O(n log n) complexity. After sorting, candidate values for x are tested using a single linear pass with two pointers.

What is the best approach for Find the Integer Added to Array II?

The most efficient and commonly expected solution is sorting combined with a two-pointer validation. After sorting both arrays, try up to three candidates for the added integer x based on aligning nums2[0] with the first three elements of nums1. Each candidate is validated with a linear scan while skipping at most two elements from nums1. The overall complexity is O(n log n) due to sorting and O(1) extra space.

Is Find the Integer Added to Array II asked at Google/Amazon/Meta?

Array alignment and difference-enumeration problems appear frequently in interviews at large tech companies such as Google, Amazon, and Meta. Variants that involve sorting, removing elements, or validating transformations with two pointers are common in mid-level algorithm interviews.

What data structure is used in Find the Integer Added to Array II?

The problem primarily uses arrays with sorting and a two-pointer scanning technique. An alternative approach uses a hash map (frequency map) to count occurrences in nums2 and verify matches after applying the candidate integer shift.

What is the time complexity of Find the Integer Added to Array II?

The optimal solution runs in O(n log n) time because both arrays are sorted before validation. After sorting, only three candidate values of x are checked, and each check scans the arrays once in O(n). The space complexity can be O(1) if the two-pointer technique is used.

Find the Integer Added to Array II solution and explanation

The problem

Approach overview

Approach 1: Sorting and Two-Pointer Technique

Approach 2: Difference and Hashmap

Approach 3: Sorting + Enumeration + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Find the Integer Added to Array II solution and explanation

The problem

Approach overview

Approach 1: Sorting and Two-Pointer Technique

Approach 2: Difference and Hashmap

Approach 3: Sorting + Enumeration + Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems