#1300

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Sum of Mutated Array Closest to Target

Find the integer that mutates all larger elements in an array to minimize the sum difference to a target efficiently.

Problem Statement

Given an integer array arr and a target value target, return the integer value such that replacing all elements larger than it with this value results in a sum closest to target. If multiple values achieve the same minimal difference, return the smallest one.

The answer may not exist in the original array. The challenge emphasizes binary search over the valid answer space, combining sorting with careful sum calculations to ensure efficiency and accuracy.

Examples

Example 1

Input: arr = [4,9,3], target = 10

Output: 3

When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.

Example 2

Input: arr = [2,3,5], target = 10

Output: 5

Example details omitted.

Example 3

Input: arr = [60864,25176,27249,21296,20204], target = 56803

Output: 11361

Example details omitted.

Constraints

1 <= arr.length <= 104
1 <= arr[i], target <= 105

Solution Approach

Sort and Identify Boundaries

Start by sorting the array. Recognize that the answer must lie between 0 and the maximum element of the array, allowing us to define the binary search range precisely.

Binary Search Over Potential Values

Perform a binary search over the integer range, computing the array sum after mutating all elements larger than the mid value. Adjust the search range based on whether the sum is below or above the target, always tracking the minimal difference.

Tie-Break and Return

After the search converges, check edge cases and return the smallest integer that yields the minimal absolute difference between the mutated array sum and the target. Use precomputed prefix sums for efficiency when evaluating candidate values.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log m) where n is array length and m is the max element, because each binary search step evaluates the sum in O(n) using prefix sums. Space complexity is O(n) for the sorted array and prefix sums.

What Interviewers Usually Probe

Sorting the array before search may improve efficiency and is worth mentioning.
Binary search over the answer space is the expected approach; brute force will likely exceed time limits.
Tracking minimal absolute difference and tie-breaking is critical; omitting it may indicate incomplete understanding.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the array first, which can cause incorrect prefix sums.
Not handling tie cases properly when multiple values yield the same minimal difference.
Iterating every possible value instead of using binary search, leading to time limit exceeded.

Follow-up variants

Maximize the sum without exceeding target instead of minimizing difference.
Return all possible integers yielding the minimal difference.
Allow negative numbers in the array, testing binary search correctness with extended ranges.

FAQ

What is the main strategy for Sum of Mutated Array Closest to Target?

Use binary search over the possible integer values and compute the mutated sum at each step to minimize the absolute difference to target.

Should the answer always be an element from the original array?

No, the optimal mutation value may not exist in the original array; the solution searches the full valid integer range.

How do tie situations get resolved?

If multiple values yield the same minimal difference, return the smallest integer according to problem instructions.

Why use prefix sums in this problem?

Prefix sums allow efficient calculation of the mutated array sum at each candidate value during binary search, reducing time complexity.

What is the failure mode if you don’t sort first?

Without sorting, prefix sums may be incorrect, leading to wrong sum computations and failing test cases for large arrays.

terminal

Solution

Solution 1: Sorting + Prefix Sum + Binary Search + Enumeration

We notice that the problem requires changing all values greater than `value` to `value` and then summing them up. Therefore, we can consider sorting the array `arr` first, and then calculating the prefix sum array $s$, where $s[i]$ represents the sum of the first $i$ elements of the array.

1

2

3

4

5

6

7

8

9

10

11

12

class Solution:
    def findBestValue(self, arr: List[int], target: int) -> int:
        arr.sort()
        s = list(accumulate(arr, initial=0))
        ans, diff = 0, inf
        for value in range(max(arr) + 1):
            i = bisect_right(arr, value)
            d = abs(s[i] + (len(arr) - i) * value - target)
            if diff > d:
                diff = d
                ans = value
        return ans

Continue Practicing

#1268 search suggestions system #1337 the k weakest rows in a matrix #1346 check if n and its double exist