Koko Eating Bananas

▶

Steps

setup

Initialize search boundaries

Set the initial search range for Koko's eating speed from 1 to the largest pile size, which is 11.

💡 Starting with the full possible speed range ensures we don't miss the minimum feasible speed.

Line:

low, high = 1, max(piles)

💡 The search space covers all possible speeds from slowest (1) to fastest (max pile).

compare

Calculate mid speed candidate

Calculate mid as the average of low and high: (1 + 11) // 2 = 6. This is the candidate speed to test.

💡 Midpoint divides the search space to test feasibility efficiently.

Line:

mid = (low + high) // 2

💡 Testing speed 6 will tell us if we can finish in time at this speed or need to adjust.

compare

Check feasibility at speed 6

Calculate hours needed at speed 6: ceil(3/6)=1, ceil(6/6)=1, ceil(7/6)=2, ceil(11/6)=2; total 6 hours, which is <= 8.

💡 Feasibility check confirms if Koko can finish all piles within the hour limit at this speed.

Line:

if can_finish(piles, mid, h):

💡 Speed 6 is fast enough, so we can try slower speeds to find minimum.

compare

Calculate new mid speed candidate

Calculate mid as (1 + 6) // 2 = 3 to test a slower speed.

💡 Testing slower speeds helps find the minimum feasible speed.

Line:

mid = (low + high) // 2

💡 Speed 3 will be tested next for feasibility.

compare

Check feasibility at speed 3

Calculate hours at speed 3: ceil(3/3)=1, ceil(6/3)=2, ceil(7/3)=3, ceil(11/3)=4; total 10 hours, which is > 8.

💡 If total hours exceed limit, speed is too slow.

Line:

if can_finish(piles, mid, h):

💡 Speed 3 is too slow, so we discard speeds <= 3.

compare

Calculate new mid speed candidate

Calculate mid as (4 + 6) // 2 = 5 to test a speed between 4 and 6.

💡 Narrowing search space by testing midpoints.

Line:

mid = (low + high) // 2

💡 Speed 5 is the next candidate to test.

compare

Check feasibility at speed 5

Calculate hours at speed 5: ceil(3/5)=1, ceil(6/5)=2, ceil(7/5)=2, ceil(11/5)=3; total 8 hours, which is <= 8.

💡 Feasibility check confirms speed 5 is sufficient.

Line:

if can_finish(piles, mid, h):

💡 Speed 5 works, so try slower speeds to find minimum.

compare

Calculate new mid speed candidate

Calculate mid as (4 + 5) // 2 = 4 to test speed 4.

💡 Testing the next candidate speed to narrow down minimum.

Line:

mid = (low + high) // 2

💡 Speed 4 is the next candidate to test.

compare

Check feasibility at speed 4

Calculate hours at speed 4: ceil(3/4)=1, ceil(6/4)=2, ceil(7/4)=2, ceil(11/4)=3; total 8 hours, which is <= 8.

💡 Speed 4 is feasible, so we try to find if slower speeds work.

Line:

if can_finish(piles, mid, h):

💡 Speed 4 works, so we reduce high to 4.

prune

Conclude search with low == high

Since low equals high (4), the minimum feasible speed is found and returned.

💡 When search space narrows to one value, that is the answer.

Line:

return low

💡 The minimum speed to finish in time is 4.

from math import ceil

def can_finish(piles, speed, h):
    hours = 0
    for pile in piles:
        hours += ceil(pile / speed)
        if hours > h:
            return False
    return True

def minEatingSpeed(piles, h):
    low, high = 1, max(piles)  # STEP 1
    while low < high:
        mid = (low + high) // 2  # STEP 2,4,6,8
        if can_finish(piles, mid, h):  # STEP 3,5,7,9
            high = mid
        else:
            low = mid + 1
    return low  # STEP 10

if __name__ == '__main__':
    piles = [3,6,7,11]
    h = 8
    print(minEatingSpeed(piles, h))  # Output: 4

📊

Koko Eating Bananas - Watch the Algorithm Execute, Step by Step

Watching each step of the binary search on the answer space reveals how the algorithm efficiently finds the minimum speed without checking every possible speed.

3

0

lo

6

1

7

2

11

3

Next: lo=1 hi=11

Target: 6

3

0

lo

6

1

7

2

11

3

Next: lo=1 hi=11

Target: 6

3

0

lo

6

1

7

2

11

3

Next: lo=1 hi=6

Target: 3

3

0

lo

6

1

7

2

mid

11

3

mid[3]=3 - pending feasibility check

Next: lo=1 hi=6

Target: 3

3

0

lo

6

1

7

2

mid

11

3

mid[3]=3 - not feasible (10 hours > 8)

Next: lo=4 hi=6

Target: 5

3

0

6

1

7

2

11

3

Next: lo=4 hi=6

Target: 5

3

0

6

1

7

2

11

3

Next: lo=4 hi=5

Target: 4

3

0

6

1

7

2

11

3

Next: lo=4 hi=5

Target: 4

3

0

6

1

7

2

11

3

Next: lo=4 hi=4

3

0

6

1

7

2

11

3

Next: lo=4 hi=4

Key Takeaways

✓ Binary search on the answer space efficiently finds the minimum feasible speed without checking every speed.

