Aggressive Cows
Hard · Binary Search · Array · Binary Search · Greedy · Sorting
Problem
A barn has n stalls along a straight line, at the distinct positions given in stalls (not necessarily sorted). You must house k cows, one cow per stall. The cows fight when they stand close together.
Choose k of the stalls so that the smallest distance between any two chosen stalls is as large as possible. Return that largest possible minimum distance.
Examples
Input: stalls = [1,2,4,8,9], k = 3 Output: 3
Stalls 1, 4 and 8 (or 9) keep every pair at least 3 apart. Distance 4 cannot fit three cows.
Input: stalls = [10,1,5,7], k = 2 Output: 9
Put the two cows in the farthest stalls, 1 and 10.
Input: stalls = [0,3,6,9], k = 4 Output: 3
All four stalls are needed, and neighbors are 3 apart.
Constraints
- 2 <= n == len(stalls) <= 10^5
- 0 <= stalls[i] <= 10^9
- All stall positions are distinct
- 2 <= k <= n
Approaches
- Baseline: try every pairwise distance — time O(n³) in the worst case, space O(n²)
Follow-up
The pattern is "maximize the minimum": a monotone yes-or-no test plus a binary search over the answer. The use cases ask the test on its own (most cows for a given gap) and the mirror question, shrinking the widest gap by adding stations.
Related problems
Start free on Cariara · Coding problems · System design studio
