Aggressive Cows (Binary Search on Answer)

Problem Statement

Given stall positions and c cows, place the cows in stalls so the minimum distance between any two cows is as large as possible. Return that maximum possible minimum distance.

Example

Input:  stalls = [1,2,4,8,9], c = 3
Output: 3
Explanation: Place cows at 1, 4, 8 -> min gap 3.

Approach

Binary search on the answer (a distance d). The predicate "can we place all c cows at least d apart?" is monotone: easier for small d, harder for large. Check it greedily after sorting — place a cow, then the next only when the gap is >= d. Keep the largest feasible d.

Complexity

• Time: O(n log(maxPos - minPos)) after sorting
• Space: O(1)

Solution Code

Python

def aggressive_cows(stalls, c):
    stalls.sort()
    def can_place(d):
        count, last = 1, stalls[0]
        for s in stalls[1:]:
            if s - last >= d:
                count += 1
                last = s
        return count >= c
    lo, hi, best = 1, stalls[-1] - stalls[0], 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if can_place(mid):
            best = mid
            lo = mid + 1
        else:
            hi = mid - 1
    return best

Java

boolean canPlace(int[] stalls, int c, int d) {
    int count = 1, last = stalls[0];
    for (int i = 1; i < stalls.length; i++) {
        if (stalls[i] - last >= d) { count++; last = stalls[i]; }
    }
    return count >= c;
}
int aggressiveCows(int[] stalls, int c) {
    Arrays.sort(stalls);
    int lo = 1, hi = stalls[stalls.length - 1] - stalls[0], best = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(stalls, c, mid)) { best = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return best;
}

C++

bool canPlace(vector<int>& stalls, int c, int d) {
    int count = 1, last = stalls[0];
    for (int i = 1; i < (int)stalls.size(); i++) {
        if (stalls[i] - last >= d) { count++; last = stalls[i]; }
    }
    return count >= c;
}
int aggressiveCows(vector<int>& stalls, int c) {
    sort(stalls.begin(), stalls.end());
    int lo = 1, hi = stalls.back() - stalls.front(), best = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(stalls, c, mid)) { best = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return best;
}

Key Takeaways

• Maximising a minimum is a hallmark of "binary search on the answer".
• Sort first, then the greedy placement is the feasibility test.
• Reference: classic problem SPOJ AGGRCOW; see also GeeksforGeeks.