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

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:

1. Finding the minimum is a straightforward operation
2. 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:

1. Find the minimum element in nums2 using min(nums2)
2. Find the minimum element in nums1 using min(nums1)
3. Calculate the difference: x = min(nums2) - min(nums1)
4. 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.

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

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:

1. Sorting both arrays first to align elements
2. Creating frequency maps to match elements
3. 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.