Koko Eating Bananas

📋

Problem

Koko loves eating bananas but wants to finish them all before the guards come back. She needs to figure out the minimum speed to eat all bananas within a limited time.

Koko has n piles of bananas, where piles[i] is the number of bananas in the ith pile. Guards will come back in h hours. Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats k bananas from it. If the pile has less than k bananas, she eats all of them and stops eating for that hour. Return the minimum integer k such that Koko can eat all bananas within h hours.

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

Edge cases: Single pile with bananas equal to h → minimum speed is 1All piles have 1 banana and h equals number of piles → minimum speed is 1Very large piles with h equal to number of piles → minimum speed equals max pile size

</>

IDE

def minEatingSpeed(piles: list[int], h: int) -> int:public int minEatingSpeed(int[] piles, int h)int minEatingSpeed(vector<int>& piles, int h)function minEatingSpeed(piles, h)

def minEatingSpeed(piles, h):
    # Write your solution here
    pass

class Solution {
    public int minEatingSpeed(int[] piles, int h) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minEatingSpeed(vector<int>& piles, int h) {
    // Write your solution here
    return 0;
}

function minEatingSpeed(piles, h) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: max pile sizeGreedy approach assuming minimum speed is max pile size without binary searching lower speeds.✅ Implement binary search on speed range [1, max pile size] with feasibility check using ceiling division.

Wrong: 1Misunderstanding problem constraints leading to underestimating minimum speed, especially when h < total piles.✅ Use feasibility function summing ceil(pile / speed) and binary search to find minimal speed that meets h.

Wrong: speed less than max pile sizeOff-by-one error in binary search boundaries or mid calculation causing premature termination.✅ Carefully update low and high pointers and use mid = low + (high - low) // 2 to avoid infinite loops.

Wrong: error or incorrect speedNot handling empty piles input causing exceptions or invalid results.✅ Add explicit check for empty piles and return 0 immediately.

Wrong: TLEUsing brute force linear search on speed instead of binary search on answer space.✅ Implement binary search on speed range with O(n log m) complexity feasibility checks.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly to avoid runtime errors.

Think about common algorithmic pitfalls like greedy assumptions and off-by-one errors in binary search.

Optimize your solution to handle large inputs efficiently using binary search and pruning.

t1_01basic

Input{"piles":[3,6,7,11],"h":8}

Expected4

⏱ Performance - must finish in 2000ms

At speed 4, Koko can finish piles in 8 hours: 3/4=1h, 6/4=2h, 7/4=2h, 11/4=3h total 8h.

💡 Consider binary searching the eating speed between 1 and max pile size.

💡 Check feasibility by summing ceil(pile / speed) for all piles and compare with h.

💡 Adjust binary search boundaries based on feasibility to find minimum speed.

Why it failed: Returned speed too high or low due to incorrect feasibility check or binary search boundaries. Fix by correctly computing hours with ceiling division and updating search range accordingly.

✓ Correctly implements binary search on answer space with proper feasibility check.

t1_02basic

Input{"piles":[30,11,23,4,20],"h":5}

Expected30

⏱ Performance - must finish in 2000ms

Minimum speed is 30 because Koko must finish 5 piles in 5 hours, so speed must be at least max pile size.

💡 When h equals number of piles, minimum speed is at least max pile size.

💡 Check if speed less than max pile size causes total hours to exceed h.

💡 Binary search should start at 1 and end at max pile size to find minimum feasible speed.

Why it failed: Incorrectly returns speed less than max pile size causing total hours to exceed h. Fix by ensuring binary search upper bound is max pile size and feasibility check uses ceiling division.

✓ Correctly identifies minimum speed as max pile size when h equals number of piles.

t2_01edge

Input{"piles":[],"h":0}

Expected0

⏱ Performance - must finish in 2000ms

No piles and zero hours means no eating needed, so minimum speed is 0.

💡 Consider the case when there are no piles to eat.

💡 If piles is empty, minimum speed should be zero regardless of h.

💡 Return 0 immediately if piles is empty to handle this edge case.

Why it failed: Fails to handle empty piles input causing errors or incorrect speed. Fix by adding a check for empty piles and returning 0.

✓ Correctly returns 0 speed when no piles are present.

t2_02edge

Input{"piles":[10],"h":10}

Expected1

⏱ Performance - must finish in 2000ms

Single pile with bananas equal to h means minimum speed is 1 to finish in time.

💡 With one pile and h equal to pile size, speed can be as low as 1.

💡 Check if speed 1 is feasible by summing hours needed.

💡 Binary search should consider lower bound 1 and upper bound pile size.

Why it failed: Returns speed greater than 1 incorrectly due to wrong feasibility calculation. Fix by correctly computing hours with ceiling division and allowing speed=1 if feasible.

✓ Correctly returns minimum speed 1 for single pile equal to h.

t2_03edge

Input{"piles":[1,1,1,1],"h":4}

Expected1

⏱ Performance - must finish in 2000ms

All piles have 1 banana and h equals number of piles, so minimum speed is 1.

💡 When each pile has 1 banana and h equals number of piles, speed 1 suffices.

💡 Feasibility check should confirm speed 1 finishes in h hours.

💡 Binary search lower bound 1 should be returned if feasible.

Why it failed: Incorrectly returns speed > 1 due to miscalculated hours or binary search bounds. Fix by ensuring feasibility check uses ceiling division and binary search includes speed=1.

✓ Correctly returns speed 1 when all piles are 1 banana and h equals piles count.

t3_01corner

Input{"piles":[30,11,23,4,20],"h":6}

Expected23

⏱ Performance - must finish in 2000ms

Greedy approach picking max pile size as speed fails here; minimum speed is 23 to finish in 6 hours.

💡 Greedy picking max pile size as speed may be too high and not minimal.

💡 Use binary search on speed and check feasibility for each candidate speed.

💡 Adjust binary search bounds based on feasibility to find minimal speed.

Why it failed: Greedy approach returns 30 instead of 23, missing minimal speed. Fix by implementing binary search on answer space with feasibility check.

✓ Correctly finds minimal speed 23 using binary search, avoiding greedy trap.

t3_02corner

Input{"piles":[312884470],"h":312884469}

Expected2

⏱ Performance - must finish in 2000ms

Tests confusion between 0/1 knapsack and unbounded; speed must be at least 2 to finish in time.

💡 Do not confuse problem with 0/1 knapsack; speed can be any integer.

💡 Check feasibility by summing ceil(pile / speed) and compare with h.

💡 Binary search must consider all speeds between 1 and max pile size.

Why it failed: Incorrectly returns 1 due to misunderstanding problem constraints. Fix by correctly implementing feasibility check with ceiling division and binary search.

✓ Correctly returns speed 2 respecting problem constraints.

t3_03corner

Input{"piles":[1,1000000000],"h":2}

Expected1000000000

⏱ Performance - must finish in 2000ms

Off-by-one errors in binary search can cause incorrect speed; minimum speed equals max pile size here.

💡 Check binary search mid calculation and update boundaries carefully.

💡 Ensure feasibility check uses ceiling division correctly.

💡 Avoid infinite loops by updating low and high pointers properly.

Why it failed: Returns speed less than max pile size due to off-by-one error in binary search. Fix by correctly updating low and high pointers and using ceiling division.

✓ Correctly returns max pile size as minimum speed with proper binary search.

t4_01performance

Input{"piles":[1000000000,999999999,999999998,999999997,999999996,999999995,999999994,999999993,999999992,999999991,999999990,999999989,999999988,999999987,999999986,999999985,999999984,999999983,999999982,999999981,999999980,999999979,999999978,999999977,999999976,999999975,999999974,999999973,999999972,999999971,999999970,999999969,999999968,999999967,999999966,999999965,999999964,999999963,999999962,999999961,999999960,999999959,999999958,999999957,999999956,999999955,999999954,999999953,999999952,999999951,999999950,999999949,999999948,999999947,999999946,999999945,999999944,999999943,999999942,999999941,999999940,999999939,999999938,999999937,999999936,999999935,999999934,999999933,999999932,999999931,999999930,999999929,999999928,999999927,999999926,999999925,999999924,999999923,999999922,999999921,999999920,999999919,999999918,999999917,999999916,999999915,999999914,999999913,999999912,999999911,999999910,999999909,999999908,999999907,999999906,999999905,999999904,999999903,999999902,999999901,999999900],"h":100000}

Expectednull

⏱ Performance - must finish in 2000ms

Large input with n=100 and large pile sizes to test O(n log m) complexity within 2 seconds.

💡 Brute force linear search on speed will time out due to large max pile size.

💡 Use binary search on answer space to reduce complexity to O(n log m).

💡 Implement early stopping in feasibility check to optimize performance.

Why it failed: Brute force or naive linear search causes TLE due to O(n * max(pile)) complexity. Fix by implementing binary search on answer space with O(n log m) complexity.

✓ Efficient binary search solution runs within time limits confirming O(n log m) complexity.

Practice

1. You are given an array of positions of balls on a number line and a number m. You want to place m balls in these positions such that the minimum distance between any two balls is maximized. Which algorithmic approach guarantees finding the optimal minimum distance efficiently?

easy

A. Binary search on the answer space combined with a greedy feasibility check

B. Greedy placement by always placing balls at the closest possible positions without backtracking

C. Dynamic programming to consider all subsets of positions and their minimum distances

D. Sorting the positions and then using a sliding window to find the maximum minimum distance

Solution

1. Step 1: Understand the problem structure

