Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
You are not searching the array — you are searching the answer. Binary search on the candidate minimum distance d; for each d a greedy left-to-right placement checks feasibility in O(n). Because 'can I place all cows at least d apart?' is monotonic (true for small d, false for large d), binary search finds the largest feasible d in O(n log(maxPos)).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize that the search space is the answer (a distance) rather than the input array, and whether you can prove the feasibility predicate is monotonic before you write the binary search.
Where candidates slip
Binary-searching over array indices instead of over the distance value, forgetting to sort the stalls, or moving the wrong pointer on a feasible mid (going left when you should go right because you're maximizing).
How to stand out
Say out loud: 'feasible(d) is monotone decreasing, so I binary-search for the boundary'. Then state that greedy-leftmost placement is optimal for the feasibility count, and give the O(n log(maxPos)) bound.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMaximize the minimum distance between cowsIs feasible(d) monotonic in d?YesNoExplore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Linear Scan Over the Answer — Baseline
1Hint 1Explore hintHide hint
The answer is some distance d between 1 and (largest stall − smallest stall). What if you just tried every d and kept the largest one that works?
2Hint 2Explore hintHide hint
For a fixed d, can you place the cows greedily and count how many fit? Plant the first cow at the leftmost stall, then each next cow at the first stall at least d away.
3Hint 3Explore hintHide hint
Walk d from 1 upward. The moment a d becomes infeasible, every larger d is also infeasible — so you can stop. But d can be up to 10⁹, so the scan itself is the bottleneck.
A · Core idea
Lock onto the key reframing immediately: the thing you are searching for is a distance, and that distance lives in the range [1, stalls[last] − stalls[0]]. The most direct algorithm simply tries every value in that range.
The feasibility check is the heart of the problem. For a fixed target gap d, ask: can I seat all `c` cows so that consecutive cows are at least `d` apart? Plant the first cow at the leftmost stall. Then sweep rightward; whenever you reach a stall that is at least d past the last cow you planted, seat a cow there and move your 'last placed' marker. Count how many cows you managed to seat. If that count reaches c, distance d is feasible.
Why greedy-leftmost is optimal for the count. Pushing each cow as far left as legally allowed leaves the maximum room on the right for the cows still to come. Any other valid placement of the same cow sits at the same spot or further right, which can only reduce the room remaining — so greedy seats at least as many cows as any other strategy. That makes the greedy count an exact yes/no answer to feasibility, not an approximation.
Why the scan can stop early. If gap d is feasible then gap d − 1 is feasible too (loosening the requirement never removes a valid arrangement). Equivalently, once some d fails, every larger d fails. So you can break at the first failure — but that doesn't save you in the worst case, because the feasible region can stretch nearly to maxPos.
Why we don't ship this. With stalls[i] up to 10⁹, the candidate range is enormous. Running an O(n) check up to a billion times is far outside any time limit. The fix is to exploit the exact monotonicity we just proved and binary-search the boundary instead of walking to it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
stalls = [1, 2, 4, 8, 9], c = 3Array state
seat cow 1
plant first cow at stalls[0] = 1
3C · Code with teaching comments
Reference implementation previewpublic int aggressiveCows(int[] stalls, int c) { Arrays.sort(stalls); int maxDist = stalls[stalls.length - 1] - stalls[0]; int best = 0; for (int d = 1; d <= maxDist; d++) {Explore the full codeHide the full code
D · Why it works and complexityO(n · maxPos) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The early-break observation ('once infeasible, always infeasible') is the proof that feasible(d) is monotonic — and monotonicity is precisely the precondition that lets you replace a linear scan with a binary search. Recognising that is the whole leap from this baseline to the optimal solution.
ComplexityO(n · maxPos) time, O(1) space — For each candidate distance (up to maxPos ≈ 10⁹) you run an O(n) greedy placement. That's O(n · maxPos) — fine for tiny coordinate ranges, hopeless for the stated constraints.
E · Edge cases and pitfalls3Forgetting to sort — greedy placement then counts garbage.Explore edge casesHide edge cases
Pitfalls
- Forgetting to sort — greedy placement then counts garbage.
- Letting d run to maxPos = 10⁹ — the scan itself times out.
- Counting cows but never comparing against c — the check must return a clean boolean.
Approach 2 of 2 · Optimal
Binary Search on the Distance (Optimal)
1Hint 1Explore hintHide hint
You proved feasible(d) flips from true to false exactly once as d grows. What algorithm finds that flip point in logarithmic time?
2Hint 2Explore hintHide hint
Binary-search the distance in [1, stalls[last] − stalls[0]]. At each mid, run the same O(n) greedy check. If mid is feasible, the answer is at least mid — try larger. If not, try smaller.
3Hint 3Explore hintHide hint
Because you are maximizing, record mid as a candidate answer on the feasible branch and move lo = mid + 1; on the infeasible branch move hi = mid - 1. Return the last feasible mid you saw.
A · Core idea
This is the textbook 'binary search on the answer'. We never binary-search the array itself — we binary-search the space of possible answers, which here is the integer distance range [1, stalls[last] − stalls[0]].
The monotonic predicate, stated precisely. Define feasible(d) = true if all c cows can be seated with every consecutive pair at least d apart. We proved in the baseline that if feasible(d) holds then feasible(d − 1) holds too. So as d increases from 1, the predicate is a run of trues followed by a run of falses — [T, T, T, …, T, F, F, …, F]. There is exactly one boundary, and the answer is the largest `d` that is still true. That single-flip shape is the only thing binary search needs.
The feasibility check is unchanged. canPlace(d) does the same greedy-leftmost sweep as the baseline: seat the first cow at stalls[0], then seat each subsequent cow at the first stall whose distance from the last placed cow is ≥ d. If it seats c cows, d is feasible. This is the check that makes binary-search-on-the-answer work — without a cheap monotone predicate, the technique doesn't apply.
Driving the search toward the largest true. Start lo = 1, hi = stalls[last] − stalls[0]. Compute mid = lo + (hi − lo) / 2. If canPlace(mid) is true, mid is achievable, but a bigger gap might be too — so record ans = mid and search the upper half with lo = mid + 1. If it's false, mid is too greedy — search the lower half with hi = mid − 1. When lo > hi, ans holds the largest feasible distance.
Why the off-by-one traps bite here. Three classic mistakes: (1) writing mid = (lo + hi) / 2, which can overflow when positions approach 10⁹ — use lo + (hi − lo) / 2. (2) Updating ans on the wrong branch, so you return a distance that doesn't actually fit all cows. (3) Moving lo/hi the wrong way because you confused 'maximize' with 'minimize' — on a feasible mid you must go right, since you want the biggest gap that still works. Say the invariant aloud — 'ans always holds a proven-feasible distance' — and these vanish.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
stalls = [1, 2, 4, 8, 9], c = 3Array state
lo=1, hi=8
mid=4 infeasible → hi=3
3C · Code with teaching comments
D · Why it works and complexityO(n log(maxPos)) timeO(1) spaceOpen the invariant and proofExplore the proofHide the proof
The leap from baseline to optimal is entirely about the predicate's shape. The baseline walks the [T…T,F…F] array one cell at a time; binary search jumps to the T/F boundary in log steps. Any 'maximize the minimum' or 'minimize the maximum' problem with a cheap monotone check reduces to exactly this skeleton — the only thing that changes between Aggressive Cows, Allocate Pages, and Koko is what canPlace/canFinish computes.
ComplexityO(n log(maxPos)) time, O(1) space — The distance range has size maxPos, so binary search does O(log(maxPos)) iterations. Each iteration runs the O(n) greedy feasibility check. Total O(n log(maxPos)); sorting adds O(n log n). Space is O(1) beyond the input.
E · Edge cases and pitfalls6stalls = [1, 1000000000], c = 2 — lo=1, hi=999999999; only seating both cows works → answer is the full span 999999999. Confirms the overflow-safe midpoint matters.Explore edge casesHide edge cases
Edge cases handled
stalls = [1, 1000000000], c = 2lo=1, hi=999999999; only seating both cows works → answer is the full span 999999999. Confirms the overflow-safe midpoint matters.stalls = [4, 2, 1, 3, 6], c = 5All five cows must be placed → minimum gap is the smallest consecutive gap after sorting [1,2,3,4,6], which is 1. canPlace(1) is the tightest feasible distance.
Pitfalls
- Using mid = (lo + hi) / 2 — overflows when positions approach 10⁹.
- Updating ans on the infeasible branch — returns a gap that doesn't fit all cows.
- Going left on a feasible mid — that minimizes instead of maximizing.
- Binary-searching array indices instead of the distance value — the classic misread of the search space.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int aggressiveCows(int[] stalls, int c) { Arrays.sort(stalls); int lo = 1, hi = stalls[stalls.length - 1] - stalls[0], ans = 0; while (lo <= hi) { int mid = lo + (hi - lo) / 2;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Searching indices instead of the answer
The search space is the distance value in [1, span], not positions in the array. Binary-searching indices answers a different question entirely.
Explore the code comparisonHide the code comparison
Searching indices instead of the answer
The search space is the distance value in [1, span], not positions in the array. Binary-searching indices answers a different question entirely.
Don't write this
int lo = 0, hi = stalls.length - 1; // WRONG: these are indices
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (canPlace(stalls, c, mid)) lo = mid + 1; else hi = mid - 1;
}Write this instead
int lo = 1, hi = stalls[stalls.length - 1] - stalls[0]; // distances
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (canPlace(stalls, c, mid)) { ans = mid; lo = mid + 1; }
else hi = mid - 1;
}2Skipping the sort
Greedy-leftmost placement assumes positions increase. On unsorted input the gaps are meaningless and the count is wrong.
Explore the code comparisonHide the code comparison
Skipping the sort
Greedy-leftmost placement assumes positions increase. On unsorted input the gaps are meaningless and the count is wrong.
Don't write this
def aggressive_cows(self, stalls, c):
# forgot stalls.sort()
lo, hi = 1, max(stalls) - min(stalls)
...Write this instead
def aggressive_cows(self, stalls, c):
stalls.sort()
lo, hi = 1, stalls[-1] - stalls[0]
...3Wrong pointer move on a feasible mid
Because we maximize the minimum gap, a feasible mid means 'try bigger'. Going left here throws away the larger feasible distances and under-reports the answer.
Explore the code comparisonHide the code comparison
Wrong pointer move on a feasible mid
Because we maximize the minimum gap, a feasible mid means 'try bigger'. Going left here throws away the larger feasible distances and under-reports the answer.
Don't write this
if (canPlace(stalls, c, mid)) {
hi = mid - 1; // WRONG: shrinks away from larger valid gaps
}Write this instead
if (canPlace(stalls, c, mid)) {
ans = mid;
lo = mid + 1; // maximize → push toward bigger gaps
}Revise
Carry the pattern into the interview
Pattern to remember
Binary search on the answer + greedy feasibility check
Code pattern to memorize
sort(stalls)
lo, hi = 1, stalls[-1] - stalls[0]
while lo <= hi:
mid = lo + (hi - lo) // 2
if canPlace(mid): # greedy: place each cow at the first stall >= last + mid
ans = mid; lo = mid + 1 # feasible → try a BIGGER gap
else:
hi = mid - 1 # infeasible → shrink the gapRules to remember
- 1Sort the stalls first. Greedy placement only works on a sorted line — the whole feasibility argument assumes positions increase.
- 2The predicate is monotonic: if you can place all cows ≥ d apart, you can also place them ≥ (d−1) apart. We maximize, so on a feasible mid we go right (
lo = mid + 1) and remember it. - 3Feasibility is greedy: always plant the first cow at
stalls[0], then each next cow at the first stall whose gap from the last placed cow is ≥ d. Greedy-leftmost is provably optimal for counting how many fit. - 4Search bounds are on the distance, not the index:
lo = 1,hi = stalls[last] − stalls[0]. Off-by-one here means you scan impossible gaps or miss the true max. - 5Use
mid = lo + (hi - lo) / 2to avoid integer overflow, and updateansonly on the feasible branch so you never return an infeasible distance.
Use this pattern when
- The answer is a single number inside a known numeric range (a distance, a capacity, a speed, a time)
- You can write a cheap O(n) check 'is value X good enough?' that flips from true to false (or false to true) exactly once
- The problem says MAXIMIZE the minimum (or MINIMIZE the maximum) — the classic min-max signature
- Brute-forcing every candidate value is too slow but checking one value is fast
Choose another pattern when
- The check isn't monotonic — a value being good tells you nothing about neighbours → binary search on the answer is invalid
- You need the actual arrangement of every cow, not just the best gap → still feasible but track placements
- The range of answers is tiny → a plain linear scan over candidates is simpler and fast enough
- Positions can't be sorted or compared on a line → the greedy feasibility argument breaks
Interview takeaway
'Maximize the minimum' is the dead giveaway for binary search on the answer. Once you see that feasibility is monotonic in the answer, the hard optimization collapses into a sorted-array binary search wrapped around an O(n) greedy check — the same skeleton powers Allocate Pages, Painter's Partition, and Koko Eating Bananas.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Binary Search on the Answer. Trigger on 'maximize the minimum' / 'minimize the maximum' with a cheap monotone feasibility check. The same skeleton — sort, bound the answer range, binary-search with an O(n) greedy/scan predicate — solves Allocate Pages, Painter's Partition, Koko Eating Bananas, and Split Array Largest Sum.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Allocate Minimum PagesSame skeleton, but MINIMIZE the maximum pages per student — feasible(x) is monotone the other way.
- Painter's PartitionIdentical to allocate pages: minimize the time for k painters with contiguous boards.
- Koko Eating BananasBinary search the eating speed; feasible(speed) = can finish within h hours.
- Magnetic Force Between Two BallsComing soonLiterally Aggressive Cows reworded — maximize the minimum magnetic force.