3132. Find the Integer Added to Array II

MediumArrayTwo PointersEnumerationSorting

Problem Description

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.

Intuition

The key insight for solving this problem is understanding that we can manipulate the entire array nums1 by a constant x to try and make it match nums2. However, since two elements have been removed from nums1, we have some flexibility. The challenge is finding the minimal x that achieves this match.

To intuitively arrive at a solution, a sensible approach is:

Sort both arrays: By sorting nums1 and nums2, we can easily see corresponding positions and use them easier in calculations, especially considering sorted elements can be directly compared for differences.
Focus on the First Few Elements of nums1: Since two elements are missing from nums1, we don't need to consider the entire array. Technically, only the first three elements of the sorted nums1 need to be examined in detail because removing any two would still include one from these if there's a significant shift to match nums2.
Calculate Possible x Values: We can compute potential x values by taking the difference between the first element of nums2 and the first three elements of nums1. This gives us three candidates for x: x = nums2[0] - nums1[i] for i in 0, 1, or 2.
Validate Each x Using Two Pointers: For each candidate of x, apply a two-pointer approach to check if the adjusted nums1 potentially matches nums2 after accounting for two omissions. If so, update the minimum x found.

By systematically enumerating and validating possible transformations via sorting and two-pointer logic, we efficiently find the minimal adjustment needed.

Learn more about Two Pointers and Sorting patterns.

Solution Approach

The solution utilizes a combination of sorting, enumeration, and the two-pointer technique to efficiently determine the minimal x required to make nums1 match nums2.

Sorting: Start by sorting both arrays nums1 and nums2. This allows direct positional comparison and simplifies the pointer operations.
Enumeration of x:
- Since two elements are missing from nums1, and the rest might have been adjusted by x, calculate potential adjustments x by considering the difference between the first element of nums2 and the first three elements of nums1.
- Compute x as x = nums2[0] - nums1[i] for i in {0, 1, 2}.
Two-Pointer Verification:
- For each candidate x, verify if this transformation could lead to nums1 being equal to nums2 by simulating the adjustment using a two-pointer method.
- Initialize two pointers, i for nums1 and j for nums2, and a counter cnt to track mismatches.
- Traverse through nums1 comparing each transformed element (nums1[i] + x) with the corresponding element in nums2.
- If the values do not align, increment cnt. If they do, move both pointers forward.
- This check ensures at most two mismatches (allowing for the two removed elements).
Select the Minimum x:
- If cnt is less than or equal to 2 for any candidate x, update the record of minimum x.
- Return this smallest valid x that allows nums1 to potentially match nums2 after adjustment and two-element removal.

This approach efficiently narrows down potential adjustments by evaluating only a limited set of transformation scenarios and ensures correctness through a simple comparison logic, balanced by the constraints that allow two unmatching elements.

Ready to land your dream job?

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

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach with an example.

Suppose we have:

nums1 = [2, 4, 6, 8, 10]
nums2 = [8, 10, 12]

Two elements have been removed from nums1, and the remaining elements have been adjusted by an integer x. Our goal is to determine the minimum x such that the adjusted nums1 becomes equal to nums2.

Sorting:
- nums1 is already sorted as [2, 4, 6, 8, 10].
- nums2 is sorted as [8, 10, 12].
Enumeration of x:
- Consider potential x from the differences between the first element of nums2 and the first three elements of nums1.
- Calculate candidate x values:
  - x1 = nums2[0] - nums1[0] = 8 - 2 = 6
  - x2 = nums2[0] - nums1[1] = 8 - 4 = 4
  - x3 = nums2[0] - nums1[2] = 8 - 6 = 2
Two-Pointer Verification:

We will verify each candidate x.
- For x = 6:
  - Adjusted nums1 = [8, 10, 12, 14, 16]
  - Compare with nums2 = [8, 10, 12] using two pointers:
    - 8 == 8: move both pointers
    - 10 == 10: move both pointers
    - 12 == 12: move both pointers
  Now the comparison is complete with cnt = 0 mismatches. Hence, x = 6 is valid.
