What is the time complexity of Koko Eating Bananas?

The optimal solution has a time complexity of O(nlog(m)).

What data structures are used to solve Koko Eating Bananas?

This problem uses Array, Binary Search. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Koko Eating Bananas?

Insight 1: The problem is essentially finding the minimum value of `k` within a specific range that satisfies the constraint of eating all bananas within `h` hours. This points towards using binary search. Insight 2: The eating speed `k` is bounded. The lower bound is 1 (she must eat at least one banana per hour), and the upper bound is the maximum number of bananas in any pile (if she eats faster than this, she wastes time).

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Koko Eating Bananas - LeetCode 875 Solution

Q: Which companies ask LeetCode 875. Koko Eating Bananas in interviews?

This problem is frequently asked at Accenture, Atlassian, Autodesk, Citadel, DE Shaw and 18 more companies.

Koko Eating Bananas - Complete Solution Guide

Koko Eating Bananas is LeetCode problem 875, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

Koko loves to eat bananas. There are n piles of bananas, the i th 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. R

Detailed Explanation

Koko loves to eat bananas. She has `n` piles of bananas, where the `i`-th pile has `piles[i]` bananas. The guards are returning in `h` hours. Koko needs to eat all the bananas before the guards return. Koko can choose her eating speed `k` bananas per hour. If a pile has fewer than `k` bananas, she eats them all and doesn't eat from any other pile that hour. The problem asks for the minimum `k` such that Koko can eat all the bananas within `h` hours.

Solution Approach

The solution uses binary search to find the minimum eating speed `k`. The binary search space is from 1 to the maximum number of bananas in any pile. For each potential `k`, the algorithm calculates the total hours spent eating all the piles. If the total hours spent is less than or equal to `h`, it means `k` might be too high, and we search in the lower half. Otherwise, `k` is too low, and we search in the upper half. The binary search continues until the lower and upper bounds converge, giving us the minimum `k`.

Step-by-Step Algorithm

Step 1: Find the maximum number of bananas in any pile. This will be the upper bound for the binary search.
Step 2: Initialize the lower bound of the binary search to 1 and the upper bound to the maximum number of bananas found in Step 1.
Step 3: While the lower bound is less than the upper bound, calculate the middle value `k` as the average of the lower and upper bounds (using `(low + high) // 2` to prevent overflow).
Step 4: Calculate the total hours spent eating all the piles for the current value of `k`. For each pile, the hours spent is `(pile + k - 1) // k`.
Step 5: If the total hours spent is less than or equal to `h`, it means `k` might be too high. Update the upper bound to `k`.
Step 6: Otherwise, `k` is too low. Update the lower bound to `k + 1`.
Step 7: After the while loop terminates, the lower bound will be equal to the minimum eating speed `k`.

Key Insights

Insight 1: The problem is essentially finding the minimum value of `k` within a specific range that satisfies the constraint of eating all bananas within `h` hours. This points towards using binary search.
Insight 2: The eating speed `k` is bounded. The lower bound is 1 (she must eat at least one banana per hour), and the upper bound is the maximum number of bananas in any pile (if she eats faster than this, she wastes time).
Insight 3: Calculating the time spent eating a pile can be done using `ceil(pile_size / k)`, but a common trick is to use integer division: `(pile_size + k - 1) // k`.

Complexity Analysis

Time Complexity: O(nlog(m))

Space Complexity: O(1)

Topics

This problem involves: Array, Binary Search.

Companies

Asked at: Accenture, Atlassian, Autodesk, Citadel, DE Shaw, Deutsche Bank, DoorDash, Flipkart, HashedIn, Infosys, Netflix, Nykaa, Okta, PayPal, PhonePe, Ripple, Splunk, Turing, VMware, Walmart Labs, Zepto, eBay, oyo.

Koko Eating Bananas | LeetCode 875

Medium

Array Binary Search

Time: O(nlog(m))Space: O(1)

Solution Code

Available in:

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1;
        int high = 0;
        for (int pile : piles) {
            high = Math.max(high, pile);
        }
        
        while (low < high) {
            int k = low + (high - low) / 2;
            
            int hours_spent = 0;
            for (int pile : piles) {
                hours_spent += (pile + k - 1) / k;
            }
            
            if (hours_spent <= h) {
                high = k;
            } else {
                low = k + 1;
            }
        }
        
        return low;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 875: Koko Eating Bananas - Detailed explanation and solution approaches.

Topics

