Python DSA Demos

Algorithm Notes

Summary: Koko Eating Bananas — notes not yet curated.
Time: Estimate via loops/recurrences; common classes: O(1), O(log n), O(n), O(n log n), O(n^2)
Space: Count auxiliary structures and recursion depth.
Tip: See the Big-O Guide for how to derive bounds and compare trade-offs.

Big-O Guide

Source

"""
Koko Eating Bananas

TODO: Add problem description
"""

import logging

from src.interview_workbook.leetcode._registry import register_problem
from src.interview_workbook.leetcode._runner import TestCase
from src.interview_workbook.leetcode._types import Category, Difficulty


class Solution:
    def minEatingSpeed(self, piles: list[int], h: int) -> int:
        """Find minimum eating speed for Koko to eat all bananas within h hours."""
        left, right = 1, max(piles)
        while left < right:
            k = (left + right) // 2
            hours = sum((pile + k - 1) // k for pile in piles)
            if hours <= h:
                right = k
            else:
                left = k + 1
        return left

    def minEatingSpeedOptimized(self, piles: list[int], h: int) -> int:
        """Alternative optimized version with binary search clearer bound updates."""
        import math

        low, high = 1, max(piles)
        ans = high
        while low <= high:
            mid = (low + high) // 2
            hours = sum(math.ceil(p / mid) for p in piles)
            if hours <= h:
                ans = mid
                high = mid - 1
            else:
                low = mid + 1
        return ans


logging.basicConfig(level=logging.DEBUG)

test_cases = [
    TestCase(([3, 6, 7, 11], 8), 4, "Standard example"),
    TestCase(([30, 11, 23, 4, 20], 5), 30, "Tight hours limit"),
]


def demo():
    """Run simple test cases for Koko Eating Bananas."""
    sol = Solution()
    outputs = []
    for case in test_cases:
        res = sol.minEatingSpeed(*case.input_args)
        logging.debug(
            "Test case input=%s, result=%s, expected=%s", case.input_args, res, case.expected
        )
        outputs.append(
            f"Koko Eating Bananas | Input: {case.input_args} -> Output: {res}, Expected: {case.expected}\n✓ PASS"
        )
    result_str = "\n".join(outputs)
    logging.debug("Final demo output (len=%d)", len(result_str))
    return result_str


register_problem(
    id=875,
    slug="koko_eating_bananas",
    title="Koko Eating Bananas",
    category=Category.BINARY_SEARCH,
    difficulty=Difficulty.MEDIUM,
    tags=["array", "binary_search"],
    url="https://leetcode.com/problems/koko-eating-bananas/",
    notes="",
)