Sum of Mutated Array Closest to Target: Binary Search on Answer

Given an integer array arr and a target value target, you need to find an integer value such that when you replace every element in arr larger than value with value, the sum of the mutated array is as close to target as possible. If there is a tie, return the smaller value.

This is LeetCode 1300: Sum of Mutated Array Closest to Target, and it is a clean application of binary search on the answer. Instead of searching through an array for a target element, you are searching through all possible cap values to find the one that gets the mutated sum closest to the target.

Why this problem matters

This problem teaches you to think about binary search beyond sorted arrays. The key realization is that the cap value controls the mutated sum, and that sum is monotonically non-decreasing as the cap increases. When you see a monotonic relationship between a parameter and an outcome, binary search is the right tool.

It also reinforces a pattern that appears across many medium and hard problems: binary search on the answer space. Problems like Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum all share this structure. Once you internalize the template, you can solve any of them by writing the right feasibility check.

Finally, this problem adds a twist compared to the classic "find the minimum valid value" template. Here you are not looking for the first feasible answer. You are looking for the answer that minimizes a distance function. That means you need to check both the value just below the target sum and the value just above it, then pick the closer one.

The key insight

Sort the array first. As you increase the cap value from 0 to max(arr), the mutated sum increases monotonically. At cap = 0, the sum is 0. At cap = max(arr), the sum is the original array sum. Somewhere in between, the sum crosses the target.

Binary search finds this crossing point efficiently. Once you know the cap value where the sum transitions from below the target to at or above the target, you compare the two neighbors (the cap just below and the cap at or above) and return whichever produces a sum closer to the target.

The sum calculation for a given cap value is O(n): for each element, take min(element, cap) and add it up. Sorting lets you optimize this further with prefix sums, but the simple min-based approach is clear enough and passes within the time limit.

The solution

from bisect import bisect_left

def find_best_value(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(cap: int) -> int:
        idx = bisect_left(arr, cap)
        return prefix[idx] + cap * (n - idx)

    lo, hi = 0, max(arr)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if mutated_sum(mid) >= target:
            hi = mid
        else:
            lo = mid + 1

    if lo == 0:
        return lo
    if abs(mutated_sum(lo) - target) < abs(mutated_sum(lo - 1) - target):
        return lo
    return lo - 1

The binary search finds the smallest cap value whose mutated sum is at least the target. Then we compare that cap with the cap one below it. Whichever produces a sum closer to the target wins. If they tie, the smaller cap (lo - 1) is returned because Python's < in the comparison naturally favors it.

Visual walkthrough

The binary search narrows in on the cap value where the mutated sum crosses the target. Once you find that crossing point, the answer is either the cap at the crossing or the cap one below it. You compare both sums to the target and pick the closer one.

Complexity analysis

Time: Sorting takes O(n log n). Building the prefix sum takes O(n). The binary search runs O(log max) iterations, and each iteration uses a binary search on the sorted array in O(log n) time, giving O(log(max) * log(n)). The dominant term is O(n log n) from sorting.

Space: The prefix sum array takes O(n). The sorted array is done in-place or takes O(n) depending on the implementation.

The building blocks

1. Binary search on the answer

The core idea is that you are not searching an array for a target. You are searching a range of candidate answers (cap values from 0 to max(arr)) for the optimal one. The mutated sum is monotonically non-decreasing in the cap value, so binary search works.

lo, hi = 0, max(arr)
while lo < hi:
    mid = lo + (hi - lo) // 2
    if mutated_sum(mid) >= target:
        hi = mid
    else:
        lo = mid + 1

2. Prefix sum for efficient range queries

After sorting, you can compute the mutated sum without looping through the entire array each time. Use a prefix sum array and bisect_left to find where the cap value falls in the sorted array. Everything to the left of that index stays unchanged (use the prefix sum), and everything to the right gets replaced by the cap.

from bisect import bisect_left

def mutated_sum(cap):
    idx = bisect_left(arr, cap)
    return prefix[idx] + cap * (n - idx)

Edge cases

• All elements equal: if arr = [5, 5, 5] and target = 15, the answer is 5 (no capping needed). If target = 9, the answer is 3 (cap all to 3, sum = 9).
• Target is zero: the answer is 0, because capping everything to 0 gives sum 0.
• Target is larger than the array sum: the answer is max(arr), because even with no capping the sum cannot reach the target.
• Single element array: arr = [10], target = 7. The answer is 7, because min(10, 7) = 7.
• Cap value between array elements: when the optimal cap is not an existing array element, the binary search still finds it because we search the entire integer range [0, max(arr)].

From understanding to recall

The logic here combines two patterns: binary search on the answer and prefix sums for efficient sum computation. You understand both individually. But in an interview, you need to combine them smoothly and handle the edge case of comparing two neighboring cap values.

The details that trip people up: remembering to check both lo and lo - 1 at the end, getting the bisect_left usage right, and building the prefix sum with the right indexing. These are small things, but under time pressure they matter.

Spaced repetition makes these details automatic. You write the solution from scratch today, then again in two days, then in a week. After a few rounds, the binary search template and the prefix sum trick are muscle memory. You do not need to think about off-by-one errors. You just write the code.

Related posts

• Binary Search - The foundational binary search pattern that this problem builds on
• Koko Eating Bananas - Another classic binary search on answer problem with a similar template
• Capacity to Ship Packages - Same binary search on answer structure with a different feasibility check

CodeBricks breaks Sum of Mutated Array Closest to Target into its binary search and prefix sum building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a binary search on answer problem shows up in your interview, you do not hesitate. You just write it.