Array Binary Search

Companies

AccentureAtlassianAutodeskCitadelDE ShawDeutsche BankDoorDashFlipkart

Stats

Difficulty:Medium

Languages:4

Companies:23

Problem #:875

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

7 steps

1
Step 1: Find the maximum number of bananas in any pile. This will be the upper bound for the binary search.
2
Step 2: Initialize the lower bound of the binary search to 1 and the upper bound to the maximum number of bananas found in Step 1.
3
Step 3: While the lower bound is less than the upper bound, calculate the middle value `k` as the average of the lower and upper bounds (using `(low + high) // 2` to prevent overflow).
4
Step 4: Calculate the total hours spent eating all the piles for the current value of `k`. For each pile, the hours spent is `(pile + k - 1) // k`.
5
Step 5: If the total hours spent is less than or equal to `h`, it means `k` might be too high. Update the upper bound to `k`.
6
Step 6: Otherwise, `k` is too low. Update the lower bound to `k + 1`.
7
Step 7: After the while loop terminates, the lower bound will be equal to the minimum eating speed `k`.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(nlog(m))

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

The time complexity is determined by the binary search performed on the possible values of `k` (from 1 to max(piles)). The binary search takes O(log(max(piles))) steps. Within each step, we iterate through the `piles` array, resulting in an O(n) operation. Therefore the overall time complexity is O(n*log(max(piles))). The space complexity is O(1) since no extra data structures scale with input size. We only use constant extra space for variables like `low`, `high`, `k`, and `hours_spent`.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Linear Search

Iterate through possible values of `k` starting from 1 and incrementing until a value is found that satisfies the constraint of eating all bananas within `h` hours.

Time: O(n*m), where n is the number of piles and m is the minimum eating speedSpace: O(1)

Trade-offs: This approach is much slower than binary search, especially when the maximum number of bananas in a pile is large. It is only useful if we know that the minimum eating speed `k` is likely to be small.

✨

Key Insights

1Insight 1: The problem is essentially finding the minimum value of `k` within a specific range that satisfies the constraint of eating all bananas within `h` hours. This points towards using binary search.
2Insight 2: The eating speed `k` is bounded. The lower bound is 1 (she must eat at least one banana per hour), and the upper bound is the maximum number of bananas in any pile (if she eats faster than this, she wastes time).
3Insight 3: Calculating the time spent eating a pile can be done using `ceil(pile_size / k)`, but a common trick is to use integer division: `(pile_size + k - 1) // k`.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Binary Search

Halving the search space each step. Like finding a word in a dictionary!

Edge Cases

Edge case 1: All piles have only one banana. The solution correctly handles this case because the lower bound of the binary search is 1.
Edge case 2: One very large pile and `h` is small. The binary search will eventually converge to the correct value of `k`, ensuring that the constraint on `h` is satisfied.
Edge case 3: The input `piles` is empty. The provided code does not explicitly handle this. However, the constraint `1 <= piles.length <= 10^4` ensures that the input `piles` is non-empty. If we remove this contraint, we would need to add a check like `if not piles: return 0` at the beginning of the function.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not using binary search. Using a linear search approach will be significantly slower and may result in timeouts for large input sizes.

✗Common mistake 2: Incorrectly calculating the hours spent eating a pile. Using `pile / k` without handling the remainder properly will lead to incorrect results. Integer division `(pile + k - 1) // k` or using `ceil(pile / k)` from the `math` library correctly accounts for partially eaten piles.

✗Common mistake 3: Integer overflow when calculating `k = (low + high) / 2`. Using `k = low + (high - low) / 2` avoids this issue.

✗Common mistake 4: Incorrect initialization of low and high values. Starting `low` at 0 could lead to a division by zero error when calculating `hours_spent`.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Resource allocation. Optimizing the use of resources with a given constraint, such as bandwidth allocation for network traffic or task scheduling for processors.

🏦Real-world scenario 2: Production planning. Determining the minimum production rate needed to meet a specific demand within a given timeframe, considering varying production quantities per item.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

👨‍💻 From Experience

This problem pattern appears frequently in real codebases. I've used similar logic when building production systems.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 3, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 14

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 7

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

Can binary search be applied to non-sorted arrays?

Binary search requires a monotonic property, not necessarily sorted data. It can be applied to any search space where you can determine if the answer is in the left or right half. Examples include searching rotated arrays or finding minimum in optimization problems.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Koko Eating Bananas"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether binary search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?