   The problem asks to maximize the minimum distance between placed balls, which is a classic optimization problem over a numeric answer space.

2. Step 2: Identify the correct approach

   Binary search on the answer space (possible distances) combined with a greedy feasibility check efficiently finds the maximum minimum distance. Greedy alone or DP are either incorrect or inefficient.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search narrows down distance candidates efficiently [OK]

Hint: Maximize minimum distance -> binary search on answer space [OK]

Common Mistakes:

• Thinking greedy alone suffices without binary search
• Using DP which is inefficient here

2. What is the worst-case time complexity of the optimal modified binary search algorithm to find the minimum in a rotated sorted array with duplicates?

medium

A. O(n log n)

B. O(log n)

C. O(n)

D. O(1)

Solution

1. Step 1: Understand binary search with duplicates

   Duplicates can cause the algorithm to reduce high by one each iteration when nums[mid] == nums[high], leading to linear scan behavior.

2. Step 2: Analyze worst-case scenario

   In worst case (all elements equal), the algorithm degrades to O(n) because it may shrink high by one each time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Duplicates cause worst-case linear time [OK]

Hint: Duplicates cause worst-case linear time despite binary search [OK]

Common Mistakes:

• Assuming always O(log n)
• Confusing average and worst case

3. What is the time complexity of the iterative fast exponentiation algorithm for computing x^n where n is a 32-bit integer?

medium

A. O(n)

B. O(n log n)

C. O(log n)

D. O(1)

Solution

1. Step 1: Identify loop iterations

