Learning Journal

3/4/2024

Koko Eating Bananas

function minEatingSpeed(piles: number[], h: number): number {
    let max = 0;

    for(let i = 0; i < piles.length; i++) {
        if(piles[i] > max)
            max = piles[i];
    }

    let min = 1;

    while(true) {
        if(max === min)
            break;
        
        const mid = Math.floor((max + min)/2);

        if(fastEnough(mid)){
            max =mid;
        }
        else {
            min = mid + 1;
        }
    }

    return max;


    function fastEnough(speed: number):boolean {
        let totalH = 0;

        for(let i = 0; i < piles.length; i++){
            totalH += Math.ceil(piles[i]/speed);
        }

        return totalH <= h;      
    }
};function minEatingSpeed(piles: number[], h: number): number {
    let max = 0;

    for(let i = 0; i < piles.length; i++) {
        if(piles[i] > max)
            max = piles[i];
    }

    let min = 1;

    while(true) {
        if(max === min)
            break;
        
        const mid = Math.floor((max + min)/2);

        if(fastEnough(mid)){
            max =mid;
        }
        else {
            min = mid + 1;
        }
    }

    return max;


    function fastEnough(speed: number):boolean {
        let totalH = 0;

        for(let i = 0; i < piles.length; i++){
            totalH += Math.ceil(piles[i]/speed);
        }

        return totalH <= h;      
    }
};

THE PROBLEM

This problem helps me understand binary search more. In binary search (or in any divide and conquer algorithm), there are three pointers, hi, lo, and mid. In each iteration, we calculate mid from hi and lo, then move hi or lo depending on the result of comparing the value at mid with the value that we are searching for. After the search ends, the value we return will depend on how we move hi or lo with regard to mid.

But how do we move hi or lo and what value do we return? Well, it's all about the invariant that we want to keep after each iteration.

Notice that right before the first iteration, the invariants are:

The element that the high pointer (max in this case) is pointing to is the speed that we know for sure is a valid speed, any speed higher than that is not relevant.
The element that the low pointer (min in this case) is pointing to is the speed that we are not sure whether or not it is a valid speed (maybe it is, maybe it is not, we are not sure).

After any iteration, we need to maintain those two invariants, which means:

If the mid pointer is pointing to the valid speed, any speed higher than that is not relevant. So, if we move max to mid, we still maintain the first invariant and make our search space smaller.
If the mid pointer is pointing to the invalid speed, it and any speed lower than that is not relevant. So, the speed that is 1 unit higher than that is the want we don't know for sure whether or not is a valid speed. So, we can move min to mid +1 to maintain the second invariant and make our search space smaller.

Because after the search ends, the invariants are still maintained, max and min are pointing to the same element. It means that this element is on both of the 2 set: the set of valid speeds and the set of speeds that we don't know for sure whether or not they are valid. So, it is the valid speed. So, we can return it.