Reading code alone doesn't show how the search space shrinks visually and why fewer checks are needed.

✓ Feasibility checks with early stopping prevent unnecessary calculations once the hour limit is exceeded.

This optimization is subtle in code but critical for performance and is clear when watching the step-by-step checks.

✓ Adjusting low and high pointers based on feasibility results narrows the search space until the exact minimum speed is found.

Seeing the pointer movements and eliminated regions clarifies how decisions prune the search space.

Practice

1. You are given an array of positive integers and a threshold value. You want to find the smallest integer divisor such that when each array element is divided by this divisor and rounded up, the sum of these results does not exceed the threshold. Which algorithmic approach guarantees finding this smallest divisor efficiently?

easy

A. Greedy approach that picks divisors based on local minimum sums without backtracking

B. Dynamic programming to explore all divisor combinations and sums

C. Binary search on the divisor value combined with a feasibility check function

D. Sorting the array and using two pointers to find the divisor

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding the smallest divisor that satisfies a sum condition involving ceiling division, which is monotonic with respect to the divisor.

2. Step 2: Identify the suitable algorithmic pattern

   Binary search on the answer space (divisor values) combined with a helper feasibility function efficiently narrows down the smallest divisor by checking if a candidate divisor meets the threshold condition.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search exploits monotonicity of feasibility -> [OK]

Hint: Monotonic feasibility suggests binary search on answer space [OK]

Common Mistakes:

• Assuming greedy local choices yield global minimum divisor
• Trying DP which is inefficient and unnecessary here
• Using sorting and two pointers which don't apply to divisor search

2. Consider the following recursive binary search code for finding the insert position of target = 2 in nums = [1, 3, 5, 6]. What is the final returned value?

easy

A. 0

B. 1

C. 2

D. 3

Solution

1. Step 1: Trace binary_search(0, 3)

   mid = (0+3)//2 = 1, nums[1] = 3 > 2, recurse left: binary_search(0, 0)

2. Step 2: Trace binary_search(0, 0)

   mid = (0+0)//2 = 0, nums[0] = 1 < 2, recurse right: binary_search(1, 0)

3. Step 3: Base case binary_search(1, 0)

   left > right, return left = 1 as insertion index

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Target 2 fits between 1 and 3 at index 1 [OK]

Hint: Follow recursive calls and base case carefully [OK]

Common Mistakes:

• Returning right instead of left at base case
• Off-by-one in mid calculation
• Confusing left and right updates

3. You are given a sorted array where every element appears exactly twice except for one element which appears only once. Which algorithmic approach guarantees an optimal O(log n) time solution to find the single element?

easy

A. Modified binary search using index parity to halve the search space

B. Dynamic programming to store counts of elements and find the unique one

C. Linear scan checking pairs sequentially until the unique element is found

D. Greedy approach selecting elements based on local pair matches

Solution

1. Step 1: Understand problem constraints

   The array is sorted and every element except one appears twice consecutively.

2. Step 2: Identify algorithm that exploits sorted pairs

   Modified binary search using index parity halves the search space by comparing pairs, achieving O(log n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search with parity is known optimal for this problem [OK]

Hint: Use parity-based binary search for O(log n) solution [OK]

Common Mistakes:

• Thinking linear scan is optimal
• Using DP unnecessarily
• Applying greedy without global insight

4. Identify the bug in the following recursive binary search implementation:

def binary_search_recursive(nums, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if nums[mid] == target:
        return mid
    elif nums[mid] < target:
        return binary_search_recursive(nums, target, mid, high)
    else:
        return binary_search_recursive(nums, target, low, mid - 1)

What is the bug causing potential infinite recursion or incorrect results?

medium

A. Returning -1 too early before checking all elements

B. Line calculating mid without overflow protection

C. Base case condition low > high instead of low >= high

D. Recursive call with low updated to mid instead of mid + 1

Solution

1. Step 1: Examine recursive call when nums[mid] < target

   It calls with low=mid, which can cause infinite recursion if mid equals low.

2. Step 2: Correct update should be low=mid + 1

   This ensures progress by excluding mid from next search range.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Updating low to mid causes infinite loop on repeated mid values [OK]

Hint: Update low to mid + 1 to avoid infinite recursion [OK]

Common Mistakes:

• Using mid instead of mid+1
• Ignoring base case correctness
• Misplacing return statements

5. The following code attempts to compute the integer square root using Newton's method. Which line contains a subtle bug that can cause incorrect results or infinite loops for inputs 0 or 1?

medium

A. Line 1: def mySqrt(x: int) -> int:

B. Line 2: guess = x // 2

C. Line 3: while guess * guess > x:

D. Line 4: guess = (guess + x // guess) // 2

Solution

1. Step 1: Identify missing base case handling

   The code does not handle x=0 or x=1 explicitly, which can cause guess to be 0 and lead to division by zero or infinite loop.

2. Step 2: Pinpoint the bug line

   Line 2 initializes guess = x // 2 without checking if x < 2, causing issues for small inputs.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Proper base case handling prevents infinite loops [OK]

Hint: Always handle small inputs before iterative methods [OK]

Common Mistakes:

• Ignoring base cases
• Assuming guess initialization always valid
• Misplacing loop condition