LeetCode 1300 - Sum of Mutated Array Closest to Target
The problem gives us an integer array arr and an integer target. We are allowed to choose a value x, then modify the arr
Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sorting
Solution
Problem Understanding
The problem gives us an integer array arr and an integer target. We are allowed to choose a value x, then modify the array so that every element larger than x becomes exactly x. Smaller elements remain unchanged.
After this mutation, we compute the sum of the modified array. Our goal is to find the integer x that makes this sum as close as possible to target.
If two different values produce the same absolute difference from the target, we must return the smaller value.
For example, if:
arr = [4,9,3]
target = 10
and we choose x = 3, then:
[4,9,3] -> [3,3,3]
sum = 9
If we choose x = 4, then:
[4,9,3] -> [4,4,3]
sum = 11
Both 9 and 11 are distance 1 away from 10, but since ties require the smaller value, the answer is 3.
An important detail is that the answer does not need to already exist in the array. We are free to choose any integer value.
The constraints are:
1 <= arr.length <= 10^41 <= arr[i], target <= 10^5
These limits tell us several things:
- The array can contain up to ten thousand elements, so quadratic solutions may become too slow.
- Array values and target values are reasonably bounded, which makes binary search over possible mutation values practical.
- Since all numbers are positive integers, the mutated sum behaves monotonically as the chosen value increases. This monotonic behavior is the key insight for the optimal solution.
Several edge cases are important:
- The target may already equal the original array sum.
- The target may be smaller than every element in the array.
- The target may be larger than the original sum, meaning no mutation is necessary.
- Multiple values may produce equally close sums, and we must correctly return the smaller one.
Approaches
Brute Force Approach
A straightforward solution is to try every possible mutation value from 0 up to the maximum element in the array.
For each candidate value:
- Create the mutated array by replacing every element larger than the candidate with the candidate itself.
- Compute the mutated sum.
- Compare the distance from the target.
- Track the value producing the smallest difference.
This works because it exhaustively checks every possible answer.
However, the time complexity becomes expensive. If the maximum array value is 10^5, and we recompute the array sum for each candidate, the complexity becomes:
O(max(arr) * n)
In the worst case:
10^5 * 10^4 = 10^9
which is too slow.
Key Insight for the Optimal Solution
The crucial observation is that the mutated sum changes monotonically as the mutation value increases.
If the chosen value increases:
- More elements retain their original values.
- Replaced values become larger.
- Therefore, the resulting sum never decreases.
This monotonic behavior means we can binary search for the best mutation value.
To efficiently compute mutated sums:
- Sort the array.
- Build a prefix sum array.
- For any candidate value
x, use binary search to find the first element greater thanx. - Elements before that index remain unchanged.
- Elements after that index contribute
xeach.
This allows each sum computation to be done efficiently.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(max(arr) * n) | O(1) | Tests every possible mutation value |
| Optimal | O(n log n + log(max(arr)) * log n) | O(n) | Uses sorting, prefix sums, and binary search |
Algorithm Walkthrough
Optimal Algorithm
- Sort the array in ascending order.
Sorting helps us quickly identify which elements will be replaced for a given mutation value. Once sorted, all elements greater than a candidate value appear consecutively at the end. 2. Build a prefix sum array.
The prefix sum array allows us to compute the sum of any prefix in constant time. If prefix[i] stores the sum of the first i elements, then the sum of unchanged elements can be retrieved efficiently.
3. Define a helper function to compute the mutated sum for a candidate value.
For a candidate value x:
- Use binary search to find the first index where
arr[index] > x. - Elements before this index remain unchanged.
- Elements from this index onward become
x.
The mutated sum becomes:
unchanged_sum + x * replaced_count
- Binary search the answer space.
The mutation value can range from 0 to max(arr).
For each midpoint:
- Compute the mutated sum.
- If the sum is smaller than the target, move right.
- Otherwise, move left.
This works because mutated sums increase monotonically with the mutation value. 5. After binary search finishes, evaluate nearby candidates.
Binary search identifies the boundary where the sum crosses the target, but the closest answer may be either side of that boundary.
Compare:
leftleft - 1
Choose the one with the smaller absolute difference. 6. Apply the tie-breaking rule.
If both values produce the same difference, return the smaller value.
Why it works
The mutated sum is a monotonic function of the chosen mutation value. Increasing the mutation value never decreases the final sum. Because of this monotonicity, binary search correctly narrows the search space toward the optimal answer.
The prefix sums ensure that each candidate evaluation is efficient, while the final comparison between adjacent candidates guarantees that the closest possible value is returned.
Python Solution
from bisect import bisect_right
from typing import List
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
arr.sort()
n = len(arr)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + arr[i]
def mutated_sum(value: int) -> int:
index = bisect_right(arr, value)
unchanged = prefix[index]
replaced_count = n - index
return unchanged + value * replaced_count
left = 0
right = arr[-1]
while left < right:
mid = (left + right) // 2
if mutated_sum(mid) < target:
left = mid + 1
else:
right = mid
sum1 = mutated_sum(left)
sum2 = mutated_sum(left - 1)
if abs(sum2 - target) <= abs(sum1 - target):
return left - 1
return left
The implementation starts by sorting the array so that all values larger than a candidate mutation value appear together at the end.
Next, a prefix sum array is constructed. The prefix sum array allows constant-time retrieval of the sum of unchanged elements.
The mutated_sum helper function computes the resulting array sum for a chosen mutation value. It uses bisect_right to find how many elements remain unchanged. Everything after that position becomes the mutation value.
The main binary search operates over possible mutation values from 0 to the maximum element in the array. Since mutated sums increase monotonically, binary search efficiently locates the transition point near the target.
Finally, both left and left - 1 are checked because the exact closest value may lie on either side of the binary search boundary. The tie-breaking rule is handled naturally by preferring the smaller value when differences are equal.
Go Solution
package main
import "sort"
func findBestValue(arr []int, target int) int {
sort.Ints(arr)
n := len(arr)
prefix := make([]int, n+1)
for i := 0; i < n; i++ {
prefix[i+1] = prefix[i] + arr[i]
}
mutatedSum := func(value int) int {
index := sort.Search(len(arr), func(i int) bool {
return arr[i] > value
})
unchanged := prefix[index]
replacedCount := n - index
return unchanged + value*replacedCount
}
left := 0
right := arr[n-1]
for left < right {
mid := (left + right) / 2
if mutatedSum(mid) < target {
left = mid + 1
} else {
right = mid
}
}
sum1 := mutatedSum(left)
sum2 := mutatedSum(left - 1)
if abs(sum2-target) <= abs(sum1-target) {
return left - 1
}
return left
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
The Go solution follows the same algorithmic structure as the Python version.
Instead of bisect_right, Go uses sort.Search to locate the first element greater than the candidate value.
Slices are used directly, and prefix sums are stored in an integer slice of length n + 1.
Integer overflow is not a concern under the given constraints because the maximum possible sum is:
10^4 * 10^5 = 10^9
which safely fits inside Go's int type on LeetCode platforms.
Worked Examples
Example 1
arr = [4,9,3]
target = 10
Step 1: Sort
arr = [3,4,9]
Step 2: Prefix sums
| Index | Prefix Sum |
|---|---|
| 0 | 0 |
| 1 | 3 |
| 2 | 7 |
| 3 | 16 |
Step 3: Binary search
| left | right | mid | mutated sum | Action |
|---|---|---|---|---|
| 0 | 9 | 4 | 11 | move left |
| 0 | 4 | 2 | 6 | move right |
| 3 | 4 | 3 | 9 | move right |
Binary search ends with:
left = 4
Now compare:
| Value | Mutated Sum | Difference |
|---|---|---|
| 3 | 9 | 1 |
| 4 | 11 | 1 |
Tie occurs, return smaller value:
answer = 3
Example 2
arr = [2,3,5]
target = 10
Original sum:
2 + 3 + 5 = 10
No mutation improves the result.
Binary search eventually selects:
answer = 5
because the original array already matches the target exactly.
Example 3
arr = [60864,25176,27249,21296,20204]
target = 56803
Step 1: Sort
[20204,21296,25176,27249,60864]
Step 2: Prefix sums
| Index | Prefix Sum |
|---|---|
| 0 | 0 |
| 1 | 20204 |
| 2 | 41500 |
| 3 | 66676 |
| 4 | 93925 |
| 5 | 154789 |
Binary search gradually narrows toward the best value.
Final comparison identifies:
11361
as the value producing the closest possible sum.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n + log(max(arr)) * log n) | Sorting dominates initially, each binary search step performs another binary search |
| Space | O(n) | Prefix sum array requires linear extra space |
The sorting step costs O(n log n).
The outer binary search runs over values from 0 to max(arr), which requires O(log(max(arr))) iterations.
Each iteration computes a mutated sum using binary search over the sorted array, costing O(log n).
The total complexity is therefore:
O(n log n + log(max(arr)) * log n)
The extra space comes from the prefix sum array.
Test Cases
from typing import List
class Solution:
def findBestValue(self, arr: List[int], target: int) -> int:
from bisect import bisect_right
arr.sort()
n = len(arr)
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + arr[i]
def mutated_sum(value: int) -> int:
index = bisect_right(arr, value)
return prefix[index] + value * (n - index)
left = 0
right = arr[-1]
while left < right:
mid = (left + right) // 2
if mutated_sum(mid) < target:
left = mid + 1
else:
right = mid
if abs(mutated_sum(left - 1) - target) <= abs(mutated_sum(left) - target):
return left - 1
return left
solution = Solution()
assert solution.findBestValue([4, 9, 3], 10) == 3 # example 1
assert solution.findBestValue([2, 3, 5], 10) == 5 # exact original sum
assert solution.findBestValue([60864, 25176, 27249, 21296, 20204], 56803) == 11361 # example 3
assert solution.findBestValue([1], 1) == 1 # single element exact match
assert solution.findBestValue([10], 5) == 5 # single element reduction
assert solution.findBestValue([1, 2, 3], 100) == 3 # target larger than original sum
assert solution.findBestValue([5, 5, 5], 10) == 3 # repeated elements
assert solution.findBestValue([100000], 1) == 1 # large value reduced heavily
assert solution.findBestValue([2, 2, 2], 1) == 0 # mutation to zero
assert solution.findBestValue([4, 4, 4], 11) == 4 # already closest
assert solution.findBestValue([1, 100, 100], 102) == 51 # tie handling
| Test | Why |
|---|---|
[4,9,3], 10 |
Verifies tie-breaking rule |
[2,3,5], 10 |
Original array already matches target |
| Large mixed values example | Tests general binary search correctness |
[1], 1 |
Smallest valid input |
[10], 5 |
Single element reduction |
[1,2,3], 100 |
Target larger than original sum |
[5,5,5], 10 |
Repeated values |
[100000], 1 |
Very large value reduction |
[2,2,2], 1 |
Mutation value becomes zero |
[4,4,4], 11 |
Closest value equals existing element |
[1,100,100], 102 |
Verifies correct tie handling |
Edge Cases
One important edge case occurs when the target is larger than the original array sum. In this situation, no mutation can increase the sum because mutations only reduce values. The optimal answer is therefore the maximum array value, which leaves the array unchanged. The implementation handles this naturally because the binary search eventually converges to the largest possible mutation value.
Another important case occurs when the target is extremely small, even smaller than the array length. Since all elements are positive, the best mutation value may become zero. Many incorrect implementations assume mutation values must be positive, but the problem allows zero. The binary search correctly includes zero in the search space.
Tie-breaking is another subtle source of bugs. Two adjacent mutation values may produce sums equally distant from the target. The problem explicitly requires returning the smaller value. The implementation handles this by checking both left and left - 1, then using <= when comparing differences so the smaller value wins ties.
A final edge case involves arrays containing many duplicate elements. Binary search boundaries can become tricky if the helper function does not correctly identify the first value greater than the mutation threshold. Using bisect_right in Python and sort.Search in Go ensures duplicates are handled correctly and all values less than or equal to the mutation threshold remain unchanged.