- For x = 4:
  - Adjusted nums1 = [6, 8, 10, 12, 14]
  - Compare with nums2 = [8, 10, 12] using two pointers:
    - 6 != 8: skip
    - 8 == 8: move both pointers
    - 10 == 10: move both pointers
    - 12 == 12: move both pointers
  There is one mismatch, which is acceptable. Thus, x = 4 is also valid and smaller than x = 6.
- For x = 2:
  - Adjusted nums1 = [4, 6, 8, 10, 12]
  - Compare with nums2 = [8, 10, 12]:
    - 4 != 8: skip
    - 6 != 8: skip
    - 8 == 8: move both pointers
    - 10 == 10: move both pointers
    - 12 == 12: move both pointers
  There are two mismatches, which is the allowable limit. Thus, x = 2 is valid and the minimum among the valid configurations.
Select the Minimum x:

Since x = 2 results in a valid configuration with the minimal x, we conclude that the answer is 2.

This walkthrough demonstrates the process of calculating potential x values, validating them using a two-pointer technique, and determining the smallest possible x that achieves the required transformation.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def minimumAddedInteger(self, nums1: List[int], nums2: List[int]) -> int:
6        # Helper function to check if a given difference `x` is valid
7        def is_valid_difference(x: int) -> bool:
8            i = j = cnt = 0  # Initialize pointers and count of mismatches
9            while i < len(nums1) and j < len(nums2):
10                if nums2[j] - nums1[i] != x:
11                    cnt += 1  # Increment mismatch count if difference isn't `x`
12                else:
13                    j += 1  # Move to the next element in nums2 if difference matches
14                i += 1  # Always move to the next element in nums1
15            return cnt <= 2  # True if two or fewer mismatches
16
17        # Sort both lists
18        nums1.sort()
19        nums2.sort()
20        # Initialize answer with infinity
21        min_added_integer = inf
22      
23        # Try the first 3 elements of nums1 to find the minimum difference possible
24        for i in range(3):
25            # Calculate the initial difference from the first element of nums2
26            difference = nums2[0] - nums1[i]
27            # Check if this difference is valid and update the minimum answer
28            if is_valid_difference(difference):
29                min_added_integer = min(min_added_integer, difference)
30      
31        # Return the minimum valid difference
32        return min_added_integer
33

1import java.util.Arrays;
2
3class Solution {
4    public int minimumAddedInteger(int[] nums1, int[] nums2) {
5        // Sort both input arrays
6        Arrays.sort(nums1);
7        Arrays.sort(nums2);
8
9        // Initialize answer with a large value
10        int ans = 1 << 30;  // This is equivalent to 2^30
11
12        // Check the first three elements in nums1
13        for (int i = 0; i < 3; ++i) {
14            int x = nums2[0] - nums1[i];  // Calculate the difference
15
16            // Verify if nums1 can be transformed into nums2 with difference x
17            if (f(nums1, nums2, x)) {
18                ans = Math.min(ans, x);  // Update the minimum added integer
19            }
20        }
21        return ans;
22    }
23
24    private boolean f(int[] nums1, int[] nums2, int x) {
25        int i = 0;
26        int j = 0;
27        int cnt = 0;
28
29        // Iterate over both arrays
30        while (i < nums1.length && j < nums2.length) {
31            // Check if the current difference is not equal to x
32            if (nums2[j] - nums1[i] != x) {
33                ++cnt;  // Increment count of mismatched elements
34            } else {
35                ++j;  // Move to the next element in nums2
36            }
37
38            ++i;  // Move to the next element in nums1
39        }
40
41        // Return true if two or fewer mismatched elements
42        return cnt <= 2;
43    }
44}
45

