Skip to main content
Talentd

Find the Integer Added to Array II - Solution & Explanation

MediumArrayTwo PointersSortingEnumeration16 min readAsked at: Mitsogo
Practice this problem

Problem Statement

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

Sort `nums1` and `nums2`. Consider each potential element `x` as making the first of `nums2` equal to `nums1[i]`. This strategy helps find the required increment or decrement amount.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if in-place sorting is considered.

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.

Count each integer's frequency in both arrays using arrays as hashmaps. Compute potential `x` based on imbalances in frequencies.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(k), where k is the range of possible element values.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting and Two-Pointer Technique

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if in-place sorting is considered.

Difference and Hashmap

Time Complexity: O(n).
Space Complexity: O(k), where k is the range of possible element values.

Sorting + Enumeration + Two Pointers—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Two PointersO(n log n)O(1)Best general solution; simple validation after sorting
Difference Enumeration + HashMapO(n log n)O(n)Useful when verifying matches using frequency counts

Video Solution

3132 & 3131 Find the Integer Added to Array II | 3131. Find the Integer Added to Array I • Aryan Mittal • 4,211 views views

Watch 8 more video solutions →

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.

Ready to solve this problem?

Practice Find the Integer Added to Array II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays