Find the Integer Added to Array II
MedPrompt
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 <= 200nums2.length == nums1.length - 20 <= nums1[i], nums2[i] <= 1000- The test cases are generated in a way that there is an integer
xsuch thatnums1can become equal tonums2by removing two elements and addingxto each element ofnums1.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach systematically considers every possible pair of elements to remove from nums1. For each choice, it calculates the required integer x and verifies if this x transforms the remaining n-2 elements of nums1 into nums2. The minimum valid x found is the answer.
Algorithm
- Sort both
nums1andnums2arrays. - Initialize a variable
min_xto a very large value to store the minimum possiblex. - Use nested loops to iterate through every possible pair of indices
(i, j)fromnums1. These two indices represent the elements to be removed. - For each pair
(i, j): a. Create a temporary list,temp, containing all elements ofnums1except fornums1[i]andnums1[j]. b. Sincenums1was sorted,tempwill also be sorted. Calculate a potential differencexby comparing the first elements:x = nums2[0] - temp.get(0). c. Verify if thisxis valid for all other elements. Iterate fromk = 1tonums2.length - 1and check ifnums2[k] - temp.get(k)is equal tox. d. If the difference is consistent for all elements, it means we have found a validx. Updatemin_x = min(min_x, x). - After checking all possible pairs to remove, return
min_x.
Walkthrough
The fundamental idea is to exhaust all possibilities. Since we know two elements are removed from nums1, we can try removing every unique pair of elements. To make the verification step easier, we first sort both nums1 and nums2. Sorting ensures that if a valid transformation exists, the remaining n-2 elements from nums1 (after adding x) will match nums2 in the same sorted order.
We use two nested loops to select two distinct indices, i and j, from nums1. We then construct a temporary array temp containing the elements of nums1 that were not at indices i and j. With temp and nums2 (both sorted and of the same length), we can determine the potential value of x. The difference x = nums2[0] - temp[0] must hold for all corresponding pairs of elements. We check this condition. If it holds, the calculated x is a valid candidate, and we update our minimum x found so far. By iterating through all O(n^2) pairs, we are guaranteed to find the correct transformation and thus the minimum x.
import java.util.ArrayList;import java.util.Arrays;import java.util.List; class Solution { public int minimumAddedInteger(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int n = nums1.length; int minX = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { // Create a temporary list of nums1 after removing elements at i and j List<Integer> temp = new ArrayList<>(); for (int k = 0; k < n; k++) { if (k != i && k != j) { temp.add(nums1[k]); } } // Check if this temporary list can be transformed into nums2 int diff = nums2[0] - temp.get(0); boolean possible = true; for (int k = 1; k < nums2.length; k++) { if (nums2[k] - temp.get(k) != diff) { possible = false; break; } } if (possible) { minX = Math.min(minX, diff); } } } return minX; }}Complexity
Time
O(n^3), where n is the length of `nums1`. Sorting takes O(n log n). The two nested loops iterate O(n^2) times. Inside the loops, creating the temporary list and checking the difference both take O(n) time, leading to a total of O(n^3).
Space
O(n), where n is the length of `nums1`. This is for storing the temporary list `temp` which has a size of `n-2`.
Trade-offs
Pros
It is a straightforward and easy-to-understand implementation of the problem statement.
It is guaranteed to be correct as it explores the entire search space of removed elements.
Cons
The time complexity of O(n^3) is inefficient and may not pass for larger constraints, although it works for the given constraints (n <= 200).
Solutions
Solution
class Solution {public int minimumAddedInteger(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int ans = 1 << 30; for (int i = 0; i < 3; ++i) { int x = nums2[0] - nums1[i]; if (f(nums1, nums2, x)) { ans = Math.min(ans, x); } } return ans; }private boolean f(int[] nums1, int[] nums2, int x) { int i = 0, j = 0, cnt = 0; while (i < nums1.length && j < nums2.length) { if (nums2[j] - nums1[i] != x) { ++cnt; } else { ++j; } ++i; } return cnt <= 2; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.