Sponsored
Sponsored
Since the constraint for hours is very large, a direct approach may not work efficiently. Instead, we can use binary search on the possible eating speeds (from 1 to the maximum value in the piles) to find the minimum speed at which Koko can eat all the bananas in the allotted time. For a given speed, compute the number of hours Koko would need to eat all the bananas.
Time Complexity: O(N log M), where N is the number of piles and M is the maximum number of bananas in a pile. Space Complexity: O(1), as the additional space used by the algorithm does not depend on input size.
1using System;
2using System.Linq;
3public class Solution {
4 public int MinEatingSpeed(int[] piles, int h) {
5 int left = 1, right = piles.Max();
6 while (left < right) {
7 int mid = (left + right) / 2;
8 int hours = 0;
9 foreach (int pile in piles) {
10 hours += (int)Math.Ceiling((double)pile / mid);
11 }
12 if (hours <= h) right = mid;
13 else left = mid + 1;
14 }
15 return left;
16 }
17}The C# algorithm adopts a binary search over possible speeds. It leverages LINQ to find the maximum pile size and performs iterative checks to ensure the calculated eating hours do not exceed the provided time.
In this approach, we iterate over every possible eating speed from 1 to the maximum pile size and check if Koko can finish eating all within h hours. Although inefficient for large inputs, it works correctly for smaller constraints but mainly serves as a fallback understanding of the problem dynamics.
Time Complexity: O(N * M), where N is the number of piles and M is the largest pile size. Space Complexity: O(1).
1class Solution:
2 def minEatingSpeed(self, piles, h):
3The brute force Python solution iteratively checks each potential speed and calculates the total hours required with a direct loop comparison. It returns the first speed that allows completing all piles within the time limit.