1300. Sum of Mutated Array Closest to Target
Problem Description
Given an integer array arr
and a target value target
, the goal is to find an integer value
such that when we replace all the integers in the array that are greater than value
with value
itself, the sum of the modified array is as close as possible to the target
. In terms of absolute difference, we're looking to minimize the discrepancy between the sum of the modified array and the target
. If there are multiple value
that achieve the same minimum absolute difference, the problem asks us to return the smallest such integer. Also, it's important to note that the integer value
we are looking for does not necessarily have to be an element already present in the array arr
.
Intuition
The intuition behind the solution involves understanding that as we increase the value
used to replace elements in the array, the sum of the array will increase in a step-wise fashion until it reaches a point where increasing value
further won't change the sum since there won't be any larger elements left to replace. To find the integer value
that brings the sum closest to the target, we can follow these steps:
-
Sort the Array: Sorting
arr
allows us to efficiently work through the array to find the point where changing greater elements to a certainvalue
will affect the sum. -
Accumulate the Sum: We use a prefix sum array
s
to keep a running total, which helps us quickly calculate the sum of the array when we hypothetically replace elements greater than the currentvalue
. -
Iterate and Simulate: Iterate through potential values from
0
to themax(arr)
and for each value, we simulate what the sum would be if all the elements larger than thisvalue
were replaced by it. We use binary search (bisect_right
) to efficiently find the index where the elements start to be larger than the currentvalue
being considered. -
Compare Differences: For each
value
, we compare the absolute difference between the target and the simulated sum. We keep track of the smallest difference and the associatedvalue
. -
Return the Best Answer: Once we have considered all relevant values, we return the
ans
that corresponds to the smallest difference.
By iterating through the array and keeping track of the differences, we can find the best value
that minimizes the absolute difference to the target. The choice of binary search for finding the right index is crucial for efficiency, and sorting the array beforehand makes such an approach possible.
Learn more about Binary Search and Sorting patterns.
Solution Approach
The solution approach implements the following steps in Python code, each relying on algorithms and data structures that ensure efficient execution:
-
Sort the Array: We begin by sorting the array
arr
in increasing order. This is done witharr.sort()
, which uses an efficient sorting algorithm such as Timsort (Python's default sorting algorithm) that has a complexity of O(n log n) where n is the number of elements inarr
. -
Accumulate the Sum: We then create a prefix sum array
s
using theaccumulate
function with an initial value of 0 (initial=0
). The prefix sum array holds the cumulative sum of elements, and by includinginitial=0
, we ensure thats[0]
is0
, representing that no elements have been summed yet. This array allows us to quickly calculate the sum of all elements up to a certain point. -
Initialize Variables: Two variables are initialized:
ans
, which will hold the final answer, anddiff
, which is set to infinityinf
as a placeholder for the smallest difference found so far. -
Iteration and Value Simulation: We iterate through possible values for replacement
value
in the range from0
tomax(arr)+1
(inclusive). For each value, the code uses binary search withbisect_right
to find the indexi
where elements inarr
are greater thanvalue
. Asarr
is sorted, this tells us how many elements will be replaced withvalue
. -
Calculating the Difference: With the index
i
, the algorithm calculates the sum of the array up toi
(the sum of elements not changed) and adds(len(arr) - i) * value
(the sum if all larger elements are replaced byvalue
). This gives us the simulated sum of the array after replacements. The differenced
between the simulated sum andtarget
is computed in absolute terms. -
Track the Best Value: If the current difference
d
is smaller than the smallest difference found so fardiff
, we updatediff
tod
andans
to the current value being considered. If two values result in the samediff
, since we iterate in increasing order,ans
will already hold the smaller value. -
Return the Result: After the loop completes, the smallest
ans
is returned, representing the value that when used to replace elements inarr
results in a sum closest totarget
.
The key to this solution is the combination of sorting, prefix sums, binary search, and careful tracking of the smallest absolute difference, which altogether yields an efficient approach to solving the problem.
Here is the solution code again for reference:
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
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach. Suppose we have the following input:
- arr: [4, 9, 3]
- target: 10
Now let's walk through the solution step by step:
-
Sort the Array:
- After sorting,
arr
becomes [3, 4, 9].
- After sorting,
-
Accumulate the Sum:
- We create a prefix sum array
s
which would be[0, 3, 7, 16]
. Here,s[0]
is0
, and other elements represent the sum up to that index inarr
.
- We create a prefix sum array
-
Initialize Variables:
- We set
ans
to 0 anddiff
to infinity (inf
) initially.
- We set
-
Iteration and Value Simulation:
- We iterate
value
from0
tomax(arr) + 1
, which is 10 in this case. - For each
value
, say2
, we use binary search to find the first indexi
inarr
where the element is greater than2
. - In this case, for
value
equals2
,i
is1
becausearr[1]
is the first element greater than2
.
- We iterate
-
Calculating the Difference:
- For
value
equals2
, the sum of the array if all elements larger than2
are replaced will bes[i] + (len(arr) - i) * value
. Here, it will be0 + (3 - 1) * 2
which equals4
. - The difference
d
between this simulated sum (4
) and the target (10
) is6
. We compare this todiff
and since6
is less thaninf
, we updatediff
to6
andans
to2
.
- For
-
Track the Best Value:
- We continue this process for each
value
up to10
. For eachvalue
, we find a newd
and updateans
anddiff
accordingly if we find a smallerd
.
- We continue this process for each
-
Return the Result:
- Once we go through all possible values, let's imagine we found the best
value
to be3
which gives us the leastdiff
of1
(the sum of the array becomes3 + 3 + 3 = 9
which is closest to the target10
). - Thus,
ans
is set to3
, and that will be the result returned.
- Once we go through all possible values, let's imagine we found the best
Through the above steps, the findBestValue
function would eventually return 3
as the smallest integer we can replace the elements greater than value
with to make the sum of the array closest to the target
10
.
Solution Implementation
1from bisect import bisect_right
2from itertools import accumulate
3
4class Solution:
5 def findBestValue(self, arr, target):
6 # Sort the array to enable binary search later
7 arr.sort()
8
9 # Precompute the prefix sums to quickly calculate total sum when needed
10 prefix_sums = list(accumulate(arr, initial=0))
11
12 # Initialize the answer and the smallest difference found so far
13 best_value = 0
14 smallest_difference = float('inf') # Using 'inf' from the math module signifies infinity
15
16 # Iterate over all possible values from 0 to the maximum in the array
17 for value in range(max(arr) + 1):
18 # Find the index of the first element greater than the current value
19 index = bisect_right(arr, value)
20
21 # Calculate the total sum if all elements from index onwards were changed to 'value'
22 current_sum = prefix_sums[index] + (len(arr) - index) * value
23 # Calculate the difference between the current sum and the target sum
24 difference = abs(current_sum - target)
25
26 # If the current difference is smaller than any we have seen so far
27 if smallest_difference > difference:
28 # Update the smallest difference and the best value we've found
29 smallest_difference = difference
30 best_value = value
31
32 # Return the value that results in a sum closest to the target
33 return best_value
34
1class Solution {
2 public int findBestValue(int[] arr, int target) {
3 // Sort the input array
4 Arrays.sort(arr);
5
6 int n = arr.length; // length of the array
7 // Create a prefix sum array with an additional initial 0 for easier calculations
8 int[] prefixSum = new int[n + 1];
9 int maxValue = 0; // To keep track of the maximum value in the array
10
11 // Calculate prefix sums and find the maximum value in the array
12 for (int i = 0; i < n; ++i) {
13 prefixSum[i + 1] = prefixSum[i] + arr[i];
14 maxValue = Math.max(maxValue, arr[i]);
15 }
16
17 // Initialize answer variables
18 int bestValue = 0;
19 int minDiff = Integer.MAX_VALUE;
20
21 // Iterate over possible values, 0 to max value in the array
22 for (int candidateValue = 0; candidateValue <= maxValue; ++candidateValue) {
23 // Find the index where elements start to be greater than the candidateValue
24 int index = binarySearch(arr, candidateValue);
25 // Calculate the difference from the target for this candidateValue
26 int difference = Math.abs(prefixSum[index] + (n - index) * candidateValue - target);
27
28 // If this is a smaller difference, update the best value found so far
29 if (minDiff > difference) {
30 minDiff = difference;
31 bestValue = candidateValue;
32 }
33 }
34 return bestValue;
35 }
36
37 // Binary search to find the leftmost position where arr[i] > x
38 private int binarySearch(int[] arr, int x) {
39 int left = 0, right = arr.length;
40 while (left < right) {
41 // Middle index between left and right
42 int mid = (left + right) >> 1;
43
44 // Modify the search range based on the middle element
45 if (arr[mid] > x) {
46 right = mid; // Look in the left half
47 } else {
48 left = mid + 1; // Look in the right half
49 }
50 }
51 return left;
52 }
53}
54
1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to find the best value for the input array such that
7 // the sum of the array after replacing values greater than the best value
8 // is as close to the target as possible.
9 int findBestValue(vector<int>& arr, int target) {
10 // First, sort the array for binary search to work properly.
11 sort(arr.begin(), arr.end());
12
13 int n = arr.size(); // Store the size of the array for later use.
14
15 // Create a prefix sum array where s[i] is the sum of arr[0] to arr[i-1].
16 // It helps in calculating the sum efficiently.
17 vector<int> prefixSum(n + 1, 0);
18 int maxValue = 0; // Track the maximum value in the array.
19
20 // Calculate the prefix sum and find the maximum value in the array.
21 for (int i = 0; i < n; ++i) {
22 prefixSum[i + 1] = prefixSum[i] + arr[i];
23 maxValue = max(maxValue, arr[i]);
24 }
25
26 // Initialize variables to track the answer and the smallest difference found so far.
27 int answer = 0;
28 int smallestDiff = INT_MAX;
29
30 // Iterate through all possible values from 0 to maxValue to find the best value.
31 for (int value = 0; value <= maxValue; ++value) {
32 // Find the first element in the array that is greater than the current value
33 // and calculate the total sum if we replace all larger elements with 'value'.
34 int idx = upper_bound(arr.begin(), arr.end(), value) - arr.begin();
35 int currentSum = prefixSum[idx] + (n - idx) * value;
36
37 // Calculate the difference from the target sum.
38 int diff = abs(currentSum - target);
39
40 // If the current difference is smaller than the smallest found so far,
41 // update the answer and the smallest difference.
42 if (smallestDiff > diff) {
43 smallestDiff = diff;
44 answer = value;
45 }
46 }
47
48 // Return the best value found.
49 return answer;
50 }
51};
52
1function findBestValue(arr: number[], target: number): number {
2 // Sort the array for efficient binary search.
3 arr.sort((a, b) => a - b);
4
5 const n: number = arr.length; // Store the length of the array.
6
7 // Create a prefix sum array for efficient sum calculation.
8 const prefixSum: number[] = new Array(n + 1).fill(0);
9 let maxValue: number = 0; // To keep track of the maximum value in the array.
10
11 // Calculate the prefix sum and find the maximum value.
12 for (let i = 0; i < n; i++) {
13 prefixSum[i + 1] = prefixSum[i] + arr[i];
14 maxValue = Math.max(maxValue, arr[i]);
15 }
16
17 // Initialize variables to track the closest sum and the smallest difference.
18 let bestValue: number = 0;
19 let smallestDifference: number = Number.MAX_SAFE_INTEGER;
20
21 // Iterate over all possible values to find the one that gives us the closest sum to the target.
22 for (let value = 0; value <= maxValue; value++) {
23 // Use binary search to find the first element greater than the current value.
24 const idx: number = binarySearch(arr, value);
25 const currentSum: number = prefixSum[idx] + (n - idx) * value;
26
27 const difference: number = Math.abs(currentSum - target);
28
29 // If this difference is smaller than the smallest one found so far, record this value and difference.
30 if (difference < smallestDifference) {
31 smallestDifference = difference;
32 bestValue = value;
33 }
34 }
35
36 return bestValue;
37}
38
39// Helper function to perform binary search, finding the index of the first element greater than the value.
40function binarySearch(arr: number[], value: number): number {
41 let left = 0;
42 let right = arr.length - 1;
43 while (left <= right) {
44 const mid = left + Math.floor((right - left) / 2);
45 if (arr[mid] > value) {
46 right = mid - 1;
47 } else {
48 left = mid + 1;
49 }
50 }
51 return left;
52}
53
Time and Space Complexity
The given Python code aims to find an integer value that, when used to replace larger elements in an array, results in the sum of the array being as close as possible to a given target. The time complexity and space complexity of the code are analyzed as follows:
Time Complexity
- The
arr.sort()
operation has a time complexity ofO(n log n)
, wheren
is the length of the array. - The
list(accumulate(arr, initial=0))
operation constructs a prefix sum array inO(n)
time. - The for loop runs for a maximum of
max(arr) + 1
iterations. In the worst case, this is alsoO(n)
sincemax(arr)
is less than or equal to the sum of alln
elements. - Inside the loop, the
bisect_right
function is called, which operates inO(log n)
time. - The remaining operations within the loop (calculating the difference
d
and comparing/updatingdiff
andans
) are all constant time operations, i.e.,O(1)
.
Combining these, the overall time complexity is dominated by the sorting operation and the for loop that includes the binary search. Therefore, the time complexity is O(n log n) + O(n) * O(log n)
, which simplifies to O(n log n)
because both terms have log n
and the larger factor n log n
dominates.
Space Complexity
- The additional space used by the algorithm includes the space for the prefix sum array
s
which isO(n)
and a constant amount of space for variables likeans
,diff
,i
,d
, andvalue
.
Therefore, the overall space complexity of the code is O(n)
due to the use of the prefix sum array.
Learn more about how to find time and space complexity quickly using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!