#115

Cutting Wood

medium

arraybinary-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

Input: heights = [2,6,3,8], k = 7

Output: 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.

Constraints

1 <= heights.length <= 10^4
0 <= heights[i] <= 10^9
1 <= k <= sum of all heights

Intuition

The direct approach tries every possible blade height from the tallest tree downward, summing the wood each height yields, and returns the first (highest) height that reaches k.

function cutWood(heights, k) {
  const max = Math.max(...heights);
  // Try blade heights from tallest down; the first that yields >= k is the answer.
  for (let h = max; h >= 0; h--) {
    let wood = 0;
    for (const height of heights) wood += Math.max(0, height - h); // wood above the blade
    if (wood >= k) return h;
  }
  return 0;
}

Brute force — try every height from the tallest down: O(M·n), M = tallest tree.

This is O(M·n) — and when trees are billions tall, M is huge. The trees aren't sorted, so what is there to binary-search? Can we do better?

The trick is to binary-search the answer, not the input. The wood collected is monotonic in the blade height: raise the blade and you collect strictly less (never more). So the candidate heights split cleanly into a feasible low range (wood >= k) and an infeasible high range, with one boundary between them — exactly the monotonic-predicate setup. Search heights in [0, max]: for a candidate mid, sum max(0, h − mid) over all trees in O(n); if that's >= k, the blade can go at least this high, so record it and search higher; otherwise search lower.

That replaces the M outer steps with log M, giving O(n log M).

Walking it through:

heights = [2, 6, 3, 8], k = 7 (searching blade height in [0, 8])

lo↓

mid↓

hi↓

H = 4 → wood = 2 + 0 + 4 = 6 < 7 → hi = 3

The lane is the candidate heights 0..8. At H = 4 the wood is (6−4)+(8−4) = 6 < 7 — infeasible, so go lower.

lo↓

mid↓

hi↓

H = 1 → wood = 1 + 5 + 2 + 7 = 15 >= 7 → best = 1, lo = 2

Now [0, 3], H = 1 yields 15 ≥ 7 — feasible. Record 1 as the best so far and search higher.

lo↓mid↓

hi↓

H = 2 → wood = 0 + 4 + 1 + 6 = 11 >= 7 → best = 2, lo = 3

H = 2 yields 11 ≥ 7 — still feasible. Update best to 2 and keep climbing.

lo↓mid↓hi↓

H = 3 → wood = 0 + 3 + 0 + 5 = 8 >= 7 → best = 3, lo = 4 > hi → stop

H = 3 yields 8 ≥ 7 — feasible, best = 3. lo passes hi, so 3 is the highest blade that still collects 7.

Optimization

Binary search on the blade height

The wood collected is monotonic in the blade height H: raise the blade and you can only collect less (or equal) wood. So the heights split cleanly into a feasible low range (enough wood) and an infeasible high range, and we binary-search for the boundary — the largest H that still yields at least k.

Search H in [0, max(heights)]. For a candidate mid, sum max(0, h - mid) over every tree: if that total is >= k the blade can go at least this high, so record it and search higher; otherwise search lower.

O(n log M) time, where M is the tallest tree, and O(1) space.

function cutWood(heights, k) {
  const woodAt = (h) => {
    let total = 0;
    for (const height of heights) total += Math.max(0, height - h);
    return total;
  };
  let lo = 0;
  let hi = Math.max(...heights);
  let best = 0;
  while (lo <= hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (woodAt(mid) >= k) {
      best = mid;
      lo = mid + 1;
    } else {
      hi = mid - 1;
    }
  }
  return best;
}

Complexity analysis

Time complexity: O(n log M). Here's why:

The blade height is binary-searched over [0, M] where M is the tallest tree — about log₂ M steps.
Each step sums the wood over all n trees in O(n) to test feasibility.

So the total is n × log M = O(n log M), versus O(n·M) for trying every height.

Space complexity: O(1). Here's why:

The search keeps only the height bounds and a running wood sum; no extra structure is allocated.

Nothing scales with n or M beyond the input itself — overall O(1).

Test cases

Beyond the example above, these are worth thinking through before you submit.

Input	Expected output	Description
heights = [7], k = 3	4	Single tree — cutting at height 4 yields exactly 3 units.
heights = [4,4,4], k = 12	0	Need all the wood — only cutting to the ground reaches k.
heights = [10,10,10], k = 15	5	Three equal trees — height 5 gives 5+5+5 = 15.
heights = [1,2,3,4,5], k = 9	1	Uneven trees — at height 1 the wood is 0+1+2+3+4 = 10 ≥ 9; at 2 it drops to 6.
heights = [2,6,3,8], k = 15	1	Same trees as the example, larger k — forces a lower blade (height 1).
heights = [50], k = 10	40	One tall tree — height 40 yields exactly 10 units.

Try it yourself

Write your solution against the real judge before checking the reference.

Open in editor