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.
1import java.util.*;
2public class Solution {
3 public int minEatingSpeed(int[] piles, int h) {
4 int left = 1, right = Arrays.stream(piles).max().getAsInt();
5 while (left < right) {
6 int mid = left + (right - left) / 2;
7 int hours = 0;
8 for (int pile : piles) {
9 hours += (pile + mid - 1) / mid;
10 }
11 if (hours <= h) right = mid;
12 else left = mid + 1;
13 }
14 return left;
15 }
16}In Java, the solution incorporates a binary search pattern across possible speeds. It uses Java's stream API to find the maximum value in the pile array efficiently, performs a binary search, and checks the feasibility of the mid speed value by calculating the necessary hours.
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.