   The algorithm halves n each iteration, so the loop runs approximately log₂(n) times.

2. Step 2: Confirm work per iteration

   Each iteration does a constant number of multiplications and divisions, so total time is O(log n).

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Halving exponent each step -> logarithmic time [OK]

Hint: Halving exponent means O(log n) time [OK]

Common Mistakes:

• Confusing with O(n) from naive multiplication
• Assuming O(1) due to constant ops per iteration
• Thinking recursion adds extra complexity

4. Examine the following buggy code that attempts to search a target in a 2D matrix using the staircase search approach starting from the top-left corner. Identify the line containing the subtle bug that causes incorrect behavior or infinite loops.

medium

A. Line 9: Incrementing row when element is less than target

B. Line 7: Using '<' instead of '<=' in while condition

C. Line 11: Decrementing col without boundary check

D. Line 3: Starting at top-left corner instead of top-right

Solution

1. Step 1: Analyze starting point

   Starting at top-left corner breaks the staircase search logic because we cannot eliminate rows or columns correctly.

2. Step 2: Check pointer movements

   Moving row down when current < target and col left when current > target only works if starting at top-right corner.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Starting at top-left causes infinite loops or wrong results [OK]

Hint: Staircase search must start at top-right corner [OK]

Common Mistakes:

• Starting at top-left or bottom-left corner
• Not checking empty matrix
• Moving pointers in wrong directions

5. Suppose the problem is modified so that packages can be shipped in any order (not necessarily the given order) within the given days. Which of the following approaches correctly finds the minimal ship capacity under this new constraint?

hard

A. Use dynamic programming to assign packages to days minimizing maximum load per day, combined with binary search on capacity

B. Sort packages in descending order and use a greedy bin-packing heuristic combined with binary search on capacity

C. Use a simple greedy approach assigning packages to days in any order without binary search

D. Use the same binary search on capacity with the original feasibility check since order doesn't matter

Solution

1. Step 1: Understand the relaxed constraint

   Packages can be shipped in any order, so the problem becomes a variant of multi-way partition or bin packing minimizing max load.

2. Step 2: Identify correct approach

   Binary search on capacity still applies, but feasibility check requires DP or backtracking to assign packages optimally to days, as greedy heuristics may fail.

3. Step 3: Why other options fail

   Original feasibility check assumes fixed order; greedy heuristics are approximate and may not find minimal capacity.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   DP feasibility check with binary search needed for unordered assignment [OK]

Hint: Order relaxation requires DP feasibility check, not simple greedy [OK]

Common Mistakes:

• Using original feasibility check ignoring order change
• Assuming greedy suffices
• Ignoring complexity increase