noodleProblems/
Cutting Wood
#115

Cutting Wood

AlgorithmmediumArrayBinary Search

You are given an array heights representing the heights of a row of trees, and an integer k — the total length of wood you need to collect.

A sawmill sets its blade at some integer height H. Every tree taller than H is cut down to height H, and the part above the blade is collected as wood: a tree of height h yields max(0, h - H) units, and trees at or below H are left untouched.

Return the **maximum** integer blade height H such that the total wood collected is **at least** k. It is guaranteed that collecting k units is always possible (i.e. cutting every tree to the ground yields at least k).

Example cases

  • basic
    in heights = [2,6,3,8], k = 7
    out 3
    At H = 3 the wood is 3 + 5 = 8 ≥ 7. At H = 4 it is 2 + 4 = 6 < 7, so 3 is the highest blade that works.
  • taller trees
    in heights = [4,42,40,26,46], k = 20
    out 36
    At H = 36 the wood is 6 + 4 + 10 = 20 ≥ 20; at H = 37 it is 5 + 3 + 9 = 17 < 20.
  • single tree
    in heights = [10], k = 4
    out 6
    One tree of height 10; cutting at H = 6 yields 4 units, exactly k.

Constraints

  • 1 <= heights.length <= 10^4
  • 0 <= heights[i] <= 10^9
  • 1 <= k <= sum of all heights
Saved
heights =
[2,6,3,8]
k =
7