Ad Budget Pacing - Find the Cutoff Spend Per Campaign

Problem Statement

You have a total ad budget to distribute across n campaigns. Each campaign i has requested an amount requests[i]. You want to give each campaign as much as it asked for, but if the total requested exceeds the budget, you cap every campaign at some ceiling value C:

Campaigns requesting ≤ C get their full request.
Campaigns requesting > C get exactly C.

Find the largest integer ceiling C such that the total distributed spend does not exceed budget.

Constraints

1 <= requests.length <= 10^5
1 <= requests[i] <= 10^9
1 <= budget <= 10^14
Return the largest integer C (if all requests can be fully funded, return max(requests))

Example

Input: requests = [3, 10, 5, 2], budget = 15

Output: 5

Explanation: With ceiling 5: spend = 3 + 5 + 5 + 2 = 15 ≤ 15. With ceiling 6: 3 + 6 + 5 + 2 = 16 > 15. So the largest valid ceiling is 5.

The Insight — Binary Search on the Ceiling

The total spend for a given ceiling C is a monotonically non-decreasing function of C: raise the cap, spend can only go up or stay the same. Monotonicity → binary search on C.

Algorithm:

Binary search C in range [0, max(requests)].
For a candidate C, compute total spend = sum(min(request, C)) for all campaigns.
If total ≤ budget → C is feasible, try larger. Else → try smaller.

Optimization to O(n log n): sort requests once and use prefix sums so each feasibility check is O(log n) instead of O(n) — but even the O(n log(max)) version is usually accepted.

The "aha": the answer isn't in the array — it's a threshold value you binary-search over, using a monotonic "does this cap fit the budget?" check. Same pattern as "minimize the max," reframed as "maximize the cap."

Follow-ups

Why is total-spend monotonic in the ceiling C? Why does that enable binary search?
What if C could be a non-integer (real-valued)? How does the search change?
How do prefix sums make each feasibility check O(log n)?
How does this relate to LeetCode's "sum of mutated array closest to target"?