These are the notes for DSA episode 14, the third episode of the binary search block. In episodes 12 and 13 binary search needed a sorted array. Here there is no sorted array at all: we binary search over the range of possible answers. Two classic problems fall to it: Koko Eating Bananas (LeetCode 875) and Aggressive Cows (SPOJ AGGRCOW, also on GeeksforGeeks). Trying every answer one by one takes up to 10⁹ tries and times out; binary search on the answer needs about 30. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
Your exam is tomorrow. Four chapters are left, with 3, 6, 7 and 11 pages, and you have 8 hours. You study in one-hour slots and each slot is for one chapter only: if a chapter finishes in the middle of a slot, you rest for the rest of that hour. Reading fast tires you and you remember less, so: what is the slowest speed, in pages per hour, that still finishes everything in 8 hours? (Answer: 4.)
Problem statement (Koko Eating Bananas, LeetCode 875)
There are n piles of bananas, piles[i] in pile i, and h hours. Koko picks a speed k: each hour she eats up to k bananas from one pile (if the pile has fewer, she eats them all and waits for the next hour). A pile of x bananas takes ⌈x / k⌉ hours (rounded up). Return the smallest k that finishes all piles within h hours.
Constraints: 1 <= n <= 10⁴, n <= h <= 10⁹, 1 <= piles[i] <= 10⁹.
| piles | h | answer | why |
|---|---|---|---|
| [3, 6, 7, 11] | 8 | 4 | 1 + 2 + 2 + 3 = 8 hours |
| [30, 11, 23, 4, 20] | 5 | 30 | 5 piles in 5 hours: every pile in one hour |
| [30, 11, 23, 4, 20] | 6 | 23 | the pile of 30 now takes 2 hours |
| [1000000000] | 2 | 500000000 | |
| [5] | 10 | 1 | plenty of time: the slowest speed |
Solution 1: brute force (try speed 1, 2, 3, ...)
import java.util.*;
public class Main {
static long hours(int[] p, int k) {
long h = 0;
for (int x : p) h += (x + k - 1) / k;
return h;
}
static int minSpeed(int[] p, int h) {
int k = 1;
while (hours(p, k) > h) k++;
return k;
}
public static void main(String[] args) {
System.out.println(minSpeed(new int[]{3, 6, 7, 11}, 8));
System.out.println(minSpeed(new int[]{30, 11, 23, 4, 20}, 5));
}
}
Output:
4
30
(x + k - 1) / k is integer division rounded up (the ceiling). The total is a long, because at small speeds it can reach n × 10⁹.
Now a real input: one lakh piles of 10⁹ bananas each, and 2 lakh hours (the answer is 5 × 10⁸):
int[] p = new int[100000];
Arrays.fill(p, 1000000000);
long t0 = System.nanoTime();
int k = minSpeed(p, 200000);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(k + " " + ms + " ms");
Result: Time Limit Exceeded.
Why it is slow
- Trying one speed costs O(n): one pass over the piles.
- There can be up to
max(pile) = 10⁹speeds to try, so the brute force is O(n · max). Here: 5 × 10⁸ tries × 10⁵ piles. - We check the answers one by one, in order, like reading a dictionary from page 1.
The key insight: a yes/no question that is sorted
Forget the piles and look at the answers. For every speed k from 1 to the biggest pile, write the hours needed, and ask "does it finish within h?":
| speed k | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| hours | 27 | 15 | 10 | 8 | 8 | 6 | 5 | 5 | 5 | 5 | 4 |
| <= 8 ? | no | no | no | yes | yes | yes | yes | yes | yes | yes | yes |
A faster speed never needs more hours, so the yes/no row is all no's, then all yes's. It is sorted! A condition like this is called monotonic. We want the first yes, which is a lower bound, exactly the template from episode 12, applied to the range of answers instead of an array.
Binary search on the answer:
- Search space: speeds
lo = 1 ... hi = max(pile)(speedmax(pile)always works: one hour per pile). - Question:
ok(k) = hours(k) <= h. ok(mid)→midmight be the answer, keep it:hi = mid. Otherwisemidis too slow:lo = mid + 1.- log₂(10⁹) ≈ 30 checks, each O(n).
Dry run: minSpeed([3, 6, 7, 11], 8)
| Step | lo | hi | mid | hours(mid) | ok? | Action |
|---|---|---|---|---|---|---|
| 1 | 1 | 11 | 6 | 6 | yes | hi = 6 |
| 2 | 1 | 6 | 3 | 10 | no | lo = 4 |
| 3 | 4 | 6 | 5 | 8 | yes | hi = 5 |
| 4 | 4 | 5 | 4 | 8 | yes | hi = 4 |
| 5 | 4 | 4 | answer 4 |
Solution 2: Koko, typed live
import java.util.*;
public class Main {
static long hours(int[] p, int k) {
long h = 0;
for (int x : p) h += (x + k - 1) / k;
return h;
}
static int minSpeed(int[] p, int h) {
int lo = 1, hi = 1;
for (int x : p) hi = Math.max(hi, x);
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (hours(p, mid) <= h) hi = mid;
else lo = mid + 1;
}
return lo;
}
public static void main(String[] args) {
System.out.println(minSpeed(new int[]{3, 6, 7, 11}, 8));
System.out.println(minSpeed(new int[]{30, 11, 23, 4, 20}, 5));
System.out.println(minSpeed(new int[]{30, 11, 23, 4, 20}, 6));
System.out.println(minSpeed(new int[]{1000000000}, 2));
System.out.println(minSpeed(new int[]{5}, 10));
}
}
Output:
4
30
23
500000000
1
The input that timed out (10⁵ piles of 10⁹, h = 2 × 10⁵) printed:
500000000 23 ms
About 30 checks of one lakh piles each. (x + k - 1 stays inside int here because x, k <= 10⁹, so it is at most about 2 × 10⁹ - 1 < 2,147,483,647.)
The second problem: exam hall seats (Aggressive Cows)
An exam hall corridor has seats at fixed positions: 1, 2, 4, 8 and 9 metres. Three students write the exam, and the invigilator wants to stop copying: seat them so that the closest two are as far apart as possible. In the classic version these are stalls in a barn and cows that fight: Aggressive Cows. We maximise the minimum gap.
Flip it into a yes/no question: canSeat(d) = can every pair be at least d apart?
- Greedy check, O(n): sort the seats, put the first student at the first seat, then walk right and seat the next student at the first seat that is at least
dfrom the last one. Taking the earliest possible seat never hurts: it leaves the most room for everyone after. - Answers for every
d: 1 yes, 2 yes, 3 yes, 4 no, 5 no ... This time it is yes, then no (a bigger gap only gets harder). We want the last yes = first no - 1, the same trick as "last occurrence = lowerBound(t + 1) - 1" in episode 12.
Greedy check for d = 3: seat at 1; next seat >= 4 is 4; next seat >= 7 is 8 → 3 seated, yes. For d = 4: 1, then >= 5 is 8, then >= 12 none → only 2, no. Answer 3.
import java.util.*;
public class Main {
static boolean canSeat(int[] s, int c, int d) {
int placed = 1, last = s[0];
for (int i = 1; i < s.length; i++)
if (s[i] - last >= d) { placed++; last = s[i]; }
return placed >= c;
}
static int maxGap(int[] s, int c) {
Arrays.sort(s);
int lo = 1, hi = s[s.length - 1] - s[0] + 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (!canSeat(s, c, mid)) hi = mid;
else lo = mid + 1;
}
return lo - 1;
}
public static void main(String[] args) {
System.out.println(maxGap(new int[]{1, 2, 8, 4, 9}, 3));
System.out.println(maxGap(new int[]{1, 2, 8, 4, 9}, 2));
System.out.println(maxGap(new int[]{1, 2, 8, 4, 9}, 5));
System.out.println(maxGap(new int[]{0, 1000000000}, 2));
}
}
Output:
3
8
1
1000000000
hi is one more than the largest possible gap, so the first "no" is always inside [lo, hi]. Two students sit at the two ends (8); five students use every seat (1).
The same solutions in C++ and Python
#include <bits/stdc++.h>
using namespace std;
long long hoursAt(const vector<int>& p, int k) {
long long h = 0;
for (int x : p) h += (x + (long long)k - 1) / k; // ceil(x / k)
return h;
}
int minSpeed(const vector<int>& p, long long h) {
int lo = 1, hi = *max_element(p.begin(), p.end());
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (hoursAt(p, mid) <= h) hi = mid;
else lo = mid + 1;
}
return lo;
}
bool canSeat(const vector<int>& s, int c, int d) {
int placed = 1, last = s[0];
for (size_t i = 1; i < s.size(); i++)
if (s[i] - last >= d) { placed++; last = s[i]; }
return placed >= c;
}
int maxGap(vector<int> s, int c) {
sort(s.begin(), s.end());
int lo = 1, hi = s.back() - s[0] + 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (!canSeat(s, c, mid)) hi = mid;
else lo = mid + 1;
}
return lo - 1;
}
int main() {
cout << minSpeed({3, 6, 7, 11}, 8) << " " << minSpeed({30, 11, 23, 4, 20}, 5) << " "
<< minSpeed({30, 11, 23, 4, 20}, 6) << " " << minSpeed({1000000000}, 2) << " " << minSpeed({5}, 10) << "\n";
cout << maxGap({1, 2, 8, 4, 9}, 3) << " " << maxGap({1, 2, 8, 4, 9}, 2) << " "
<< maxGap({1, 2, 8, 4, 9}, 5) << " " << maxGap({0, 1000000000}, 2) << "\n";
}
def hours(p, k):
return sum((x + k - 1) // k for x in p) # ceil(x / k)
def min_speed(p, h):
lo, hi = 1, max(p)
while lo < hi:
mid = (lo + hi) // 2
if hours(p, mid) <= h:
hi = mid
else:
lo = mid + 1
return lo
def can_seat(s, c, d):
placed, last = 1, s[0]
for x in s[1:]:
if x - last >= d:
placed += 1
last = x
return placed >= c
def max_gap(s, c):
s = sorted(s)
lo, hi = 1, s[-1] - s[0] + 1
while lo < hi:
mid = (lo + hi) // 2
if not can_seat(s, c, mid):
hi = mid
else:
lo = mid + 1
return lo - 1
print(min_speed([3, 6, 7, 11], 8), min_speed([30, 11, 23, 4, 20], 5),
min_speed([30, 11, 23, 4, 20], 6), min_speed([10**9], 2), min_speed([5], 10))
print(max_gap([1, 2, 8, 4, 9], 3), max_gap([1, 2, 8, 4, 9], 2),
max_gap([1, 2, 8, 4, 9], 5), max_gap([0, 10**9], 2))
Both print:
4 30 23 500000000 1
3 8 1 1000000000
Two real bugs
Bug 1: lo = 0 → / by zero
int lo = 0, hi = 1;
minSpeed(new int[]{5}, 10) crashed:
Exception in thread "main" java.lang.ArithmeticException: / by zero
at Main.hours(Main.java:4)
The answer is 1, so the search walks down to lo = 0, hi = 1, mid = 0, and hours divides by a speed of 0. We are searching answers, not indexes: start lo at the smallest answer that makes sense (speed 1).
Bug 2: forgetting to sort
Without Arrays.sort(s), maxGap(new int[]{1, 2, 8, 4, 9}, 3) printed 1 (should be 3). No error, just a wrong answer. The greedy walk assumes seats come left to right, and hi uses the first and last elements as the corridor's two ends; both are only true after sorting.
The recipe: binary search on the answer
- The answer is a number inside a range
[lo, hi]you can name. - Write
ok(x): isxgood enough? Usually a greedy pass, O(n). - Check it is monotonic: no ... no yes ... yes (find the first yes) or yes ... yes no ... no (find the last yes = first no - 1).
- Use the lower-bound template to find where it flips.
Hints in the statement: "minimise the maximum", "maximise the minimum", "the smallest value such that ...". The same recipe solves Capacity to Ship Packages Within D Days (1011), Split Array Largest Sum (410), Book Allocation, Minimum Days to Make m Bouquets (1482), Painter's Partition.
Complexity
| Approach | Time | Extra space | 10⁵ piles of 10⁹ |
|---|---|---|---|
| Koko, try k = 1, 2, 3, ... | O(n · max) | O(1) | Time Limit Exceeded |
| Koko, binary search on k | O(n · log max) | O(1) | 23 ms |
| Cows, try every d | O(n log n + n · range) | O(1) besides the sort | |
| Cows, binary search on d | O(n log n + n · log range) | O(1) besides the sort |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
int lo = 0 for a speed |
ArithmeticException: / by zero |
mid can become 0 |
lo = smallest valid answer (1) |
maxGap without Arrays.sort |
maxGap({1, 2, 8, 4, 9}, 3) = 1 |
greedy needs seats left to right | sort first |
x / k for the hours |
minSpeed({3, 6, 7, 11}, 8) = 3 (should be 4) |
integer division rounds down | (x + k - 1) / k rounds up |
int total hours |
can overflow: 10⁴ piles × 10⁹ hours at k = 1 = 10¹³ | sum bigger than 2,147,483,647 | long |
hi = mid - 1 when ok(mid) |
can skip the answer | mid itself may be the first yes |
hi = mid |
Cows: returning lo instead of lo - 1 |
one too big | lo ends on the first no |
lo - 1 |
Mini project: the study planner
Read the page counts of your chapters and the hours left. Print the slowest safe speed (minSpeed) and a timetable: for each chapter, how many one-hour slots it takes at that speed. Extension: given a maximum speed you can actually manage, print the minimum hours you need instead (binary search on hours, with the same ok idea).
Practice
- Capacity to Ship Packages Within D Days (LeetCode 1011): weights in order, the smallest ship capacity that ships everything in
daysdays.
Solution
Answer range: lo = max(weight) (a package can't be split), hi = sum(weights). ok(cap) = greedily fill each day up to cap and count days; ok is monotonic (bigger capacity, fewer days). First yes:
static int shipWithinDays(int[] w, int days) {
int lo = 0, hi = 0;
for (int x : w) { lo = Math.max(lo, x); hi += x; }
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
int need = 1, cur = 0;
for (int x : w) {
if (cur + x > mid) { need++; cur = 0; }
cur += x;
}
if (need <= days) hi = mid;
else lo = mid + 1;
}
return lo;
}
shipWithinDays({1, 2, ..., 10}, 5) printed 15.
- Split Array Largest Sum (LeetCode 410): split into
knon-empty contiguous parts, minimise the largest part's sum.
Solution
It is the same function as practice 1, with days = k: shipWithinDays({7, 2, 5, 10, 8}, 2) printed 18 ([7, 2, 5] | [10, 8]).
- Book allocation:
nbooks with page counts in order,mstudents, each gets a contiguous block; minimise the maximum pages any student reads.
Solution
Same recipe again. For pages {12, 34, 67, 90} and 2 students the program printed 113 (12 + 34 + 67 | 90).
- Why is "take the earliest seat" safe in the cows check?
Solution
Exchange argument: take any valid seating. Move its first student to the first seat; gaps only grow. Then move each next student to the earliest seat at least d from the previous one; this seat is at or before theirs, so the remaining students have at least as much room. So if any seating works, the greedy one does too.
Quick quiz
What does minSpeed(new int[]{10, 10}, 4) return?
- 5
- 10
- 4
- 3
Answer
5. At k = 5 each pile takes 2 hours, 4 in total: fits. At k = 4 each pile takes 3 hours, 6 in total: too many. The first yes is 5.
Interview questions
- When can you binary search on the answer? When the answer is a number in a known range and a yes/no check on a candidate is monotonic.
- How do you choose
loandhi? The smallest and largest answers that make sense: speed 1 tomax(pile); capacitymax(weight)tosum(weights). - First yes or last yes? "Smallest that works" is the first yes (
ok(mid) → hi = mid). "Largest that works" is the last yes: find the first no and subtract 1. - What is the complexity? O(cost of
ok× log(range)): O(n log max) for Koko. - Why
longfor the hours? At small speeds the total can reachn × 10⁹, far beyondint. - Why does the cows problem need sorting? The greedy check walks seats left to right and uses the first and last as the corridor's ends.
Glossary
| Term | Meaning |
|---|---|
| Search space | The set of values being searched; here the range of possible answers, not array indexes |
| Binary search on the answer | Binary searching that range with a yes/no check on each candidate |
Predicate ok(x) |
A function that answers yes or no for a candidate answer x |
| Monotonic | Changes from no to yes (or yes to no) only once as x grows |
| Lower bound | The first position where the condition becomes true (episode 12) |
| Ceiling division | ⌈x / k⌉, division rounded up; in integers (x + k - 1) / k |
| Greedy | Making the best local choice at each step (earliest seat) without going back |
| Minimise the maximum / maximise the minimum | Typical wording of binary-search-on-the-answer problems |
ArithmeticException: / by zero |
Java's runtime error for integer division by zero |
| Integer overflow | A result bigger than the type's maximum (2,147,483,647 for int), which wraps to a wrong value |
| Time Limit Exceeded (TLE) | The program is too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
long |
Java's 64-bit integer, up to about 9.2 × 10¹⁸ |
Summary
- When the answer is a number in a range and "is
xgood enough?" is monotonic, binary search the answer. - Koko: first speed
kin[1, max]withhours(k) <= h, hours rounded up, totals inlong. - Exam seats / aggressive cows: sort, greedy
canSeat(d), answer = firstdthat fails, minus 1. - Start the range at the smallest valid answer (
lo = 0divided by zero). - O(n log range) instead of O(n × range): 30 checks instead of 5 × 10⁸.
Next episode: Median of Two Sorted Arrays (hard).