LeetCode Problem 3131

Difficulty: 🟢 Easy
Topics: Array

Solution

LeetCode 3131 - Find the Integer Added to Array I

Problem Understanding

The problem gives us two integer arrays, nums1 and nums2, which have the same length. We are told that every element in nums1 was modified by adding the same integer x, and after this transformation the resulting array became equal to nums2.

The word "equal" here does not mean the elements must appear in the same order. Instead, the arrays must contain the same values with the same frequencies. In other words, they represent the same multiset of integers.

Our task is to determine the integer x.

For example, if:

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

then adding 3 to every element of nums1 produces:

[5, 9, 7]

which contains exactly the same elements as nums2.

The constraints are very small:

• The array length is at most 100
• Every value is between 0 and 1000

This means performance is not a major concern, but we should still aim for the cleanest and most efficient solution possible.

An important guarantee in the problem statement is that a valid integer x always exists. That means we never need to handle impossible cases.

Several edge cases are important:

• Arrays with only one element
• Arrays containing duplicates
• Arrays where x is negative
• Arrays where x = 0
• Arrays where the order differs completely

A naive implementation that compares elements index by index without sorting could fail because the arrays are not guaranteed to have the same ordering.

Approaches

Brute Force Approach

A straightforward way to solve the problem is to try every possible value of x.

We could compute a candidate value using one pair of elements, apply it to every element in nums1, sort the transformed array, and compare it with a sorted version of nums2.

Since the constraints are tiny, this would work in practice.

The process would look like this:

1. Sort both arrays.
2. Try possible differences between elements.
3. Add the candidate difference to every element in nums1.
4. Check whether the transformed array equals nums2.

This approach is correct because it explicitly verifies whether a candidate transformation works. However, it performs unnecessary work because the problem has a much simpler property we can exploit.

Optimal Approach

The key observation is that adding the same integer x to every element preserves relative ordering.

If we sort both arrays:

sorted(nums1)
sorted(nums2)

then corresponding elements differ by exactly the same amount.

That means:

x = sorted(nums2)[0] - sorted(nums1)[0]

In fact, any corresponding pair would produce the same result.

Because the problem guarantees a valid solution exists, we only need to compute this difference once and return it.

This gives us a very clean and efficient solution.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n² log n)	O(n)	Tries candidate values and validates transformations
Optimal	O(n log n)	O(n)	Sort both arrays and compare corresponding elements

Algorithm Walkthrough

1. Sort nums1.

Sorting ensures the elements appear in ascending order, making corresponding positions meaningful. 2. Sort nums2.

Since the transformed arrays are equal as multisets, sorting both arrays aligns matching values. 3. Compute the difference between the first elements.

If every element in nums1 was increased by the same integer x, then:

sorted_nums2[i] = sorted_nums1[i] + x

Therefore:

x = sorted_nums2[0] - sorted_nums1[0]

4. Return the computed difference.

Because the problem guarantees a valid answer exists, this value is correct.

Why it works

Sorting both arrays aligns equal elements after transformation. Since every value in nums1 changes by the same amount, the difference between any corresponding pair of sorted elements must be identical. Therefore, computing the difference using even a single pair gives the correct value of x.

Python Solution

from typing import List

class Solution:
    def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort()

        return nums2[0] - nums1[0]

The implementation begins by sorting both arrays in place. Once sorted, the smallest element in nums1 corresponds to the smallest element in nums2.

Because every element differs by the same value x, subtracting the first element of nums1 from the first element of nums2 immediately gives the answer.

The solution is intentionally minimal because the mathematical property completely determines the result.

Go Solution

package main

import "sort"

func addedInteger(nums1 []int, nums2 []int) int {
	sort.Ints(nums1)
	sort.Ints(nums2)

	return nums2[0] - nums1[0]
}

The Go implementation follows the exact same logic as the Python version.

The sort.Ints function sorts the slices in ascending order. After sorting, the difference between the first elements is returned.

