Scale Engineer

Find the Integer Added to Array I

Easy
#2781Time: O(N^2), where N is the length of the arrays. The outer loop runs N times. The `check` function inside the loop takes O(N) time (O(N) to build the map and O(N) to check against it). This results in a total complexity of N * O(N) = O(N^2).Space: O(N), where N is the length of the arrays. This space is used to store the frequency map during the verification step.1 company
Data structures
Array
Companies
Mitsogo

Prompt

You are given two arrays of equal length, nums1 and nums2.

Each element in nums1 has 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 integer x.

 

Example 1:

Input: nums1 = [2,6,4], nums2 = [9,7,5]

Output: 3

Explanation:

The integer added to each element of nums1 is 3.

Example 2:

Input: nums1 = [10], nums2 = [5]

Output: -5

Explanation:

The integer added to each element of nums1 is -5.

Example 3:

Input: nums1 = [1,1,1,1], nums2 = [1,1,1,1]

Output: 0

Explanation:

The integer added to each element of nums1 is 0.

 

Constraints:

  • 1 <= nums1.length == nums2.length <= 100
  • 0 <= nums1[i], nums2[i] <= 1000
  • The test cases are generated in a way that there is an integer x such that nums1 can become equal to nums2 by adding x to each element of nums1.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves a brute-force search for the integer x. It works by picking an element from nums1 (e.g., nums1[0]) and assuming it corresponds to some element in nums2. This assumption gives a candidate value for x. The algorithm then verifies if adding this candidate x to all elements in nums1 results in an array that is a permutation of nums2.

Algorithm

  1. Iterate through each element n2 in nums2.
  2. For each n2, hypothesize that it corresponds to nums1[0]. Calculate a candidate difference x = n2 - nums1[0].
  3. Verify if this candidate x is the correct integer. To do this: a. Create a frequency map of the elements in nums2. b. Iterate through nums1. For each element n1, calculate the transformed value n1 + x. c. Check if this transformed value exists in the frequency map and decrement its count. d. If at any point a transformed value is not in the map or its count is zero, this candidate x is incorrect. Move to the next n2.
  4. If the verification loop completes successfully for all elements of nums1, the candidate x is the correct answer. Return x.
  5. Since a solution is guaranteed to exist, this process will find the answer.

Walkthrough

The algorithm systematically tests every possible value for x that could arise from pairing nums1[0] with each element of nums2. For each potential x, it performs a full verification. The verification step involves checking if the multiset {nums1[0]+x, nums1[1]+x, ...} is identical to the multiset of nums2. A common way to check for multiset equality is by using frequency maps (or hash maps). We build a frequency map for nums2, then iterate through the transformed nums1 elements, decrementing their counts in the map. If all elements match and the map becomes empty of positive counts, the x is valid.

import java.util.HashMap;import java.util.Map; class Solution {    public int addedInteger(int[] nums1, int[] nums2) {        // This is a brute-force approach for demonstration.        // It's less efficient than other methods.        for (int n2 : nums2) {            int potentialX = n2 - nums1[0];            if (check(nums1, nums2, potentialX)) {                return potentialX;            }        }        return -1; // Should not be reached based on problem constraints    }     private boolean check(int[] nums1, int[] nums2, int x) {        Map<Integer, Integer> freq = new HashMap<>();        for (int num : nums2) {            freq.put(num, freq.getOrDefault(num, 0) + 1);        }         for (int num : nums1) {            int target = num + x;            if (!freq.containsKey(target) || freq.get(target) == 0) {                return false;            }            freq.put(target, freq.get(target) - 1);        }        return true;    }}

Complexity

Time

O(N^2), where N is the length of the arrays. The outer loop runs N times. The `check` function inside the loop takes O(N) time (O(N) to build the map and O(N) to check against it). This results in a total complexity of N * O(N) = O(N^2).

Space

O(N), where N is the length of the arrays. This space is used to store the frequency map during the verification step.

Trade-offs

Pros

  • Conceptually simple to understand as it directly models the problem of trying possibilities and verifying them.

Cons

  • Highly inefficient compared to other solutions, with a quadratic time complexity.

  • Performs a lot of redundant work by re-checking permutations for different candidate values of x.

Solutions

class Solution {public  int addedInteger(int[] nums1, int[] nums2) {    return Arrays.stream(nums2).min().getAsInt() -           Arrays.stream(nums1).min().getAsInt();  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem