3131. Find the Integer Added to Array I

Problem Description

You are given two arrays of equal length, nums1 and nums2. Each element in nums1 has been changed by an integer, represented by the variable x. After this transformation, nums1 should be equal to nums2. Two arrays are considered equal when they contain the same integers with the same frequencies. Your task is to find and return the integer x that was used to perform this transformation.

Intuition

To solve this problem, we start by understanding that both arrays must contain the same values with the same frequencies after the transformation. If each element in nums1 is increased or decreased by x, the easiest way to achieve equality is to align the smallest numbers of both arrays. This is because any displacement in the smallest value can propagate to the rest, preserving the integers' sequence and frequency when aligned.

Therefore, we can deduce that the transformation required can be calculated by computing the difference between the smallest elements of both arrays. The difference between min(nums2) and min(nums1) yields the value of x, as adding this difference to nums1 aligns its smallest element with nums2 and allows the rest of the elements to fall into place.

Solution Approach

To implement the solution, we utilize a straightforward approach that leverages the properties of arrays and simple arithmetic:

Identify the Minimum Elements: Begin by identifying the minimum values in both nums1 and nums2. This step is crucial as it establishes a reference point for alignment of the two arrays.
```
min1 = min(nums1)
min2 = min(nums2)
```
Calculate the Difference: Once the minimum elements are identified, calculate the difference between min2 and min1. This difference, x = min2 - min1, is the required value that, when added to each element of nums1, will make the resulting array equal to nums2.
```
x = min2 - min1
```
Return the Result: Finally, return x as the solution, which represents the integer transformation required to make nums1 equal to nums2.
```
return x
```

This approach is efficient since it only requires finding the minimum elements in the arrays, which is a linear operation. The overall complexity is O(n), where n is the length of the arrays.

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 a small example.

Example

Consider the arrays:

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

Step 1: Identify the Minimum Elements

First, find the minimum elements in both arrays:

Minimum of nums1: min1 = 3
Minimum of nums2: min2 = 5

Step 2: Calculate the Difference

Compute the difference between the smallest elements of nums2 and nums1 to find x:

x = min2 - min1 = 5 - 3 = 2

Step 3: Return the Result

The integer x = 2 is the transformation that, when added to each element of nums1, will make nums1 equal to nums2.

By adding 2 to each element in nums1, we get:

nums1 + x = [3+2, 5+2, 7+2, 9+2] = [5, 7, 9, 11]

This matches nums2, confirming that the calculation is correct.

Solution Implementation

1from typing import List
2
3class Solution:
4    def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
5        # Find the minimum value in the first list
6        min_value_nums1 = min(nums1)
7      
8        # Find the minimum value in the second list
9        min_value_nums2 = min(nums2)
10      
11        # Calculate and return the difference between the two minimum values
12        return min_value_nums2 - min_value_nums1
13

1import java.util.Arrays;
2
3class Solution {
4    public int addedInteger(int[] nums1, int[] nums2) {
5        // Find the minimum value in nums2 array
6        int minInNums2 = Arrays.stream(nums2).min().getAsInt();
7      
8        // Find the minimum value in nums1 array
9        int minInNums1 = Arrays.stream(nums1).min().getAsInt();
10      
11        // Return the difference between the minimum values of nums2 and nums1
12        return minInNums2 - minInNums1;
13    }
14}
15

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Define a function `addedInteger` that takes two integer vectors as arguments.
7    int addedInteger(std::vector<int>& nums1, std::vector<int>& nums2) {
8        // Find the minimum element in nums2
9        int minNum2 = *std::min_element(nums2.begin(), nums2.end());
10      
11        // Find the minimum element in nums1
12        int minNum1 = *std::min_element(nums1.begin(), nums1.end());
13      
14        // Return the difference between the minimum elements in nums2 and nums1
15        return minNum2 - minNum1;
16    }
17};
18

1// Function that calculates the difference between the smallest integers in two arrays.
2function addedInteger(nums1: number[], nums2: number[]): number {
3    // Find the smallest number in nums2 array using the spread operator with Math.min
4    const minNum2 = Math.min(...nums2);
5  
6    // Find the smallest number in nums1 array using the spread operator with Math.min
7    const minNum1 = Math.min(...nums1);
8  
9    // Return the difference between smallest number in nums2 and smallest number in nums1
10    return minNum2 - minNum1;
11}
12

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the longest array among nums1 and nums2. This is because the min function iterates through each element of the array to find the minimum value.

The space complexity is O(1), as the space required to perform the operation does not depend on the input size and only uses a constant amount of space for storing the minimum values and performing the subtraction.

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:

Question 1 out of 10

Which of the following shows the order of node visit in a Breadth-first Search?

I don’t know