Binary Search in Forest for Wood Collection | Coding Interview | Searching

This is an easy category problem, and it has been asked by Goldmann Sachs.

For a better grasp of the problem, after reading each section, try to code that approach. If you get stuck 😉, you can always look at the commented code I have provided for your reference.

This problem is part of the 30 Days Preparation Plan.

Table of Contents

1. Description
2. Brute Force Solution
3. Code
4. Time & Space Complexity
5. Efficient Solution
6. Code
7. Time & Space Complexity

If you are new to binary search, read this article first.

Description

You are given a list of positive numbers, where each number represents the height of a tree in a forest, and a positive number, K.

You have to find the height H at which every tree in the forest should be cut to collect K amount of woods.

Example 1:
Input:  [7 4 9 2 1 8], K = 3
Output: 7
Explanation: If you cut the tree at the height of 7, you will get 0 from the first, 0 from the second, 2 units from the 3rd tree (9…