3132 & 3131 Find the Integer Added to Array II | 3131. Find the Integer Added to Array I
Find the Integer Added to Array I - Video Solution
Watch 10 video solutions for Find the Integer Added to Array I, a easy level problem involving Array. This walkthrough by Aryan Mittal has 4,211 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given two arrays of equal length, nums1 and nums2.
Each element in nums1 has 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 integer x.
Example 1:
Input: nums1 = [2,6,4], nums2 = [9,7,5]
Output: 3
Explanation:
The integer added to each element of nums1 is 3.
Example 2:
Input: nums1 = [10], nums2 = [5]
Output: -5
Explanation:
The integer added to each element of nums1 is -5.
Example 3:
Input: nums1 = [1,1,1,1], nums2 = [1,1,1,1]
Output: 0
Explanation:
The integer added to each element of nums1 is 0.
Constraints:
1 <= nums1.length == nums2.length <= 1000 <= nums1[i], nums2[i] <= 1000- The test cases are generated in a way that there is an integer
xsuch thatnums1can become equal tonums2by addingxto each element ofnums1.
Approach Overview
Problem Overview: You receive two integer arrays nums1 and nums2. Every element in nums1 had the same integer added to it, producing nums2. Your job is to determine that integer. The order of elements may differ, so the solution relies on properties that remain unchanged when a constant value is added to every element.
Approach 1: Difference Calculation Approach (O(n) time, O(1) space)
The key observation: adding the same integer x to every element shifts the entire array by the same amount. The smallest value in nums1 becomes the smallest value in nums2 after adding x. Compute min(nums1) and min(nums2), then return x = min(nums2) - min(nums1). This works even if the arrays are reordered because the relative ordering of elements does not change after adding a constant. You only need one pass to compute the minimum of each array, making this a clean linear-time solution using basic array traversal.
Approach 2: Average Difference Approach (O(n) time, O(1) space)
Another property of adding a constant to all elements is that the total sum increases by n * x, where n is the array length. Compute sum(nums1) and sum(nums2), then derive the value using x = (sum(nums2) - sum(nums1)) / n. This approach relies on simple arithmetic and avoids sorting or element comparisons. It’s essentially a math-based observation applied during a single pass through the arrays.
Recommended for interviews: The Difference Calculation approach is typically preferred because it is simple, intuitive, and avoids division. Interviewers expect you to recognize that adding a constant shifts the minimum value by the same amount. The Average Difference method also works and demonstrates a good understanding of array sums, but the minimum-difference observation usually surfaces faster during interviews.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Difference Calculation (Min Difference) | O(n) | O(1) | Best general solution. Works even if arrays are reordered and requires only min comparisons. |
| Average Difference (Sum Method) | O(n) | O(1) | Useful when reasoning with sums or when minimum values are not directly considered. |