3131. Find the Integer Added to Array I

Problem Description

You are given two arrays nums1 and nums2 that have equal length.

The array nums1 has been transformed by adding the same integer value x to every element in it. After this transformation, nums1 becomes equal to nums2.

Two arrays are considered equal when they contain exactly the same integers with the same frequencies (the same numbers appearing the same number of times).

Your task is to find and return the integer x that was added to each element of nums1 to make it equal to nums2.

For example:

If nums1 = [1, 2, 3] and nums2 = [4, 5, 6], then x = 3 because adding 3 to each element of nums1 gives us [4, 5, 6] which equals nums2.
If nums1 = [-5, 0, 2] and nums2 = [-2, 3, 5], then x = 3 because adding 3 to each element gives us [-2, 3, 5].

The solution recognizes that since the same value x is added to every element in nums1, the difference between any corresponding elements will be constant. The simplest approach is to find the minimum values in both arrays and calculate their difference: x = min(nums2) - min(nums1).

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

Since we're adding the same value x to every element in nums1 to get nums2, we can think about what this transformation does to the array as a whole.

When we add a constant to every element in an array, we're essentially shifting the entire array by that constant amount. The relative positions and differences between elements remain unchanged - we're just moving everything up or down by the same amount.

This means that if we look at any specific element in nums1 and its corresponding element in nums2 (after the arrays are sorted), the difference between them will always be x.

For instance, if nums1 = [2, 5, 8] and we add x = 3, we get [5, 8, 11]. Notice that:

5 - 2 = 3
8 - 5 = 3
11 - 8 = 3

Every corresponding pair has the same difference of 3.

The key insight is that we can pick any corresponding pair of elements to find x. The simplest choice is to use the minimum elements from both arrays. Why? Because:

Finding the minimum is a straightforward operation
After adding x to all elements in nums1, the minimum of nums1 will become the minimum of nums2

Therefore, x = min(nums2) - min(nums1) gives us the exact value that was added to transform nums1 into nums2.

Solution Approach

The implementation is remarkably straightforward once we understand the relationship between the two arrays.

Since adding the same constant x to every element in nums1 produces nums2, we can express this mathematically as:

For every element at index i: nums2[i] = nums1[i] + x
Rearranging: x = nums2[i] - nums1[i]

This means x can be calculated using any corresponding pair of elements. The solution chooses to use the minimum elements from both arrays.

Algorithm Steps:

Find the minimum element in nums2 using min(nums2)
Find the minimum element in nums1 using min(nums1)
Calculate the difference: x = min(nums2) - min(nums1)
Return x

Why this works:

When we add x to every element in nums1, the smallest element in nums1 becomes min(nums1) + x
This transformed minimum must equal the minimum in nums2, so: min(nums1) + x = min(nums2)
Therefore: x = min(nums2) - min(nums1)

Time Complexity: O(n) where n is the length of the arrays, as we need to scan through both arrays once to find their minimum values.

Space Complexity: O(1) as we only use a constant amount of extra space to store the minimum values.

The beauty of this solution lies in its simplicity - instead of checking all elements or sorting the arrays, we leverage the mathematical property that the difference between corresponding elements remains constant after the transformation.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to see how this solution works.

Given:

nums1 = [7, 3, 10, 5]
nums2 = [11, 7, 14, 9]

Step 1: Find the minimum element in nums1 Looking through nums1 = [7, 3, 10, 5]:

Compare: 7, 3, 10, 5
The minimum is 3

Step 2: Find the minimum element in nums2 Looking through nums2 = [11, 7, 14, 9]:

Compare: 11, 7, 14, 9
The minimum is 7

Step 3: Calculate x Using the formula x = min(nums2) - min(nums1):

x = 7 - 3 = 4

Step 4: Verify our answer Let's add 4 to each element in nums1:

7 + 4 = 11 ✓
3 + 4 = 7 ✓
10 + 4 = 14 ✓
5 + 4 = 9 ✓

The transformed array [11, 7, 14, 9] exactly matches nums2.

Key Observation: Notice that if we had picked any other corresponding elements (after sorting), we'd get the same answer:

Sorted nums1: [3, 5, 7, 10]
Sorted nums2: [7, 9, 11, 14]
Differences: 7-3=4, 9-5=4, 11-7=4, 14-10=4

Every pair gives us the same difference of 4, confirming that using the minimum elements is both correct and efficient.

Solution Implementation

1class Solution:
2    def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
3        """
4        Find the integer x that was added to every element in nums1 to get nums2.
5      
6        Since the same integer x is added to all elements of nums1 to get nums2,
7        the difference between corresponding elements remains constant.
8        We can find x by calculating the difference between the minimum values
9        of both arrays.
10      
11        Args:
12            nums1: First list of integers
13            nums2: Second list of integers (result of adding x to each element of nums1)
14          
15        Returns:
16            The integer x that was added to nums1 to get nums2
17        """
18        # Find the minimum value in nums2
19        min_nums2 = min(nums2)
20      
21        # Find the minimum value in nums1
22        min_nums1 = min(nums1)
23      
24        # The difference between minimums gives us the added integer
25        # Since: nums2[i] = nums1[i] + x for all i
26        # Therefore: min(nums2) = min(nums1) + x
27        # So: x = min(nums2) - min(nums1)
28        return min_nums2 - min_nums1
29

