Aggressive Cows
Mahabharata — The Maximum Safety Distance — Placing Warriors as Far Apart as Possible
शत्रुओं से दूर रखो — अधिकतम दूरी से। न्यूनतम दूरी को अधिकतम करो — यही कुशल व्यूह है॥
*Keep enemies far apart — with maximum distance. Maximize the minimum distance — that is the skillful formation.*
The Story
Given n stall positions and k cows, place all k cows in stalls such that the MINIMUM distance between any two cows is MAXIMIZED.
For `stalls=[1,2,4,8,9]`, k=3: place cows at positions 1, 4, 9. Min distance = min(3,5)=3. Answer=3.
**Binary search on answer (minimum distance):** - Sort stalls - Range of minimum distance: [1, stalls[n-1]-stalls[0]] - For each candidate minimum distance d: check if we can place k cows all at least d apart
**Feasibility check (greedy):** Place first cow at stalls[0]. For each subsequent cow: place at the first stall at least d away from the last placed cow. If we place all k cows → feasible.
```java Arrays.sort(stalls); int lo=1, hi=stalls[n-1]-stalls[0]; while (lo <= hi) { // Note: lo <= hi here, not lo < hi int mid = (lo+hi)/2; if (canPlace(stalls, k, mid)) lo=mid+1; // Feasible: try larger distance else hi=mid-1; // Infeasible: try smaller } return hi; // hi is the maximum feasible distance ```
**Note the direction!** In bs-11/12, we minimize (find min feasible k). Here we MAXIMIZE (find max feasible d). The loop condition flips: `lo <= hi` and we return `hi`.
Trace `[1,2,4,8,9]`, k=3: - Sort: [1,2,4,8,9]. lo=1, hi=8 - mid=4: canPlace(4)? 1,5→8? No, 8 is 7 from 1, try 1,_,8,_. Actually: 1,5(not in stalls),... Greedy: start at 1. Next ≥ 1+4=5: positions are [8,9] → 8. Next ≥ 8+4=12: none. Only 2 cows. Infeasible → hi=3 - mid=2: canPlace(2)? 1, ≥3:4, ≥6:8. 3 cows placed! Feasible → lo=3 - mid=3: canPlace(3)? 1, ≥4:4, ≥7:8. 3 cows! Feasible → lo=4 - lo=4>hi=3 → return hi=3 ✓
The Exhaustive Placement Checker
Try every possible minimum distance from largest to smallest. Return the first feasible one. O(n² log n).
int solveBruteForce(int n, int k, int[] stalls) {
Arrays.sort(stalls);
for (int d = stalls[n-1]-stalls[0]; d >= 1; d--)
if (canPlace(stalls, k, d)) return d;
return -1;
}The Maximum-Minimum Binary Search Wisdom
int solve(int n, int k, int[] stalls) {
Arrays.sort(stalls);
int lo = 1, hi = stalls[n-1] - stalls[0];
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
int count = 1, last = stalls[0];
for (int i = 1; i < n; i++) {
if (stalls[i] - last >= mid) { count++; last = stalls[i]; }
}
if (count >= k) lo = mid + 1; // Feasible: maximize
else hi = mid - 1; // Infeasible: reduce
}
return hi;
}Step-by-Step Walkthrough
[1,2], k=2 Sort: [1,2]. lo=1,hi=1. mid=1: place at 1,2 (2-1=1>=1) → 2 cows ✓ → lo=2. lo=2>hi=1 → return hi=1 ✅
Deep Insight
**MAXIMIZE vs MINIMIZE direction:** - bs-11 (minimize k): feasible → hi=mid (try smaller); return lo - bs-13 (maximize d): feasible → lo=mid+1 (try larger); return hi
The loop terminates when lo > hi. In the maximize case: - lo-1 = last value where lo was set = last feasible mid - hi = last value where hi was not decremented past = correct answer
**Why sort stalls?** The greedy placement (place next cow as soon as gap ≥ d) only works on a sorted array.
**Book Allocation, Split Array, Ship Packages** are all the same bs-11 minimize pattern. Aggressive Cows uniquely uses the maximize pattern.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n² log n) | O(1) | Try each distance |
| Optimal | O(n log n) | O(1) | O(n log n) sort + O(n log(max-min)) binary search |
Pattern Recognition
✅ Maximize the minimum distance — binary search on answer ✅ Sort first; greedy feasibility check ✅ Feasible: lo=mid+1 (try larger); return hi ✅ Contrast with bs-11: minimize → hi=mid; return lo **LeetCode Trigger Phrases:** → "aggressive cows" / "maximum minimum distance" → "place k elements with maximum gap" → Maximize-minimum optimization
Bhagavad Gita 6.16
नात्यश्नतस्तु योगोऽस्ति न चैकान्तमनश्नतः। न चाति स्वप्नशीलस्य जाग्रतो नैव चार्जुन॥
Yoga is not for one who eats too much or too little, nor for one who sleeps too much or keeps too little vigil, O Arjuna.
Connection: The problem seeks the maximum minimum distance — not too close (leading to conflict), not unnecessarily spread (wasting space). Like the Gita's principle of moderation that maximizes the quality of practice, the aggressive cows problem maximizes the minimum separation. Binary search finds this optimal balance point where the least separation is as great as possible — true dharmic equilibrium.