Problem Description

You have two integer arrays: nums1 and nums2. The array nums2 was created from nums1 through the following process:

1. Two elements were removed from nums1
2. All remaining elements were modified by adding the same integer value x (which can be positive, negative, or zero)

After these operations, the modified nums1 becomes equal to nums2. Two arrays are considered equal when they contain the same integers with the same frequencies (the same numbers appearing the same number of times).

Your task is to find the minimum possible integer value of x that can achieve this transformation.

For example, if nums1 = [4, 6, 3, 1, 4, 2, 10, 9, 5] and nums2 = [5, 10, 3, 2, 6, 1, 9], you would need to:

• Remove two elements from nums1 (in this case, remove 4 and 4)
• Add x = -1 to all remaining elements: [3, 5, 2, 0, 1, 9, 8, 4] which after sorting becomes [0, 1, 2, 3, 4, 5, 8, 9]
• After sorting nums2: [1, 2, 3, 5, 6, 9, 10]

The goal is to determine the smallest x value that makes this transformation possible.

Intuition

The key insight is that after sorting both arrays, the relationship between corresponding elements becomes clearer. When we remove two elements from nums1 and add x to the remaining elements, the sorted order is preserved.

Since we need to remove exactly two elements from nums1, after removal we'll have len(nums1) - 2 elements, which equals len(nums2). The critical observation is that after sorting, the first element of nums2 must correspond to one of the first three elements of the sorted nums1. Why? Because we can remove at most two elements, so at least one of the first three elements in nums1 must remain.

This means if nums1 is sorted as [a₁, a₂, a₃, ...] and nums2 is sorted as [b₁, b₂, ...], then b₁ must equal either a₁ + x, a₂ + x, or a₃ + x. This gives us only three possible values of x to check:

• x = b₁ - a₁
• x = b₁ - a₂
• x = b₁ - a₃

For each candidate value of x, we can verify if it's valid using a two-pointer approach. We traverse through nums1 and try to match each element in nums2 by checking if nums1[i] + x = nums2[j]. If they match, we move both pointers forward. If they don't match, we only move the pointer in nums1 forward (simulating the removal of that element). If we can match all elements of nums2 with at most 2 mismatches in nums1, then this x value is valid.

Among all valid x values, we return the minimum one.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The implementation follows a systematic approach using sorting, enumeration, and two pointers:

Step 1: Sort Both Arrays

nums1.sort()
nums2.sort()

Sorting helps establish a clear correspondence between elements after the transformation.

Step 2: Define a Validation Function The helper function f(x) checks if a given value of x can transform nums1 into nums2:

def f(x: int) -> bool:
    i = j = cnt = 0
    while i < len(nums1) and j < len(nums2):
        if nums2[j] - nums1[i] != x:
            cnt += 1  # Count mismatches (elements to remove)
        else:
            j += 1    # Match found, move to next element in nums2
        i += 1        # Always move forward in nums1
    return cnt <= 2   # Valid if we remove at most 2 elements

The function uses two pointers:

• i traverses through nums1
• j traverses through nums2
• cnt tracks how many elements from nums1 don't match (need to be removed)

When nums2[j] - nums1[i] = x, it means nums1[i] + x = nums2[j], indicating a valid match. Otherwise, we consider nums1[i] as one of the elements to remove.

Step 3: Enumerate Possible Values of x

ans = inf
for i in range(3):
    x = nums2[0] - nums1[i]
    if f(x):
        ans = min(ans, x)
return ans

We only need to check three possible values of x:

• x = nums2[0] - nums1[0]: assumes first element of nums1 remains
• x = nums2[0] - nums1[1]: assumes first element is removed, second remains
• x = nums2[0] - nums1[2]: assumes first two elements are removed, third remains

For each valid x, we update the answer with the minimum value found.

The time complexity is O(n log n) for sorting, where n is the length of nums1. The validation function runs in O(n) time and is called at most 3 times, so the overall complexity remains O(n log n).

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

• nums1 = [3, 5, 5, 3]
• nums2 = [7, 7]

Step 1: Sort both arrays

• Sorted nums1 = [3, 3, 5, 5]
• Sorted nums2 = [7, 7]

Step 2: Identify possible x values

Since we need to remove exactly 2 elements from nums1, at least one of the first three elements must remain to become nums2[0] = 7. This gives us three candidates:

