Watch 10 video solutions for Sum of Mutated Array Closest to Target, a medium level problem involving Array, Binary Search, Sorting. This walkthrough by code Explainer has 3,584 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an integer array arr and a target value target, return the integer value such that when we change all the integers larger than value in the given array to be equal to value, the sum of the array gets as close as possible (in absolute difference) to target.
In case of a tie, return the minimum such integer.
Notice that the answer is not neccesarilly a number from arr.
Example 1:
Input: arr = [4,9,3], target = 10 Output: 3 Explanation: 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 3:
Input: arr = [60864,25176,27249,21296,20204], target = 56803 Output: 11361
Constraints:
1 <= arr.length <= 1041 <= arr[i], target <= 105Problem Overview: You receive an integer array and a target sum. Choose a value v and replace every element greater than v with v. The goal is to pick the value that makes the mutated array sum as close as possible to the target.
Approach 1: Brute Force Value Simulation (Time: O(n * m), Space: O(1))
The simplest strategy tries every possible mutation value from 0 to max(arr). For each candidate value v, iterate through the array and compute the mutated sum where each element contributes min(arr[i], v). Track the value that produces the smallest absolute difference from the target. This approach works because the answer must lie within this numeric range. However, it repeatedly scans the array for every candidate value, which becomes expensive when the maximum array value is large. The method is straightforward and good for building intuition about how mutation changes the total sum, but it does not scale well for larger inputs.
Approach 2: Binary Search on Mutation Value (Time: O(n log m), Space: O(1))
A better strategy treats the mutation value as a search space and applies binary search. The possible value range is [0, max(arr)]. For a midpoint value mid, compute the mutated sum by iterating through the array and accumulating min(num, mid). If the resulting sum is smaller than the target, the mutation value is too small, so move the search right. Otherwise move left. The key observation is monotonicity: increasing the mutation value always increases the resulting sum. After binary search converges, compare the sums produced by the two closest candidate values and return the one that gives the minimal difference from the target.
You can also improve the sum calculation by first applying sorting and using prefix sums to quickly determine how many values exceed the candidate threshold. That reduces repeated scanning work, but the core idea remains the same: search the mutation value rather than enumerating every possibility.
Recommended for interviews: The binary search approach is what interviewers typically expect. The brute force method demonstrates that you understand how the mutation affects the sum, but recognizing the monotonic relationship and converting the problem into a binary search shows stronger algorithmic reasoning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Value Simulation | O(n * m) | O(1) | Useful for understanding the mutation effect or when the maximum value range is very small |
| Binary Search on Value | O(n log m) | O(1) | General optimal solution when the value range is large |
| Binary Search + Sorting + Prefix Sum | O(n log n) | O(n) | Useful when repeated sum checks need to be faster after preprocessing |