1class Solution {
2    /**
3     * Finds the integer that was added to each element of nums1 to get nums2.
4     * The added integer is calculated as the difference between the minimum values
5     * of the two arrays.
6     * 
7     * @param nums1 the original array
8     * @param nums2 the array after adding a constant integer to each element of nums1
9     * @return the integer that was added to transform nums1 to nums2
10     */
11    public int addedInteger(int[] nums1, int[] nums2) {
12        // Find the minimum value in nums2
13        int minNums2 = Arrays.stream(nums2)
14                .min()
15                .getAsInt();
16      
17        // Find the minimum value in nums1
18        int minNums1 = Arrays.stream(nums1)
19                .min()
20                .getAsInt();
21      
22        // Calculate and return the difference between the two minimum values
23        // This represents the constant integer added to each element
24        return minNums2 - minNums1;
25    }
26}
27

1class Solution {
2public:
3    int addedInteger(vector<int>& nums1, vector<int>& nums2) {
4        // Find the minimum element in nums2 array
5        int min_nums2 = *min_element(nums2.begin(), nums2.end());
6      
7        // Find the minimum element in nums1 array
8        int min_nums1 = *min_element(nums1.begin(), nums1.end());
9      
10        // The added integer is the difference between the minimum values
11        // This works because the same integer is added to all elements of nums1 to get nums2
12        // Therefore: min(nums2) = min(nums1) + x, where x is the added integer
13        // Solving for x: x = min(nums2) - min(nums1)
14        return min_nums2 - min_nums1;
15    }
16};
17

1/**
2 * Finds the integer that was added to each element of nums1 to get nums2
3 * @param nums1 - The original array of numbers
4 * @param nums2 - The resulting array after adding a constant to each element of nums1
5 * @returns The integer that was added to transform nums1 to nums2
6 */
7function addedInteger(nums1: number[], nums2: number[]): number {
8    // Find the minimum value in nums2
9    const minValueInNums2: number = Math.min(...nums2);
10  
11    // Find the minimum value in nums1
12    const minValueInNums1: number = Math.min(...nums1);
13  
14    // The difference between the minimum values gives us the added integer
15    // Since the same integer is added to all elements, the difference between
16    // any corresponding elements would be the same, including the minimums
17    const addedValue: number = minValueInNums2 - minValueInNums1;
18  
19    return addedValue;
20}
21

Time and Space Complexity

The time complexity is O(n), where n is the length of the arrays. This is because the min() function needs to traverse through all elements in each array once to find the minimum value. Specifically, min(nums2) takes O(n) time and min(nums1) takes O(n) time, resulting in O(n) + O(n) = O(2n) = O(n) overall time complexity.

The space complexity is O(1). The algorithm only uses a constant amount of extra space to store the minimum values and compute their difference, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Array Equality

The Problem: A common misconception is thinking that nums1 and nums2 must have elements in the same order. Developers might incorrectly try to calculate x as nums2[0] - nums1[0], assuming the arrays are already aligned.

Why It's Wrong: The problem states that arrays are equal when they contain the same integers with the same frequencies, not necessarily in the same order. For example:

nums1 = [3, 1, 2] and nums2 = [5, 6, 4]
Using nums2[0] - nums1[0] = 5 - 3 = 2 would be incorrect
The correct answer is x = 3 (min difference: 4 - 1 = 3)

Solution: Always use a position-independent metric like the minimum values of both arrays, which remains consistent regardless of element ordering.

Pitfall 2: Not Handling Duplicate Values

The Problem: Some might worry that duplicate values in the arrays could affect the calculation or think special handling is needed for repeated elements.

Why It's a Non-Issue: The algorithm using minimum values naturally handles duplicates correctly. Even if multiple elements have the minimum value, the relationship min(nums2) = min(nums1) + x still holds true.

Example:

nums1 = [1, 1, 3, 5] and nums2 = [4, 4, 6, 8]
Despite duplicates, x = min(nums2) - min(nums1) = 4 - 1 = 3 works perfectly

Pitfall 3: Attempting to Sort or Match Elements

The Problem: Developers might overcomplicate the solution by:

Sorting both arrays first to align elements
Creating frequency maps to match elements
Using more complex algorithms to find corresponding pairs

Why It's Inefficient: These approaches add unnecessary complexity:

Sorting takes O(n log n) time vs. O(n) for finding minimums
Frequency mapping requires additional space and logic
The mathematical property that all differences are equal makes these approaches redundant

Better Approach: Trust the mathematical insight that adding a constant preserves relative differences, making the minimum-based calculation both sufficient and optimal.

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12

1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

<=, left, right

<, left, right

<=, right, left

<, right, left

I don't know