• x₁ = nums2[0] - nums1[0] = 7 - 3 = 4
• x₂ = nums2[0] - nums1[1] = 7 - 3 = 4
• x₃ = nums2[0] - nums1[2] = 7 - 5 = 2

Step 3: Validate each x value

Testing x = 4: Using two pointers to check if we can match nums2 by adding 4 to elements of nums1:

Result: Successfully matched all of nums2 with 2 removals from nums1. x = 4 is valid.

Testing x = 2: Using two pointers to check if we can match nums2 by adding 2 to elements of nums1:

Result: Successfully matched all of nums2 with 2 removals from nums1. x = 2 is valid.

Step 4: Return the minimum valid x

Both x = 4 and x = 2 are valid. The minimum is x = 2.

We can verify: Remove the two 3's from nums1 = [3, 3, 5, 5], leaving [5, 5]. Adding 2 gives [7, 7], which equals nums2.

Solution Implementation

Time and Space Complexity

The time complexity of this solution is O(n × log n), where n is the length of the array nums1.

Breaking down the time complexity:

• Sorting nums1 takes O(n × log n) time
• Sorting nums2 takes O((n-2) × log(n-2)) time, which simplifies to O(n × log n) since nums2 has length n-2
• The outer loop runs at most 3 times (constant)
• Inside each iteration, the function f(x) is called, which performs a two-pointer traversal through both arrays in O(n) time
• Therefore, the loop contributes O(3 × n) = O(n) to the complexity

The dominant operation is the sorting step, giving us an overall time complexity of O(n × log n).

The space complexity is O(log n). This comes from:

• The sorting algorithms (typically implementations like Timsort in Python) use O(log n) space for the recursion stack or auxiliary space
• The function f(x) only uses a constant amount of extra space with variables i, j, and cnt
• No additional data structures proportional to input size are created

Therefore, the space complexity is O(log n), dominated by the sorting algorithm's space requirements.

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

Common Pitfalls

1. Incorrect Assumption About Which Elements to Remove

Pitfall: A common mistake is assuming we need to find and explicitly identify which two elements to remove from nums1. This leads to complex code trying all possible combinations of removing 2 elements from nums1.

Why it happens: The problem statement mentions "removing two elements," which naturally leads to thinking about combinations like C(n,2).

Correct Approach: Instead of explicitly removing elements, we use a two-pointer technique that implicitly handles removal by counting mismatches. The key insight is that after sorting, if we fix the value of x, we can greedily match elements from left to right.

2. Not Considering All Necessary Values of x

Pitfall: Only checking x = nums2[0] - nums1[0] or trying random values of x.

# Wrong approach - only checks one value
def minimumAddedInteger(nums1, nums2):
    nums1.sort()
    nums2.sort()
    x = nums2[0] - nums1[0]
    # This misses cases where nums1[0] needs to be removed

Solution: Since we can remove at most 2 elements, at least one of the first 3 elements in sorted nums1 must remain and map to nums2[0]. Therefore, we only need to check:

• x = nums2[0] - nums1[0]
• x = nums2[0] - nums1[1]
• x = nums2[0] - nums1[2]

3. Forgetting to Sort Both Arrays

Pitfall: Attempting to solve without sorting leads to incorrect matching logic.

# Wrong - without sorting, matching becomes ambiguous
def can_match(nums1, nums2, x):
    # Which element in nums1 should match which in nums2?
    # This becomes an NP-hard assignment problem

Solution: Always sort both arrays first. This establishes a clear order and allows the greedy two-pointer approach to work correctly.

4. Off-by-One Errors in the Validation Function

Pitfall: Incorrectly handling the pointer movements or removal count.

# Common mistake - incrementing removed_count in wrong place
def can_match_with_difference(target_diff):
    while nums1_idx < len(nums1) and nums2_idx < len(nums2):
        if nums2[nums2_idx] - nums1[nums1_idx] == target_diff:
            nums2_idx += 1
            removed_count += 1  # Wrong! This counts matches, not removals
        nums1_idx += 1

Solution: Only increment removed_count when elements DON'T match (need to be removed), and only increment nums2_idx when elements DO match.

5. Not Handling Edge Cases with Array Lengths

Pitfall: The validation function might not correctly handle the case where we've gone through all of nums2 but still have elements left in nums1.

Solution: The condition removed_count <= 2 implicitly handles this because any remaining elements in nums1 after matching all of nums2 are counted as removals in our traversal.