Problem Description

You are given an integer array arr and a target value target. Your task is to find an integer value that, when used to cap all elements in the array (replacing all numbers greater than value with value itself), produces a sum that is as close as possible to the target.

Here's how the transformation works:

• Any element in arr that is greater than value gets replaced with value
• Elements less than or equal to value remain unchanged
• After this transformation, calculate the sum of the modified array

The goal is to find the value that minimizes the absolute difference between the resulting sum and the target. If multiple values produce the same minimum difference, return the smallest such value.

Important note: The answer value doesn't have to be an element from the original array arr - it can be any integer.

For example, if arr = [4, 9, 3] and target = 10:

• If we choose value = 3, the array becomes [3, 3, 3] with sum = 9
• If we choose value = 4, the array becomes [4, 4, 3] with sum = 11
• If we choose value = 5, the array becomes [4, 5, 3] with sum = 12

The best choice would be value = 3 since the sum of 9 is closest to the target of 10.

Intuition

The key insight is that as we increase the value from 0 to infinity, the sum of the modified array increases monotonically. When value is very small, all elements get capped to this small value, resulting in a small sum. As value increases, more elements remain unchanged, and the sum grows larger.

This monotonic behavior suggests we need to find the optimal value where the sum is closest to the target. Since the sum changes continuously as value changes, we can systematically check all possible values.

But what range should we check? We observe that once value becomes greater than or equal to the maximum element in the array, increasing value further won't change the sum anymore (since no elements would be capped). Therefore, we only need to check values from 0 to the maximum element in the array.

To efficiently calculate the sum for each value, we can leverage sorting and prefix sums. If we sort the array first, all elements less than or equal to value will be in a contiguous segment at the beginning. We can then:

1. Use binary search to quickly find where value would fit in the sorted array
2. Use prefix sums to get the sum of elements that remain unchanged (those ≤ value)
3. Calculate the contribution of capped elements as (count of elements > value) × value

This approach transforms what could be an O(n) calculation for each value into an O(log n) operation using binary search, making the overall solution more efficient.

Since we want the minimum value in case of ties, iterating from smallest to largest naturally gives us the correct answer when we track the best result seen so far.

Learn more about Binary Search and Sorting patterns.

Solution Approach

Let's walk through the implementation step by step:

Step 1: Sort the array

arr.sort()

We sort the array to enable binary search and make it easier to identify which elements are greater than value.

Step 2: Build prefix sum array

s = list(accumulate(arr, initial=0))

We create a prefix sum array where s[i] represents the sum of the first i elements. The initial=0 parameter ensures s[0] = 0, making s have length n+1. This allows us to quickly calculate the sum of elements in any range.

Step 3: Initialize tracking variables

ans, diff = 0, inf

• ans: stores the best value found so far
• diff: tracks the minimum absolute difference from target

Step 4: Enumerate all possible values

for value in range(max(arr) + 1):

We check every integer from 0 to the maximum element in the array. Any value beyond max(arr) would leave all elements unchanged, so there's no need to check further.

Step 5: Find the split point using binary search

i = bisect_right(arr, value)

bisect_right finds the index where value would be inserted to keep the array sorted. This gives us:

• Elements at indices [0, i) are ≤ value (remain unchanged)
• Elements at indices [i, n) are > value (get capped to value)

Step 6: Calculate the sum after transformation

d = abs(s[i] + (len(arr) - i) * value - target)

The total sum consists of:

• s[i]: sum of first i elements (those ≤ value)
• (len(arr) - i) * value: contribution from capped elements

We calculate the absolute difference d between this sum and the target.

Step 7: Update the best answer

if diff > d:
    diff = d
    ans = value

If we found a better (smaller) difference, we update both diff and ans. Since we iterate from small to large values, this naturally handles ties by keeping the smaller value.

Time Complexity: O(M × log n) where M is the maximum value in the array and n is the array length. We iterate through M values and perform a binary search for each.

Space Complexity: O(n) for storing the sorted array and prefix sum array.

Example Walkthrough

Let's trace through the algorithm with arr = [4, 9, 3] and target = 10.

Step 1: Sort the array

• arr = [3, 4, 9] after sorting

Step 2: Build prefix sum array

• s = [0, 3, 7, 16]
  • s[0] = 0 (initial value)
  • s[1] = 0 + 3 = 3
  • s[2] = 3 + 4 = 7
  • s[3] = 7 + 9 = 16

Step 3: Initialize tracking variables

• ans = 0, diff = infinity

Step 4-7: Try each possible value from 0 to max(arr) = 9

When value = 0:

• bisect_right([3, 4, 9], 0) = 0 (all elements > 0)
• Sum = s[0] + (3 - 0) × 0 = 0 + 0 = 0
• Difference = |0 - 10| = 10
• Update: ans = 0, diff = 10

When value = 1:

• bisect_right([3, 4, 9], 1) = 0 (all elements > 1)
• Sum = s[0] + (3 - 0) × 1 = 0 + 3 = 3
• Difference = |3 - 10| = 7
• Update: ans = 1, diff = 7

When value = 2:

• bisect_right([3, 4, 9], 2) = 0 (all elements > 2)
• Sum = s[0] + (3 - 0) × 2 = 0 + 6 = 6
• Difference = |6 - 10| = 4
• Update: ans = 2, diff = 4

When value = 3:

• bisect_right([3, 4, 9], 3) = 1 (element 3 ≤ 3, others > 3)
• Sum = s[1] + (3 - 1) × 3 = 3 + 6 = 9
• Difference = |9 - 10| = 1
• Update: ans = 3, diff = 1

When value = 4:

• bisect_right([3, 4, 9], 4) = 2 (elements 3,4 ≤ 4, element 9 > 4)
• Sum = s[2] + (3 - 2) × 4 = 7 + 4 = 11
• Difference = |11 - 10| = 1
• No update (diff = 1 is not better)

When value = 5:

• bisect_right([3, 4, 9], 5) = 2 (elements 3,4 ≤ 5, element 9 > 5)
• Sum = s[2] + (3 - 2) × 5 = 7 + 5 = 12
• Difference = |12 - 10| = 2
• No update (diff = 2 is worse)

Continuing through values 6-9, the differences keep getting worse.

Final Answer: 3

The algorithm correctly identifies that value = 3 produces a sum of 9, which is closest to the target of 10. When there was a tie (both value = 3 and value = 4 had difference = 1), the algorithm kept the smaller value as required.

Solution Implementation

Time and Space Complexity

The time complexity of this code is O(n × log n + m × log n) where n is the length of the array arr and m is the maximum value in the array.

Breaking down the operations:

• arr.sort(): O(n × log n) for sorting the array
• list(accumulate(arr, initial=0)): O(n) to create the prefix sum array
• The for loop runs from 0 to max(arr), which is O(m) iterations
• Inside each iteration, bisect_right(arr, value) performs binary search: O(log n)
• Other operations inside the loop are O(1)
• Total for the loop: O(m × log n)

Overall time complexity: O(n × log n + m × log n). When m (max value) is considered as O(n) in typical cases or bounded by the problem constraints, this can be simplified to O(n × log n).

The space complexity is O(n):

• The sorted array is done in-place (though in Python, arr.sort() might use O(n) auxiliary space)
• The prefix sum array s requires O(n+1) = O(n) space
• Other variables (ans, diff, value, i, d) use O(1) space

Therefore, the total space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Inefficient Search Range

Problem: The current solution iterates through all values from 0 to max(arr), which can be inefficient when the array contains very large numbers. For example, if arr = [1, 2, 100000] and target = 5, we'd unnecessarily check 100,001 values when the optimal answer is likely very small.

Solution: Use binary search on the value space instead of linear iteration:

def findBestValue(self, arr: List[int], target: int) -> int:
    arr.sort()
    n = len(arr)
    prefix_sums = list(accumulate(arr, initial=0))
  
    def calculate_sum(value):
        index = bisect_right(arr, value)
        return prefix_sums[index] + (n - index) * value
  
    # Binary search on the value space
    left, right = 0, max(arr)
  
    # Find the point where sum transitions from < target to >= target
    while left < right:
        mid = (left + right) // 2
        if calculate_sum(mid) < target:
            left = mid + 1
        else:
            right = mid
  
    # Check both left-1 and left to find the closest
    if left > 0 and abs(calculate_sum(left - 1) - target) <= abs(calculate_sum(left) - target):
        return left - 1
    return left

Pitfall 2: Mathematical Optimization Opportunity Missed

Problem: The solution doesn't leverage the fact that once we fix how many elements to cap, we can directly calculate the optimal capping value mathematically.

Solution: For each possible number of elements to cap, calculate the optimal value directly:

def findBestValue(self, arr: List[int], target: int) -> int:
    arr.sort()
    n = len(arr)
    prefix_sum = 0
  
    for i in range(n):
        # Calculate optimal value if we cap elements from index i onwards
        # optimal_value = (target - prefix_sum) / (n - i)
        optimal = (target - prefix_sum) / (n - i)
      
        # If optimal value is less than current element, we found our answer
        if optimal < arr[i]:
            # Check both floor and ceiling of optimal
            low = int(optimal)
            high = low + 1
          
            sum_low = prefix_sum + low * (n - i)
            sum_high = prefix_sum + high * (n - i)
          
            if abs(sum_low - target) <= abs(sum_high - target):
                return low
            return high
      
        prefix_sum += arr[i]
  
    # If we reach here, no capping needed
    return arr[-1]

Pitfall 3: Edge Case with Empty Array or Zero Target

Problem: The solution doesn't explicitly handle edge cases like empty arrays or when the target is 0 or negative.

Solution: Add validation at the beginning:

def findBestValue(self, arr: List[int], target: int) -> int:
    if not arr:
        return 0
  
    # If target is 0 or negative, best value is 0
    if target <= 0:
        return 0
  
    # If sum of array is already less than or equal to target
    if sum(arr) <= target:
        return max(arr)
  
    # Continue with main algorithm...

These optimizations reduce time complexity from O(M × log n) to O(n log n) or even O(n) in the mathematical approach, making the solution much more efficient for arrays with large values.