1#include <vector>
2#include <algorithm>
3#include <limits.h>
4
5class Solution {
6public:
7    // Function to find the minimum integer to be added based on specific conditions.
8    int minimumAddedInteger(std::vector<int>& nums1, std::vector<int>& nums2) {
9        // Sort both vectors in ascending order.
10        std::sort(nums1.begin(), nums1.end());
11        std::sort(nums2.begin(), nums2.end());
12      
13        // Initialize the answer to a large value, close to INT_MAX.
14        int minAdditionalInteger = 1 << 30;
15      
16        // Lambda function to check if the difference between elements is not equal to x
17        // more than two times.
18        auto checkDifference = [&](int x) {
19            int i = 0, j = 0, count = 0;
20            // Use two-pointer technique to iterate through both vectors.
21            while (i < nums1.size() && j < nums2.size()) {
22                // If the difference doesn't equal x, increment the count.
23                if (nums2[j] - nums1[i] != x) {
24                    ++count;
25                } else {
26                    ++j; // Move to the next element in nums2 if the difference equals x.
27                }
28                ++i; // Always move forward in nums1.
29            }
30            // Check if the count of mismatches is less than or equal to 2.
31            return count <= 2;
32        };
33      
34        // Test the first three elements in nums1 and find the minimum x that satisfies the condition.
35        for (int i = 0; i < 3; ++i) {
36            int x = nums2[0] - nums1[i];
37            if (checkDifference(x)) {
38                minAdditionalInteger = std::min(minAdditionalInteger, x);
39            }
40        }
41      
42        // Return the smallest integer found.
43        return minAdditionalInteger;
44    }
45};
46

1// Function to determine the minimum integer that needs to be added to elements of nums1 to match differences with nums2
2function minimumAddedInteger(nums1: number[], nums2: number[]): number {
3    // Sort both input arrays in ascending order
4    nums1.sort((a, b) => a - b);
5    nums2.sort((a, b) => a - b);
6
7    // Helper function to check if the difference between nums2 and nums1 can be made equal to x with at most 2 changes
8    const f = (x: number): boolean => {
9        let i = 0; // Index for nums1
10        let j = 0; // Index for nums2
11        let changeCount = 0; // Counter for changes needed
12
13        // Loop through both arrays
14        while (i < nums1.length && j < nums2.length) {
15            // Check if current difference is not equal to x
16            if (nums2[j] - nums1[i] !== x) {
17                // Increase the change counter
18                changeCount++;
19            } else {
20                // Move to next element in nums2 if difference is correct
21                j++;
22            }
23            // Always move to next element in nums1
24            i++;
25        }
26        // Return true if the number of changes is at most 2
27        return changeCount <= 2;
28    };
29
30    let ans = Infinity; // Initialize answer to Infinity
31
32    // Check possible values of x by taking differences from first element of nums2 and first three of nums1
33    for (let i = 0; i < 3; ++i) {
34        const x = nums2[0] - nums1[i]; // Calculate potential x
35        // If condition f(x) is satisfied, update the minimum answer
36        if (f(x)) {
37            ans = Math.min(ans, x);
38        }
39    }
40
41    return ans; // Return the minimum value of x found
42}
43

Time and Space Complexity

The time complexity of the given code can be analyzed as follows:

Sorting nums1 and nums2 each takes O(n \log n), where n is the length of the respective array.
The for-loop runs a constant number of times (3 in this case), each time invoking the function f(x).
Inside the function f(x), there is a while loop that could potentially iterate over the length of nums1 and nums2, making its time complexity O(n).
Therefore, the overall time complexity of the solution is O(n \log n) for sorting, plus O(3n) for the loop and inner function which simplifies to O(n \log n).

The space complexity is:

Sorting typically requires O(\log n) auxiliary space due to the recursion stack in algorithms such as QuickSort or MergeSort.
The function f(x) and other operations use a constant amount of additional space.
Therefore, the overall space complexity is O(\log n).

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

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