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.
The brute force approach involves iterating over all possible values from 1 to the maximum element in the array. For each value, replace larger numbers in the array and calculate the sum of the array. Track and update the closest sum to the target.
This solution iterates over a range of possible values and adjusts the array values to calculate the sum. The closest value is determined by minimizing the absolute difference between the calculated sum and the target.
Time Complexity: O(n * maxValue), Space Complexity: O(1)
Start by sorting the array and using binary search to find the smallest value where adjusting elements results in the sum being as close as possible to the target. This is more efficient than the brute force approach.
The C solution uses binary search to efficiently determine the value that minimizes the sum difference from the target by dynamically reducing the search space.
Time Complexity: O(nlogn), Space Complexity: O(1)
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.
Next, we can enumerate all value values from smallest to largest. For each value, we can use binary search to find the index i of the first element in the array that is greater than value. At this point, the number of elements in the array greater than value is n - i, so the number of elements in the array less than or equal to value is i. The sum of the elements in the array less than or equal to value is s[i], and the sum of the elements in the array greater than value is (n - i) times value. Therefore, the sum of all elements in the array is s[i] + (n - i) times value. If the absolute difference between s[i] + (n - i) times value and target is less than the current minimum difference diff, update diff and ans.
After enumerating all value values, we can get the final answer ans.
Time complexity O(n times log n), space complexity O(n). Where n is the length of the array arr.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * maxValue), Space Complexity: O(1) |
| Binary Search Approach | Time Complexity: O(nlogn), Space Complexity: O(1) |
| Sorting + Prefix Sum + Binary Search + Enumeration | — |
| 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 |
1300. Sum of Mutated Array Closest to Target | LEETCODE BIWEEKLY 16 | BINARY SEARCH • code Explainer • 3,584 views views
Watch 9 more video solutions →Practice Sum of Mutated Array Closest to Target with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor