352. Eko - Cutting Wood to Get at Least M Metres

A row of n trees with given heights is available, and a sawblade can be set to any non-negative integer height H: every tree taller than H is cut down to exactly H (shorter trees are left untouched), yielding wood equal to the sum of (height[i] - H) over trees taller than H. Given a required amount of wood M, find the maximum integer H for which at least M metres of wood are collected.

Input: The first line contains an integer n. The second line contains n space-separated integers, the tree heights. The third line contains the integer M, the required amount of wood. Output: Print a single integer - the maximum sawblade height H for which at least M metres of wood are collected.

1 <= n <= 10^5, 1 <= M <= 2*10^9, 1 <= height[i] <= 10^9

This is a foundational example of the 'maximize/minimize X such that a monotonic condition holds' binary-search-on-answer pattern - directly comparable to Painter's Partition, Book Allocation, and Aggressive Cows, all solved with the exact same underlying technique.

Set a sawblade to some height H so that every tree taller than H gets trimmed down to H - find the TALLEST H that still yields at least M metres of collected wood. Brute force: Try every possible integer height H from the tallest tree down to 0, computing the wood collected for each - this costs O(n * max height), too slow when heights can be up to 10^9. Optimised: Since the total wood collected is a MONOTONIC (non-increasing) function of H, binary searching directly on H - checking feasibility with a single O(n) pass at each candidate - narrows down to the exact answer in O(n log(max height)), far faster than checking every possible height one at a time.

Notice that the total wood collected is a monotonically non-increasing function of H: raising H can only ever reduce or keep the same the amount of wood collected. That monotonicity means binary search can be used directly on the candidate height H (from 0 up to the tallest tree), each time computing the wood yield for the midpoint with a full O(n) scan over the trees and narrowing the search range based on whether that's enough wood. This collapses the search over up to 10^9 candidate heights down to about 30 comparisons, each still doing a linear scan. Time: O(n log(maxHeight)) Space: O(1)

Sort the tree heights once and build a prefix-sum array over the sorted heights. Now, for any candidate H during the binary search, the total wood collected can be computed without scanning all n trees: binary search the sorted array for how many trees exceed H, then use the prefix sums to get their total height in O(log n) instead of O(n). This removes the linear-scan cost from every one of the ~30 binary-search evaluations, replacing it with a logarithmic lookup, so the overall cost is dominated by the one-time sort rather than by repeated full scans. Time: O(n log n) Space: O(n)

Try every possible blade height H, starting from the tallest tree's height and counting downward, and for each candidate H compute the total wood collected by summing (height[i] - H) over every tree taller than H; stop at the first (largest) H that still yields at least M metres. This directly follows the problem's definition, but trying every integer height one at a time, each requiring a full scan of all trees, means the work scales with both the number of trees and the range of possible heights, which can be up to 10^9. Time: O(n * maxHeight) Space: O(1)

1. Recognize that as H decreases, the total wood collected only increases (or stays the same) - a monotonic relationship perfect for binary search. 2. Binary search on H itself, over the range of possible heights. 3. For each candidate H, compute the total wood in one O(n) pass: sum max(height[i] - H, 0) for every tree - if it's at least M, this H is 'feasible'; try an even TALLER H; otherwise, try a shorter one.

Time: O(n log(max height)) - each of the O(log(max height)) binary search steps costs O(n) to check feasibility. Space: O(1) extra space beyond the input array.

Test n = 1, an M requiring H = 0 (cutting every tree to the ground), and n = 10^5 with heights up to 10^9 for performance.

Be ready to explain the general 'binary search on the answer' pattern this exemplifies: whenever a problem asks for the best value satisfying a MONOTONIC feasibility condition (smaller/larger always easier or harder), binary searching directly on that answer value, with an efficient feasibility check per candidate, is the way to go.