3132. Find the Integer Added to Array II LeetCode Solution

Last updated: March 6, 2025

In this guide, you will get 3132. Find the Integer Added to Array II LeetCode Solution with the best time and space complexity. The solution to Find the Integer Added to Array II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Find the Integer Added to Array II solution in C++
Find the Integer Added to Array II solution in Java
Find the Integer Added to Array II solution in Python
Additional Resources

3132. Find the Integer Added to Array II LeetCode Solution image

Problem Statement of Find the Integer Added to Array II

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.

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

3132. Find the Integer Added to Array II LeetCode Solution in C++

class Solution {
 public:
  int minimumAddedInteger(vector<int>& nums1, vector<int>& nums2) {
    // After removing two elements from nums1, either nums1[0], nums1[1], or
    // nums1[2] will persist. Therefore, the difference between nums1 (with two
    // elements removed) and nums2 is represented by nums2[0] - nums1[i], where
    // 0 <= i <= 2.
    int ans = INT_MAX;

    ranges::sort(nums1);
    ranges::sort(nums2);

    for (int i = 0; i < 3; ++i) {
      const int inc = nums2[0] - nums1[i];
      if (isValidDiff(nums1, nums2, inc))
        ans = min(ans, inc);
    }

    return ans;
  }

 private:
  // Returns true if it's possible to increase nums1 (with two elements removed)
  // by `inc` to nums2.
  bool isValidDiff(const vector<int>& nums1, const vector<int>& nums2,
                   int inc) {
    int removed = 0;
    int i = 0;  // nums2's index

    for (const int num : nums1)
      if (num + inc == nums2[i]) {
        if (++i == nums2.size())
          break;
      } else {
        ++removed;
      }

    return removed <= 2;
  }
};
/* code provided by PROGIEZ */

3132. Find the Integer Added to Array II LeetCode Solution in Java

class Solution {
  public int minimumAddedInteger(int[] nums1, int[] nums2) {
    // After removing two elements from nums1, either nums1[0], nums1[1], or
    // nums1[2] will persist. Therefore, the difference between nums1 (with two
    // elements removed) and nums2 is represented by nums2[0] - nums1[i], where
    // 0 <= i <= 2.
    int ans = Integer.MAX_VALUE;

    Arrays.sort(nums1);
    Arrays.sort(nums2);

    for (int i = 0; i < 3; ++i) {
      final int inc = nums2[0] - nums1[i];
      if (isValidDiff(nums1, nums2, inc))
        ans = Math.min(ans, inc);
    }

    return ans;
  }

  // Returns true if it's possible to increase nums1 (with two elements removed)
  // by `inc` to nums2.
  private boolean isValidDiff(int[] nums1, int[] nums2, int inc) {
    int removed = 0;
    int i = 0; // nums2's index

    for (final int num : nums1)
      if (num + inc == nums2[i]) {
        if (++i == nums2.length)
          break;
      } else {
        ++removed;
      }

    return removed <= 2;
  }
}
// code provided by PROGIEZ

3132. Find the Integer Added to Array II LeetCode Solution in Python

class Solution:
  def minimumAddedInteger(self, nums1: list[int], nums2: list[int]) -> int:
    # After removing two elements from nums1, either nums1[0], nums1[1], or
    # nums1[2] will persist. Therefore, the difference between nums1 (with two
    # elements removed) and nums2 is represented by nums2[0] - nums1[i], where
    # 0 <= i <= 2.
    ans = math.inf

    nums1.sort()
    nums2.sort()

    for i in range(3):
      inc = nums2[0] - nums1[i]
      if self._isValidDiff(nums1, nums2, inc):
        ans = min(ans, inc)

    return ans

  def _isValidDiff(self, nums1: list[int], nums2: list[int], inc: int) -> bool:
    """
    Returns True if it's possible to increase nums1 (with two elements removed)
    by `inc` to nums2.
    """
    removed = 0
    i = 0  # nums2's index

    for num in nums1:
      if num + inc == nums2[i]:
        i += 1
        if i == len(nums2):
          break
      else:
        removed += 1

    return removed <= 2
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents