Longest Mountain in Array

Description

Koko loves eating bananas. There are n piles of bananas, where the i-th pile contains piles[i] bananas. The guards have left and will return in h hours.

Koko can choose her eating speed k (bananas per hour). Each hour, she picks one pile and eats up to k bananas from it. If a pile has fewer than k bananas, she finishes the entire pile in that hour and does not eat any more bananas during that hour (she cannot move to another pile in the same hour).

Koko wants to eat as slowly as possible (to savor the bananas) while still finishing all bananas before the guards return.

Return the minimum integer k such that Koko can eat all the bananas within h hours.

Examples

Example 1

Input: piles = [3, 6, 7, 11], h = 8

Output: 4

Explanation: At speed k = 4 bananas/hour:

Pile 3: ⌈3/4⌉ = 1 hour
Pile 6: ⌈6/4⌉ = 2 hours
Pile 7: ⌈7/4⌉ = 2 hours
Pile 11: ⌈11/4⌉ = 3 hours
Total = 1 + 2 + 2 + 3 = 8 hours ≤ h = 8. ✓

At speed k = 3: ⌈3/3⌉ + ⌈6/3⌉ + ⌈7/3⌉ + ⌈11/3⌉ = 1 + 2 + 3 + 4 = 10 hours > 8. ✗

So 4 is the minimum speed that works.

Example 2

Input: piles = [30, 11, 23, 4, 20], h = 5

Output: 30

Explanation: There are 5 piles and only 5 hours — exactly one hour per pile. Koko must finish each pile in exactly one hour, so she needs speed k = max(piles) = 30. Any speed lower than 30 would require more than 1 hour for the pile of 30 bananas, exceeding the time limit.

Example 3

Input: piles = [30, 11, 23, 4, 20], h = 6

Output: 23

Explanation: With one extra hour beyond the number of piles, Koko can afford to eat more slowly. At speed 23:

Pile 30: ⌈30/23⌉ = 2 hours
Pile 11: ⌈11/23⌉ = 1 hour
Pile 23: ⌈23/23⌉ = 1 hour
Pile 4: ⌈4/23⌉ = 1 hour
Pile 20: ⌈20/23⌉ = 1 hour
Total = 2 + 1 + 1 + 1 + 1 = 6 hours ≤ 6. ✓

Constraints

1 ≤ piles.length ≤ 10^4
piles.length ≤ h ≤ 10^9
1 ≤ piles[i] ≤ 10^9

Editorial

Brute Force

Intuition

The most direct way to find the minimum eating speed is to try every possible speed starting from 1, and for each speed, calculate how many total hours Koko needs to finish all piles.

Imagine you are setting the speed dial on a banana-eating machine. You start at speed 1 (the slowest), calculate if Koko can finish in time, and if not, you increment the dial by 1 and try again. The first speed that gets Koko done within h hours is your answer.

For a given speed k, the time to eat a pile of size p is ⌈p / k⌉ (ceiling division), because even a single leftover banana requires a full hour. The total hours needed is the sum of ceiling divisions across all piles.

The maximum possible speed Koko would ever need is max(piles) — eating faster than the largest pile gives no benefit since she can only eat from one pile per hour.

Step-by-Step Explanation

Let's trace through with piles = [3, 6, 7, 11], h = 8:

Step 1: Try speed k = 1.

Hours: ⌈3/1⌉ + ⌈6/1⌉ + ⌈7/1⌉ + ⌈11/1⌉ = 3 + 6 + 7 + 11 = 27.
Is 27 ≤ 8? No. Way too slow.

Step 2: Try speed k = 2.

Hours: ⌈3/2⌉ + ⌈6/2⌉ + ⌈7/2⌉ + ⌈11/2⌉ = 2 + 3 + 4 + 6 = 15.
Is 15 ≤ 8? No. Still too slow.

Step 3: Try speed k = 3.

Hours: ⌈3/3⌉ + ⌈6/3⌉ + ⌈7/3⌉ + ⌈11/3⌉ = 1 + 2 + 3 + 4 = 10.
Is 10 ≤ 8? No. Getting closer but not enough.

Step 4: Try speed k = 4.

Hours: ⌈3/4⌉ + ⌈6/4⌉ + ⌈7/4⌉ + ⌈11/4⌉ = 1 + 2 + 2 + 3 = 8.
Is 8 ≤ 8? Yes! First speed that works.

Step 5: Return k = 4.

Brute Force — Trying Every Speed from 1 Upward — Watch how we try each eating speed sequentially, computing total hours for each, until we find the first speed that finishes within h hours.

Algorithm

Find maxPile = maximum value in piles (the upper bound for speed)
For each speed k from 1 to maxPile:
- Compute totalHours = sum of ⌈piles[i] / k⌉ for all piles
- If totalHours ≤ h, return k (first valid speed is the minimum)
Return maxPile (guaranteed to work since h ≥ piles.length)

Note on ceiling division: ⌈a / b⌉ can be computed as (a + b - 1) / b using integer arithmetic, avoiding floating-point operations.

Code

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int maxPile = *max_element(piles.begin(), piles.end());
        
        for (int k = 1; k <= maxPile; k++) {
            long long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + k - 1) / k;
            }
            if (totalHours <= h) {
                return k;
            }
        }
        
        return maxPile;
    }
};

import math
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        max_pile = max(piles)
        
        for k in range(1, max_pile + 1):
            total_hours = sum(math.ceil(pile / k) for pile in piles)
            if total_hours <= h:
                return k
        
        return max_pile

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int maxPile = 0;
        for (int pile : piles) {
            maxPile = Math.max(maxPile, pile);
        }
        
        for (int k = 1; k <= maxPile; k++) {
            long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + k - 1) / k;
            }
            if (totalHours <= h) {
                return k;
            }
        }
        
        return maxPile;
    }
}

Complexity Analysis

Time Complexity: O(n × m), where n = number of piles and m = max(piles)

For each candidate speed from 1 to m, we iterate through all n piles to compute the total hours. In the worst case, we try all m speeds before finding the answer. With n up to 10^4 and m up to 10^9, this results in up to 10^13 operations — far too slow.

Space Complexity: O(1)

We only use a few variables (k, totalHours, maxPile). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force tries speeds 1, 2, 3, ..., up to max(piles), performing O(n) work at each speed to calculate total hours. With max(piles) up to 10^9 and n up to 10^4, the total work can be up to 10^13 operations — this would take thousands of seconds, far exceeding any reasonable time limit.

The critical observation is that the total hours function is monotonically decreasing as speed increases. If speed k = 5 finishes in 10 hours, then speed k = 6 finishes in ≤ 10 hours (eating faster can only reduce or maintain the total time, never increase it). This means the speeds naturally divide into two zones:

Too slow zone: speeds where total hours > h (cannot finish in time)
Fast enough zone: speeds where total hours ≤ h (can finish in time)

We want the leftmost speed in the "fast enough" zone — which is precisely a binary search boundary problem. Instead of checking every speed linearly, binary search can find this boundary in O(log m) checks, each costing O(n) work, for a total of O(n × log m).

Optimal Approach - Binary Search on Answer

Intuition

Instead of trying every speed from 1 upward, we apply binary search on the answer space — the range of possible eating speeds [1, max(piles)].

The insight is that the relationship between eating speed and total hours is monotonic: as speed increases, total hours decreases (or stays the same). This creates a clear partition:

Speeds:  1  2  3  4  5  6  7  8  9  10  11
Fits?:   ✗  ✗  ✗  ✓  ✓  ✓  ✓  ✓  ✓  ✓   ✓
                    ↑
          first valid (answer)

We want to find the leftmost speed where the answer flips from ✗ to ✓. Binary search does exactly this — it halves the search range each time by checking the middle speed:

If the middle speed works (total hours ≤ h), it could be the answer, but there might be an even slower valid speed. So we search the left half and save this as a candidate.
If the middle speed does not work (total hours > h), the answer must be a faster speed. So we search the right half.

Think of it like a thermostat. You want the lowest temperature that keeps the room warm enough. Instead of trying 1°, 2°, 3°, ..., you jump to the middle, check if it is warm, and narrow the range by half each time.

Step-by-Step Explanation

Let's trace through with piles = [3, 6, 7, 11], h = 8:

Step 1: Initialize search range. lo = 1, hi = max(piles) = 11, result = 11.

Step 2: Compute mid = (1 + 11) / 2 = 6.

Hours at speed 6: ⌈3/6⌉ + ⌈6/6⌉ + ⌈7/6⌉ + ⌈11/6⌉ = 1 + 1 + 2 + 2 = 6.
Is 6 ≤ 8? Yes. Speed 6 works! Save result = 6. But maybe a slower speed also works.
Search left: hi = mid - 1 = 5. Range becomes [1, 5].

Step 3: Compute mid = (1 + 5) / 2 = 3.

Hours at speed 3: ⌈3/3⌉ + ⌈6/3⌉ + ⌈7/3⌉ + ⌈11/3⌉ = 1 + 2 + 3 + 4 = 10.
Is 10 ≤ 8? No. Speed 3 is too slow.
Search right: lo = mid + 1 = 4. Range becomes [4, 5].

Step 4: Compute mid = (4 + 5) / 2 = 4.

Hours at speed 4: ⌈3/4⌉ + ⌈6/4⌉ + ⌈7/4⌉ + ⌈11/4⌉ = 1 + 2 + 2 + 3 = 8.
Is 8 ≤ 8? Yes. Speed 4 works! Save result = 4. Try even slower.
Search left: hi = mid - 1 = 3. Range becomes [4, 3].

Step 5: lo (4) > hi (3), so the loop ends.

Step 6: Return result = 4. Binary search found the answer in just 3 iterations instead of 4.

Binary Search on Answer — Finding Minimum Eating Speed — Watch how binary search halves the speed range at each step, efficiently finding the minimum speed where Koko can finish within h hours.

Algorithm

Find maxPile = maximum value in piles
Set lo = 1, hi = maxPile, result = maxPile
While lo ≤ hi:
- Compute mid = lo + (hi - lo) / 2
- Calculate totalHours = sum of ⌈piles[i] / mid⌉ for all piles
- If totalHours ≤ h:
  - Update result = mid (this speed works, but a slower one might too)
  - Set hi = mid - 1 (search for a potentially slower valid speed)
- Else:
  - Set lo = mid + 1 (this speed is too slow, search faster)
Return result

Key detail: Use long for totalHours to avoid integer overflow, since with 10^4 piles each taking up to 10^9 hours, the sum can reach 10^13.

Code

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int lo = 1;
        int hi = *max_element(piles.begin(), piles.end());
        int result = hi;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            
            long long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + mid - 1) / mid;
            }
            
            if (totalHours <= h) {
                result = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        
        return result;
    }
};

import math
from typing import List

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        lo, hi = 1, max(piles)
        result = hi
        
        while lo <= hi:
            mid = lo + (hi - lo) // 2
            
            total_hours = sum(math.ceil(pile / mid) for pile in piles)
            
            if total_hours <= h:
                result = mid
                hi = mid - 1
            else:
                lo = mid + 1
        
        return result

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        int lo = 1;
        int hi = 0;
        for (int pile : piles) {
            hi = Math.max(hi, pile);
        }
        int result = hi;
        
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            
            long totalHours = 0;
            for (int pile : piles) {
                totalHours += (pile + mid - 1) / mid;
            }
            
            if (totalHours <= h) {
                result = mid;
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × log m), where n = number of piles and m = max(piles)

Binary search runs for O(log m) iterations. Each iteration computes the total hours by iterating through all n piles, costing O(n) per iteration. For m = 10^9 and n = 10^4, this gives approximately 30 × 10^4 = 3 × 10^5 operations — extremely fast.

Space Complexity: O(1)

We use only a constant number of variables (lo, hi, mid, result, totalHours). No additional data structures are needed regardless of input size.