There are stalls scattered along a straight barn, and arr[i] gives the position of the i-th stall. All positions are distinct, but they are not necessarily given in sorted order.
You have k cows, and they are aggressive — put two of them close together and they fight. Assign every cow to a different stall so that the minimum distance between any two cows is as large as possible.
Return that largest possible minimum distance.
max(arr) - min(arr) assume positions increase left to right.1 — positions are distinct integers, so any k stalls are at least 1 apart — and at most max(arr) - min(arr), achieved only when k = 2 with cows at the two extreme stalls.count == k the spacing d is proven feasible and the sweep can stop early.Input: arr = [1, 2, 4, 8, 9], k = 3 Output: 3 Place cows at stalls 1, 4, and 8. The gaps are 3 and 4, so the closest pair is 3 apart — no arrangement does better.
Input: arr = [10, 1, 2, 7, 5], k = 3 Output: 4 Place cows at stalls 1, 5, and 10 (note the input is unsorted). The gaps are 4 and 5, so the closest pair is 4 apart — the maximum possible.
- 2 <= arr.length <= 10^6 - 0 <= arr[i] <= 10^8 - 2 <= k <= arr.length - All stall positions are distinct
Aggressive Cows is the gateway problem for one of the most powerful ideas in interviews: when you cannot construct the best answer directly, binary search the answer itself. Master the template here and half a dozen famous problems fall to the exact same code shape.
In plain English: choose k of the given stall positions so that the smallest pairwise distance among the chosen ones is as large as it can be, and report that distance.
Formally: pick a subset S ⊆ arr with |S| = k maximizing min of |a - b| over all pairs a, b in S. Since only adjacent chosen stalls (in sorted order) can realize the minimum, this equals the minimum gap between consecutive chosen positions.
Worked example — arr = [1, 2, 4, 8, 9], k = 3
stalls: 1 2 4 8 9 try d = 3: cow at 1 → next stall ≥ 4 → cow at 4 → next ≥ 7 → cow at 8 ✓ 3 cows fit try d = 4: cow at 1 → next stall ≥ 5 → cow at 8 → next ≥ 12 → none ✗ only 2 fit largest feasible d = 3 → answer: 3
A senior candidate pins down the input guarantees and the extremes before writing a line of code — it takes thirty seconds and prevents the two most common bugs in this problem.
“Are the stall positions distinct, and can they arrive in any order?”
Distinct is guaranteed, sorted is not — the second example is unsorted. Forgetting to sort first silently breaks the greedy check.
“Is k always at most the number of stalls?”
Yes, 2 <= k <= arr.length, so every cow can always be assigned a stall and an answer always exists.
“What happens when k equals 2?”
The two cows go to the extreme stalls, so the answer is max(arr) - min(arr) — this is also the upper bound of the search space.
“What happens when k equals arr.length?”
Every stall is used, so the answer is the minimum adjacent gap in sorted order — the lower end of interesting answers.
“How large can the array and the positions be?”
Up to a million stalls at positions up to a hundred million. A linear scan over every candidate distance is hopeless; you need logarithmically many checks.
Before I start, I have a few clarifying questions.
Positions are distinct but arrive unsorted, so I will sort them first — is that acceptable?
I will sanity-check both extremes: k equals 2 gives the two end stalls, and k equals n forces every stall to be used.
With n up to a million and positions up to a hundred million, I am aiming for a solution that binary searches the answer rather than scanning every candidate distance.
Deciding whether some spacing d is achievable does not require trying all arrangements. Sort the stalls, put the first cow in the leftmost stall, then sweep right and drop a cow at the first stall at least d past the previous cow. If k cows fit, d is feasible. Shifting any cow further left never hurts the cows after it — it only leaves more room — so this greedy check is exact, not an approximation. It runs in O(n).
If the cows can be placed d apart, the very same arrangement also satisfies d - 1. So as d grows, the verdicts form an unbroken run of YES followed by an unbroken run of NO — and the answer is the last YES.
d: 1 2 3 4 5 ...
feasible: ✓ ✓ ✓ ✗ ✗
↑ answerThe candidate distances live in [1, max(arr) - min(arr)]. Test the middle d: on ✓ record it and search the right half for something bigger; on ✗ search the left half. That is O(log D) feasibility checks at O(n) each — the whole reason this pattern is called binary search on the answer: the array is never searched, the answer space is.
| Brute force | Optimal | |
|---|---|---|
| Idea | Test d = 1, 2, 3, … until it fails | Binary search on d |
| Time | O(n log n + n · D) | O(n log n + n log D) |
| Space | O(1) | O(1) |
Here D = max(arr) - min(arr) can reach 10^8 — the difference between the two columns is the difference between a hundred million checks and about twenty-seven. Full code for both lives in the Approaches selector below.
Key takeaway
When the answer is a number with monotone feasibility — if d works, every smaller d works — do not search arrangements. Binary search the answer and pair it with a cheap greedy feasibility check. Any problem that says maximize the minimum or minimize the maximum is waving this template at you: Koko Eating Bananas, Smallest Divisor, Split Array Largest Sum.
sort(arr)
lo = 1, hi = arr[n-1] - arr[0], best = 0
while lo <= hi:
mid = (lo + hi) / 2
if canPlace(mid): best = mid, lo = mid + 1 # feasible → try bigger
else: hi = mid - 1 # too ambitious → shrink
return best