Solution Approach

We'll apply the binary search template to find the first value where sum >= target:

Step 1: Sort and prepare prefix sums

arr.sort()
prefix_sums = list(accumulate(arr, initial=0))

Sorting enables binary search lookups. Prefix sums let us calculate the sum for any value efficiently.

Step 2: Define helper function to calculate sum

def calculate_sum(value):
    index = bisect_right(arr, value)
    return prefix_sums[index] + (n - index) * value

For a given value:

• Find how many elements are ≤ value using bisect_right
• Sum = (unchanged elements) + (count of capped elements × value)

Step 3: Apply binary search template

left, right = 0, max(arr)
first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if calculate_sum(mid) >= target:  # feasible condition
        first_true_index = mid
        right = mid - 1
    else:
        left = mid + 1

The template finds the first value where calculate_sum(value) >= target.

Step 4: Check both candidates

if first_true_index == -1:
    return max(arr)
if first_true_index == 0:
    return 0

if abs(calculate_sum(first_true_index - 1) - target) <= abs(calculate_sum(first_true_index) - target):
    return first_true_index - 1
return first_true_index

The optimal answer is either first_true_index - 1 or first_true_index. We check both and return the one with smaller difference. The <= ensures we return the smaller value in case of ties.

Time Complexity: O(n log n) for sorting + O(log M × log n) for binary search where M = max(arr).

Space Complexity: O(n) for prefix sums array.

Example Walkthrough

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

Step 1: Sort and build prefix sums

• arr = [3, 4, 9] after sorting
• prefix_sums = [0, 3, 7, 16]

Step 2: Binary search using template

• left = 0, right = 9 (max of arr)
• first_true_index = -1

Iteration 1: mid = 4

• calculate_sum(4): bisect_right([3,4,9], 4) = 2
• Sum = prefix_sums[2] + (3-2)×4 = 7 + 4 = 11
• 11 >= 10? Yes (feasible)
• first_true_index = 4, right = 3

Iteration 2: left = 0, right = 3, mid = 1

• calculate_sum(1): bisect_right([3,4,9], 1) = 0
• Sum = prefix_sums[0] + (3-0)×1 = 0 + 3 = 3
• 3 >= 10? No
• left = 2

Iteration 3: left = 2, right = 3, mid = 2

• calculate_sum(2): bisect_right([3,4,9], 2) = 0
• Sum = prefix_sums[0] + (3-0)×2 = 0 + 6 = 6
• 6 >= 10? No
• left = 3

Iteration 4: left = 3, right = 3, mid = 3

• calculate_sum(3): bisect_right([3,4,9], 3) = 1
• Sum = prefix_sums[1] + (3-1)×3 = 3 + 6 = 9
• 9 >= 10? No
• left = 4

Loop ends: left = 4 > right = 3

• first_true_index = 4 (the first value where sum >= target)

Step 3: Check both candidates

• calculate_sum(3) = 9, difference = |9 - 10| = 1
• calculate_sum(4) = 11, difference = |11 - 10| = 1
• Since differences are equal (1 <= 1) and we prefer smaller value, return 3

Final Answer: 3

Time and Space Complexity

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

Breaking down the operations:

• arr.sort(): O(n log n) for sorting the array
• Building prefix sum array: O(n)
• Binary search on value space: O(log M) iterations
• Each iteration calls calculate_sum() which uses bisect_right(): O(log n)
• Total for binary search: O(log M × log n)

Overall time complexity: O(n log n + log M × log n). Since M is typically bounded by problem constraints or O(n), this simplifies to O(n log n).

The space complexity is O(n):

• Sorting may use O(n) auxiliary space depending on the implementation
• Prefix sum array requires O(n) space
• Other variables 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: Using Wrong Template Variant

Problem: Using while left < right with right = mid instead of the template's while left <= right with right = mid - 1.

# Wrong: different template variant
while left < right:
    mid = (left + right) // 2
    if calculate_sum(mid) >= target:
        right = mid  # doesn't track the answer
    else:
        left = mid + 1

Why it's wrong: This variant doesn't track first_true_index, making it harder to check both candidates. The template explicitly tracks the first feasible value.

Correct approach:

first_true_index = -1
while left <= right:
    mid = (left + right) // 2
    if calculate_sum(mid) >= target:
        first_true_index = mid  # track it
        right = mid - 1
    else:
        left = mid + 1

Pitfall 2: Not Checking Both Candidates

Problem: After binary search, only returning first_true_index without comparing it to first_true_index - 1.

# Wrong: only returns first_true_index
return first_true_index

Why it's wrong: The optimal value might be first_true_index - 1 if it produces an equal or closer difference to the target. We need to check both values around the boundary.

Correct approach:

if abs(calculate_sum(first_true_index - 1) - target) <= abs(calculate_sum(first_true_index) - target):
    return first_true_index - 1
return first_true_index

Pitfall 3: Forgetting Tie-Breaking Rule

Problem: When two values produce the same difference, not returning the smaller value.

# Wrong: uses < instead of <=
if abs(sum_left - target) < abs(sum_right - target):
    return first_true_index - 1

Why it's wrong: The problem asks for the smallest value in case of ties. Using < instead of <= returns the larger value when differences are equal.

Correct approach: Use <= to prefer the smaller value:

if abs(calculate_sum(first_true_index - 1) - target) <= abs(calculate_sum(first_true_index) - target):
    return first_true_index - 1

Pitfall 4: Missing Edge Cases

Problem: Not handling cases where first_true_index is -1 or 0.

Why it's wrong: If all values produce sum < target, first_true_index stays -1. If even value 0 produces sum >= target, we can't check first_true_index - 1.

Correct approach:

if first_true_index == -1:
    return max(arr)  # no capping needed
if first_true_index == 0:
    return 0  # even 0 is too large