Go slices are mutable, so sorting modifies the original slices directly, similar to Python's in place .sort() method.

There are no integer overflow concerns because the values are very small under the given constraints.

Worked Examples

Example 1

Input:

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

After sorting:

Array	Sorted Version
nums1	[2, 4, 6]
nums2	[5, 7, 9]

Compute:

x = 5 - 2 = 3

Return:

3

Verification:

[2+3, 6+3, 4+3] = [5, 9, 7]

which matches nums2.

Example 2

Input:

nums1 = [10]
nums2 = [5]

After sorting:

Array	Sorted Version
nums1	[10]
nums2	[5]

Compute:

x = 5 - 10 = -5

Return:

-5

Example 3

Input:

nums1 = [1, 1, 1, 1]
nums2 = [1, 1, 1, 1]

After sorting:

Array	Sorted Version
nums1	[1, 1, 1, 1]
nums2	[1, 1, 1, 1]

Compute:

x = 1 - 1 = 0

Return:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) or O(log n)	Depends on the language sorting implementation

The main cost comes from sorting the arrays. After sorting, computing the answer takes constant time.

In Python, the built in sorting algorithm may use additional stack space internally. In Go, the sorting implementation also uses a small amount of auxiliary memory. No extra data structures proportional to n are required.

Test Cases

from typing import List

class Solution:
    def addedInteger(self, nums1: List[int], nums2: List[int]) -> int:
        nums1.sort()
        nums2.sort()
        return nums2[0] - nums1[0]

solution = Solution()

assert solution.addedInteger([2, 6, 4], [9, 7, 5]) == 3  # basic positive shift
assert solution.addedInteger([10], [5]) == -5  # negative shift
assert solution.addedInteger([1, 1, 1, 1], [1, 1, 1, 1]) == 0  # zero shift
assert solution.addedInteger([0, 0, 0], [5, 5, 5]) == 5  # all duplicates
assert solution.addedInteger([5, 6, 7], [2, 3, 4]) == -3  # decreasing values
assert solution.addedInteger([3, 1, 2], [8, 6, 7]) == 5  # unordered arrays
assert solution.addedInteger([1000], [0]) == -1000  # largest possible negative shift
assert solution.addedInteger([0], [1000]) == 1000  # largest possible positive shift
assert solution.addedInteger([4, 4, 4, 4], [9, 9, 9, 9]) == 5  # repeated values
assert solution.addedInteger([1, 2, 3], [1, 2, 3]) == 0  # identical arrays

Test Summary

Test	Why
[2,6,4] -> [9,7,5]	Standard positive transformation
[10] -> [5]	Single element with negative shift
[1,1,1,1] -> [1,1,1,1]	Zero transformation
[0,0,0] -> [5,5,5]	Duplicate handling
[5,6,7] -> [2,3,4]	Negative offset across multiple elements
[3,1,2] -> [8,6,7]	Order independence
[1000] -> [0]	Extreme negative difference
[0] -> [1000]	Extreme positive difference
[4,4,4,4] -> [9,9,9,9]	All repeated values
[1,2,3] -> [1,2,3]	No change required

Edge Cases

One important edge case is when the arrays contain only a single element. In this situation there is no opportunity to compare multiple values, so the algorithm must still work correctly with minimal input size. Since the solution simply subtracts the first sorted elements, it naturally handles this case without any special logic.

Another important edge case involves duplicate values. For example:

nums1 = [1,1,1]
nums2 = [4,4,4]

A buggy implementation might incorrectly assume all values are unique or rely on set comparisons, which would lose frequency information. Sorting preserves duplicates and aligns them correctly, so the implementation remains valid.

Negative transformations are also important. The integer x is allowed to be negative, meaning elements may decrease rather than increase. Some implementations mistakenly assume the result must be nonnegative. By directly computing the difference between sorted elements, the algorithm correctly supports negative values.

A final edge case is when both arrays are already equal. In that case the answer should be 0. Since the sorted first elements are identical, the subtraction naturally returns zero without requiring additional conditions.