Aggressive Cows
Aggressive Cows is a classic GFG problem, also on SPOJ as AGGRCOW; it is not on LeetCode. You are given the positions of n stalls on a straight line (distinct, in no particular order) and a number of cows k.
Place all k cows in different stalls so that the smallest distance between any two cows is as large as possible, and return that distance. In short: maximize the minimum distance.
- 2 <= n <= 10⁵
- 2 <= k <= n
- 0 <= stalls[i] <= 10⁹
Intuition
Trying every way to place the cows is far too slow. Flip the question around: instead of finding the best distance, check a distance. Asking "can k cows be placed at least d apart?" is easy, because placing each cow as early as possible is always safe.
The check is also monotone: if d works, every smaller distance works; if it fails, every larger one fails. So the answers read yes yes yes ... no no no, and a pattern that flips once is exactly what binary search on the answer finds. To maximize the minimum distance, search for the last yes.
"Maximise the minimum" (or "minimise the maximum") plus a quick way to check one candidate answer. That is binary search on the answer: the search space is the answer's range, not the input array. The same template solves Koko Eating Bananas, Capacity to Ship Packages and Allocate Minimum Pages.
Approach
Before reading on, take stalls [1, 2, 4, 8, 9] and k = 3. Can every gap be at least 4? At least 3? What does the yes/no pattern look like as the distance grows?
Sort the stalls
Sort stalls first, at O(n log n). Cows are placed by walking left to right, and the gap between neighbouring cows only means something when the stalls are in order; the input usually is not.
Write the greedy check
fits(d): put a cow in stalls[0]; walk right and place the next cow in the first stall with s - last >= d. Return count >= k. Taking the earliest possible stall leaves the most room for the cows that follow, so if greedy fails, no placement succeeds.
Binary search the distance
- Set
lo = 1andhi = stalls[-1] - stalls[0], the smallest and largest gaps possible. - Take
mid = (lo + hi) // 2. - If
fits(mid), recordbest = midand try larger withlo = mid + 1. - Otherwise try smaller with
hi = mid - 1.
Recording best on every success means the loop never has to land exactly on the answer.
Return the last distance that fit
When lo > hi, best holds the largest distance that passed the check. Every value above it failed, and because the check is monotone, no larger distance can work. The aggressive cows solution costs the sort plus O(n log(range)) for the search.
Aggressive Cows solution in Python | C++ | Java
hi = 3.lo = 3.lo = 4.hi = 4.lo = 3.lo = 4.lo = 5.hi = 11.hi = 5.hi = 2.lo = 2.hi = 1.Common pitfalls
Forgetting to sort the stalls
def aggressiveCows(self, stalls, k):
lo, hi = 1, max(stalls) - min(stalls)def aggressiveCows(self, stalls, k):
stalls.sort()
lo, hi = 1, stalls[-1] - stalls[0]The greedy check walks left to right and compares each stall with the previous cow. On unsorted input like [10, 1, 2, 7, 5] it measures meaningless distances and returns a wrong answer.
Returning lo or mid instead of the last success
while lo <= hi:
mid = (lo + hi) // 2
if fits(mid):
lo = mid + 1
else:
hi = mid - 1
return loif fits(mid):
best, lo = mid, mid + 1
...
return best # equivalently hiWhen the loop ends, lo is one past the answer. Keep best (or return hi) so the value returned is one that actually passed the check.
Requiring exactly k cows in the check
return count == k
return count >= k
Greedy keeps placing cows as long as stalls allow. For [1, 2, 4, 8, 9], k = 3 and d = 1 it places 5 cows; with == k that small, obviously feasible distance is rejected and the search heads the wrong way.
Edge cases
The two cows go in the end stalls, so the answer is max - min. That is also why the search's upper bound starts there.
Every stall gets a cow, so the answer is the smallest gap between neighbouring stalls.
Positions up to 10^9 need only about 30 checks. C++ and Java compute lo + (hi - lo) / 2 so mid cannot overflow.
Complexity
Binary search on the answer: same template, different check
Each of these searches a range of possible answers and checks one candidate with a greedy pass.
| Problem | Search over | Check for a candidate | Keep |
|---|---|---|---|
| Aggressive Cows | minimum distance d | greedy places >= k cows at gap d | largest that fits |
| Koko Eating Bananas (875) | eating speed | total hours <= h | smallest that fits |
| Capacity to Ship Packages (1011) | ship capacity | days needed <= D | smallest that fits |
| Allocate Minimum Pages | max pages per student | students needed <= m | smallest that fits |
Aggressive Cows FAQ
What is the aggressive cows problem?
Given stall positions on a line and k cows, place the cows in stalls so that the smallest distance between any two cows is as large as possible, and return that distance. For stalls [1, 2, 4, 8, 9] and k = 3 the answer is 3 (cows at 1, 4 and 8).
What are the steps to solve aggressive cows?
- Sort the stalls.
- Check(d): place a cow at the first stall, then at each first stall at least d from the last cow; succeed if k cows fit.
- Monotone: if d fits, every smaller d fits.
- Binary search d in
[1, max - min]: on success record d and go right, on failure go left. - Answer: the largest d that fit.
- Complexity: O(n log n + n log R) time, O(1) extra space.
- Example:
[1, 2, 4, 8, 9], k = 3 gives 3.
Why does binary search work for aggressive cows?
Feasibility is monotone in d. If cows can be placed with every gap at least d, the same placement also has every gap at least d - 1. So the set of feasible distances is a prefix 1..answer, and binary search finds its end in O(log R) checks.
Why is the greedy placement correct?
Putting each cow in the earliest stall that respects the gap leaves the most space to its right for the remaining cows. Any valid placement can be shifted left to match greedy without breaking a gap, so if greedy fits fewer than k cows, no placement fits k.
Is aggressive cows on LeetCode?
Not under that name; it comes from SPOJ (AGGRCOW) and GeeksforGeeks. LeetCode's Magnetic Force Between Two Balls (1552) is the same problem with balls and baskets.