Koko Eating Bananas Leetcode Solution

Difficulty Level Medium
Frequently asked in Facebook
algorithms Binary Search coding Interview interviewprep LeetCode LeetCodeSolutionsViews 7744

Problem statement

In the problem ” Koko Eating Bananas” we are given an array of size n which contains the number of bananas in each pile. In one hour Koko can eat at most K bananas. If the pile contains less than K bananas in that case if Koko finishes all bananas of that pile then she cannot start eating bananas from another pile in the same hour.

Koko wants to eat all bananas within H hours. We are supposed to find the minimum value of K.

Example

piles = [30,11,23,4,20], H = 6
23

Explanation: 

leetcode solution to koko eating bananas

Koko will eat bananas in this way to eat all bananas in 6 hours:

First hour: 23

Second hour: 7

Third hour: 11

Fourth hour: 23

Fifth hour: 4

Sixth hour: 20

Approach for Koko Eating Bananas Leetcode Solution

The first and the most important thing to solve this problem is to bring out observations. Here are a few observations for our search interval:

  1. Koko must eat at least one banana per hour. So this is the minimum value of K. let’s name it as Start
  2. We can limit the maximum number of bananas Koko can eat in one hour to the maximum number of bananas in a pile out of all the piles. So this is the maximum value of K. let’s name it as End.

Now we have our search interval. Suppose the size of the interval is Length and the number of piles is n.  The naive approach could be to check for each value in the interval. if for that value of K Koko can eat all bananas in H hour successfully then pick the minimum of them. The time complexity for the naive approach will be Length*n in worst case.

We can improve the time complexity by using Binary Search in place of Linear Search.

The time complexity using the Binary Search approach will be log(Length)*n.

Implementation

C++ code for Koko Eating Bananas

#include <bits/stdc++.h>
using namespace std; 
       int minEatingSpeed(vector<int>& pile, int hour) {
        int left = 1, right = *max_element(pile.begin(),pile.end());;
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : pile) total += (p + mid - 1) / mid;
            if (total > hour) left = mid + 1; else right = mid;
        }
        return left;
    }
int main() 
{ 
 vector<int> arr = {30,11,23,4,20}; 
 int H=6;                               
 cout<<minEatingSpeed(arr,H)<<endl;
 return 0;
}
23

Java code for Koko Eating Bananas

import java.util.Arrays; 
public class Tutorialcup {
    public static int minEatingSpeed(int[] piles, int H) {
        int left = 1, right =Arrays.stream(piles).max().getAsInt();
        while (left < right) {
            int mid = (left + right) / 2, total = 0;
            for (int p : piles) total += (p + mid - 1) / mid;
            if (total > H) left = mid + 1; else right = mid;
        }
        return left;
    }
  public static void main(String[] args) {
    int [] arr = {30,11,23,4,20}; 
     int H=6; 
    int ans= minEatingSpeed(arr,H);
    System.out.println(ans);
  }
}
23

Complexity Analysis of Koko Eating Bananas Leetcode Solution

Time complexity

The time complexity of the above code is O(n*log(W)) because we are performing a binary search between one and W this takes logW time and for each value, in the binary search, we are traversing the piles array.  So the piles array is traversed logW times it makes the time complexity n*logW. Here n and W are the numbers of piles and the maximum number of bananas in a pile.

Space complexity

The space complexity of the above code is O(1) because we are using only a variable to store the answer.

References

Translate »