Maximum Saw Height for At Least M Cut Length
Reported by candidates from Amazon's online assessment. Pattern, common pitfall, and the honest play if you blank under the timer.
Amazon reported this one in September 2026, and the input size is the whole story. Up to 100000 poles with heights up to 10^9 means you can't try every saw height and sum the wood each time. That's a billion-times-a-hundred-thousand mess. The pattern is binary search on the answer, and once you see it the code is about fifteen lines. This is the classic "Wood Cutting" shape. If you've got the OA coming in a day or two, learn the monotonic check and the boundary handling. StealthCoder sits invisibly on your screen as a safety net if your mind goes blank mid-assessment.
The problem
You have vertical wooden poles with integer heights heights. Set a saw to a non-negative integer height h; every pole taller than h contributes height - h units of wood, and shorter poles contribute nothing. Given requiredWood, return the largest saw height that collects at least that much wood. Function maxSawHeight(heights: int[], requiredWood: int) → int Examples Example 1 heights = [20,15,10,17] requiredWood = 7 return = 15 At height 15 the cuts yield 5 + 0 + 0 + 2 = 7. Raising the saw would yield too little. Example 2 heights = [4,42,40,26,46] requiredWood = 20 return = 36 Height 36 yields 6 + 4 + 10 = 20 units from the three taller poles. Example 3 heights = [5] requiredWood = 5 return = 0 The only way to collect all five units is to place the saw at ground level. Constraints 1 <= heights.length <= 100000. 1 <= heights[i] <= 10^9. 1 <= requiredWood <= min(2 * 10^9, sum(heights)).
Reported by candidates. Source: FastPrep
Pattern and pitfall
The trick: wood collected only goes down as the saw height goes up. That's monotonic, so binary search h between 0 and max(heights). For each mid, sum max(0, height - mid) across all poles. If the sum is at least requiredWood, mid works, so store it and search higher. Otherwise search lower. Total cost is O(n log maxHeight), which fits easily. Pitfalls are real. First, the lower bound must be 0, because Example 3 returns 0. Second, use a wide integer for the sum if your language overflows at 2^31, since requiredWood goes to 2 * 10^9 and sums can be far larger. Third, watch the off-by-one: you want the largest passing h, so use lo = mid + 1 on success. You can also early-exit the sum once it passes requiredWood. If you freeze on the loop invariants during the live OA, StealthCoder is the hedge that hands you the template.
Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.
You can drill Maximum Saw Height for At Least M Cut Length cold, or you can hedge it. StealthCoder runs invisibly during screen share and surfaces a working solution in under 2 seconds. The proctor sees the IDE. They don't see what's behind it. Made for the candidate who got the OA invite this morning and has 72 hours, not six months.
Get StealthCoderRelated leaked OAs
You've seen the question.
Make sure you actually pass Amazon's OA.
Amazon reuses patterns across OAs. Made for the candidate who got the OA invite this morning and has 72 hours, not six months. Works on HackerRank, CodeSignal, CoderPad, and Karat.
Maximum Saw Height for At Least M Cut Length FAQ
What's the trick in the Amazon saw height problem?+
Binary search on the answer, not on the array. Wood collected shrinks as the saw rises, so the feasibility check is monotonic. Search heights from 0 to max(heights), sum the cuts at each midpoint, and keep the largest height that still meets requiredWood.
Why does Example 3 return 0 instead of 5?+
With one pole of height 5 and requiredWood of 5, the saw must sit at ground level to collect all 5 units. Any height above 0 gives less than 5. So your search range must include 0 as a valid answer, not start at 1.
Will brute force pass the constraints?+
No. Heights go up to 10^9 and there can be 100000 poles. Trying every height and summing is far too slow. Binary search cuts the height tries to about 30, so total work is roughly 3 million operations. That's the whole reason the input sizes are set this way.
What bugs do people hit on this problem?+
Integer overflow on the wood sum, wrong boundary updates, and starting the search at 1. Use a 64-bit sum. On success, record mid and move lo to mid + 1. On failure, move hi to mid - 1. Test with the single-pole case to catch the zero answer.
How do I prepare for this in 48 hours?+
Write the binary-search-on-answer template from memory three times. Then solve two variants where the check function changes, like splitting arrays or shipping capacity. The pattern is the same each time: define a monotonic check, bound the range, and find the largest or smallest value that passes.