Koko Eating Bananas

Why it belongs on this sheet

This is one of the cleanest examples of binary search on the answer, which is a huge interview pattern.

Pattern

Search on answer

Approach

The speed is the unknown answer. Check whether a candidate speed finishes all piles within h hours. Since feasibility is monotonic, binary search over speed works.

Java solution

class Solution {
  public int minEatingSpeed(int[] piles, int h) {
    int left = 1;
    int right = 0;

    for (int pile : piles) {
      right = Math.max(right, pile);
    }

    while (left < right) {
      int mid = left + (right - left) / 2;

      if (canFinish(piles, h, mid)) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }

    return left;
  }

  private boolean canFinish(int[] piles, int h, int speed) {
    long hours = 0;
    for (int pile : piles) {
      hours += (pile + speed - 1) / speed;
    }
    return hours <= h;
  }
}

Complexity

• Time: O(n log m) where m is the maximum pile size
• Space: O(1)

Interview note

Whenever you can answer "is this candidate feasible?", start thinking about search on answer.