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:

  1. Sort the Array: Sorting arr allows us to efficiently work through the array to find the point where changing greater elements to a certain value will affect the sum.

  2. 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 current value.

  3. Iterate and Simulate: Iterate through potential values from 0 to the max(arr) and for each value, we simulate what the sum would be if all the elements larger than this value were replaced by it. We use binary search (bisect_right) to efficiently find the index where the elements start to be larger than the current value being considered.

  4. 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 associated value.

  5. 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.

Solution Approach

The solution approach implements the following steps in Python code, each relying on algorithms and data structures that ensure efficient execution:

  1. Sort the Array: We begin by sorting the array arr in increasing order. This is done with arr.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 in arr.

  2. Accumulate the Sum: We then create a prefix sum array s using the accumulate function with an initial value of 0 (initial=0). The prefix sum array holds the cumulative sum of elements, and by including initial=0, we ensure that s[0] is 0, 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.

  3. Initialize Variables: Two variables are initialized: ans, which will hold the final answer, and diff, which is set to infinity inf as a placeholder for the smallest difference found so far.

  4. Iteration and Value Simulation: We iterate through possible values for replacement value in the range from 0 to max(arr)+1 (inclusive). For each value, the code uses binary search with bisect_right to find the index i where elements in arr are greater than value. As arr is sorted, this tells us how many elements will be replaced with value.

  5. Calculating the Difference: With the index i, the algorithm calculates the sum of the array up to i (the sum of elements not changed) and adds (len(arr) - i) * value (the sum if all larger elements are replaced by value). This gives us the simulated sum of the array after replacements. The difference d between the simulated sum and target is computed in absolute terms.

  6. Track the Best Value: If the current difference d is smaller than the smallest difference found so far diff, we update diff to d and ans to the current value being considered. If two values result in the same diff, since we iterate in increasing order, ans will already hold the smaller value.

  7. Return the Result: After the loop completes, the smallest ans is returned, representing the value that when used to replace elements in arr results in a sum closest to target.

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:

1class Solution:
2    def findBestValue(self, arr: List[int], target: int) -> int:
3        arr.sort()
4        s = list(accumulate(arr, initial=0))
5        ans, diff = 0, inf
6        for value in range(max(arr) + 1):
7            i = bisect_right(arr, value)
8            d = abs(s[i] + (len(arr) - i) * value - target)
9            if diff > d:
10                diff = d
11                ans = value
12        return ans
💪
Level Up Your
Algo Skills

Example 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:

  1. Sort the Array:

    • After sorting, arr becomes [3, 4, 9].
  2. Accumulate the Sum:

    • We create a prefix sum array s which would be [0, 3, 7, 16]. Here, s[0] is 0, and other elements represent the sum up to that index in arr.
  3. Initialize Variables:

    • We set ans to 0 and diff to infinity (inf) initially.
  4. Iteration and Value Simulation:

    • We iterate value from 0 to max(arr) + 1, which is 10 in this case.
    • For each value, say 2, we use binary search to find the first index i in arr where the element is greater than 2.
    • In this case, for value equals 2, i is 1 because arr[1] is the first element greater than 2.
  5. Calculating the Difference:

    • For value equals 2, the sum of the array if all elements larger than 2 are replaced will be s[i] + (len(arr) - i) * value. Here, it will be 0 + (3 - 1) * 2 which equals 4.
    • The difference d between this simulated sum (4) and the target (10) is 6. We compare this to diff and since 6 is less than inf, we update diff to 6 and ans to 2.
  6. Track the Best Value:

    • We continue this process for each value up to 10. For each value, we find a new d and update ans and diff accordingly if we find a smaller d.
  7. Return the Result:

    • Once we go through all possible values, let's imagine we found the best value to be 3 which gives us the least diff of 1 (the sum of the array becomes 3 + 3 + 3 = 9 which is closest to the target 10).
    • Thus, ans is set to 3, and that will be the result returned.

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.

Python Solution

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

Java Solution

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

C++ Solution

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

Typescript Solution

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 of O(n log n), where n is the length of the array.
  • The list(accumulate(arr, initial=0)) operation constructs a prefix sum array in O(n) time.
  • The for loop runs for a maximum of max(arr) + 1 iterations. In the worst case, this is also O(n) since max(arr) is less than or equal to the sum of all n elements.
  • Inside the loop, the bisect_right function is called, which operates in O(log n) time.
  • The remaining operations within the loop (calculating the difference d and comparing/updating diff and ans) 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 is O(n) and a constant amount of space for variables like ans, diff, i, d, and value.

Therefore, the overall space complexity of the code is O(n) due to the use of the prefix sum array.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