Day 1(long after day 0 )

Hey fellow devs! 👋
I dipped after bragging about becoming a 10x engineer and making a public announcement of how I will be consistent(embarrassing!!). Well I am back and ready to give this another hand. The roadmap for the last post was created with the help of my mentor, Senpai chatGPT. From this post onwards, I have decided I will freestyle the content while trying to stick to Senpai's advice. I got laid off too (out of the blue), So I am struggling to decide whether I should practice DSA and system Design or focus on building fundamentals( Any advice is welcome).

I built a CRUD API server in the mean time as part of a company interview assessment. And learnt some DSA topics solved some leetcode questions. Today to break the long winter of my disappearance I will warm-up with solving a leet-code problem.

Leetcode 875. Koko Eating Bananas

Problem statement

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:
Input: piles = [3,6,7,11], h = 8
Output: 4

Example 2:
Input: piles = [30,11,23,4,20], h = 5
Output: 30

Example 3:
Input: piles = [30,11,23,4,20], h = 6
Output: 23

Constraints:

1 <= piles.length <= 10^4
piles.length <= h <= 10^9
1 <= piles[i] <= 10^9

Thought process
So what is upper limit of rate k at which koko can eat bananas? it will be the max of array(max of pile) if she ate at that rate she can always finish before h hours(because piles.length<=h). But koko would love to eat as slow as possible which is 1 banana per hour. So our desired k lies within the range (1,max(piles)). How to calculate how much time it will take koko to finish eating all the piles: Iterate through each pile, divide by k and round to the next integer if not completely divisible.

def timeRequired(m):
 t=0
 for i in piles:
    t+=math.ceil(i/k)
 return t

this should be calculated for each k in range(1,max(piles)) then the time complexity become O(n*maxK)

maxK=max(piles)
for k in range(1,maxK):
 t=timeRequired(k)
 if t==h:
   return k
 if t>h:
   return k-1

Optimization

Since we're searching for the smallest k in the range [1, max(piles)] such that Koko finishes eating all bananas within h hours, and the total time needed decreases as k increases, we can use binary search.

We define:

left = 1: slowest possible speed

right = max(piles): fastest needed (eat whole pile in one hour)

At each step, we:

**1. Pick mid = (left + right) // 2 as our current candidate eating speed.

1. Calculate time t = sum(ceil(pile / mid) for pile in piles).
2. If time t<= h, it means mid is fast enough, but we want the minimum such speed → try smaller → right = mid.
3. If total time t > h, it means mid is too slow → try faster → left = mid + 1.

We repeat this until left == right. At that point, left holds the minimum eating speed k that allows Koko to finish in time.**

The improved time complexity is O(n*log(maxK))

l, r := 1, maxK
for l < r {
    m := (l + r) / 2
    if timeRequired(m) <= h {
        r = m
    } else {
        l = m + 1
    }
}
return l