Skip to main content
Talentd

Sum of Mutated Array Closest to Target - Solution & Explanation

MediumArrayBinary SearchSorting19 min readAsked at: Google, Bloomberg
Practice this problem

Problem Statement

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 <= 104
  • 1 <= arr[i], target <= 105

Approach Overview

Problem 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 1: Brute Force Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * maxValue), Space Complexity: O(1)

Try this approach in the editor →

Approach 2: Binary Search Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(nlogn), Space Complexity: O(1)

Try this approach in the editor →

Approach 3: 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.

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.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Value SimulationO(n * m)O(1)Useful for understanding the mutation effect or when the maximum value range is very small
Binary Search on ValueO(n log m)O(1)General optimal solution when the value range is large
Binary Search + Sorting + Prefix SumO(n log n)O(n)Useful when repeated sum checks need to be faster after preprocessing

Video Solution

1300. Sum of Mutated Array Closest to Target | LEETCODE BIWEEKLY 16 | BINARY SEARCH • code Explainer • 3,657 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Sum of Mutated Array Closest to Target easy or hard?
This problem is classified as Medium. The challenge is recognizing that the mutation value creates a monotonic relationship between the chosen value and the resulting array sum. Once that observation is made, binary search becomes a natural solution.
Sum of Mutated Array Closest to Target Python/Java solution
Implement binary search on the value range from 0 to max(arr). For each midpoint, compute the mutated sum using min(num, mid) for every element. Compare the result with the target and adjust the search boundaries until the closest value is found. The same logic works in Python, Java, C++, and other languages.
How to solve Sum of Mutated Array Closest to Target in O(n)?
A strict O(n) solution is generally not achievable because the correct mutation value must be searched within a numeric range. Binary search over that range is the standard technique, resulting in O(n log m) complexity. Some optimizations using sorting and prefix sums reduce repeated work but still involve logarithmic search.
What is the best approach for Sum of Mutated Array Closest to Target?
Binary search on the mutation value is the most efficient approach. The possible value range is from 0 to the maximum element in the array, and the resulting array sum increases monotonically as the value increases. This property allows binary search to find the value that produces a sum closest to the target in O(n log m) time.
Is Sum of Mutated Array Closest to Target asked at Google/Amazon/Meta?
This problem follows a pattern commonly used in interviews at companies like Google and Amazon: binary search on the answer. Variants of the problem appear in coding interviews where you must search a numeric range and evaluate a condition with each guess.
What data structure is used in Sum of Mutated Array Closest to Target?
The primary data structure is a simple array. The algorithm relies on binary search over a value range and repeatedly iterates through the array to compute the mutated sum. Some optimized solutions also sort the array and use prefix sums for faster calculations.
What is the time complexity of Sum of Mutated Array Closest to Target?
The optimal solution runs in O(n log m) time, where n is the array length and m is the maximum value in the array. Each binary search step computes the mutated sum by iterating through the array once. Space complexity remains O(1) since only a few variables are used.

Ready to solve this problem?

Practice Sum of Mutated Array Closest to Target with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays