Aggressive Cows — Binary Search on Answer (SPOJ / GFG Classic)

Problem Statement#

You are given N stall positions along a number line and C cows. Place the cows in distinct stalls such that the minimum distance between any two cows is maximised. Return that maximum possible minimum distance.

This is the classic SPOJ AGGRCOW / GeeksforGeeks problem. The same logic appears as LC 2064 (Magnetic Force Between Two Balls) and LC 1552 (Magnetic Force Between Two Balls — exact same problem, renamed).

Constraints:

• 2 <= N <= 10^5
• 2 <= C <= N
• 0 <= stall[i] <= 10^9
• All stall positions are distinct

Example 1:

Input:  stalls = [1, 2, 4, 8, 9], C = 3
Output: 3
Explanation: Place cows at positions 1, 4, 9.
             Min distances: 4-1=3, 9-4=5 → minimum is 3.
             No placement achieves a minimum gap > 3.

Example 2:

Input:  stalls = [0, 3, 4, 7, 10, 9], C = 4
Output: 3
Explanation: Sort to [0,3,4,7,9,10].
             Place at 0, 3, 7, 10 → gaps 3, 4, 3 → min = 3.

Example 3:

Input:  stalls = [1, 2], C = 2
Output: 1
Explanation: Only two stalls, two cows — gap is always 1.

Why This Problem Matters#

Aggressive Cows is the canonical teaching example for binary search on the answer space, also called "parametric binary search." It appears by name in competitive programming curricula worldwide (SPOJ AGGRCOW has been solved over 50 000 times) and its logic is embedded in dozens of LeetCode hard problems.

The key shift in thinking: instead of binary searching within the input for a target value, you binary search over all possible answers and check whether a given answer is achievable. This pattern unlocks an entire category of optimisation problems that appear intractable until you realise the feasibility function is monotone.

In FAANG interviews, this pattern typically surfaces in the form of "minimise the maximum" or "maximise the minimum" problems. Interviewers expect you to recognise the monotonicity property, define the feasibility check, and write the correct upper-bound binary search template. Aggressive Cows is the fastest way to internalise all three.

The Core Insight#

Observation: If you can place all C cows with a minimum gap of d, then you can also place them with any gap smaller than d. Conversely, if a gap of d is impossible, then any gap larger than d is also impossible.

This monotone feasibility means: given a candidate minimum distance mid, just greedily place cows one by one, always choosing the next stall at least mid away from the last placed cow. If you can place all C cows, then mid is feasible; otherwise it is not.

Binary search on mid in the range [1, stalls[-1] - stalls[0]] and find the largest feasible value.

Template — maximise the minimum (upper-bound variant):

lo = 1,  hi = max_possible
while lo < hi:
    mid = lo + (hi - lo + 1) // 2   # bias toward right to avoid infinite loop
    if feasible(mid): lo = mid        # mid works, try larger
    else:             hi = mid - 1    # mid too large
return lo

The +1 bias in mid is critical: without it, when lo = hi - 1 and feasible(lo) is true, mid stays at lo forever.

Visual Dry Run#

Input: stalls = [1, 2, 4, 8, 9], C = 3

After sorting: [1, 2, 4, 8, 9] Search range: lo = 1, hi = 9 - 1 = 8

Common Mistakes#

1. Using mid = (lo + hi) // 2 in the upper-bound template. When lo = hi - 1 and feasible(lo) is true, mid computes to lo, the condition sets lo = mid = lo, and the loop never terminates. Always use lo + (hi - lo + 1) // 2 for the "maximise" variant.

2. Forgetting to sort the stalls. The greedy placement only works on a sorted array. Skipping the sort produces wrong answers silently.

3. Setting hi = len(stalls) - 1 instead of stalls[-1] - stalls[0]. The binary search is over distances, not indices. Using an index as the upper bound is a conceptual error.

4. Off-by-one in the feasibility check. The first cow is always placed at stalls[0]. Starting the count at 0 and then incrementing gives the wrong final count.

5. Using a minimise template for a maximise problem. The "minimise" template biases mid toward the left; the "maximise" template biases it toward the right. Mixing them produces incorrect boundary behavior.

6. Not handling the edge case where C == 1. With only one cow, any placement works and the answer is the full span. The algorithm handles this correctly if coded properly, but verify it.

Solutions#

Python#

def aggressiveCows(stalls: list[int], c: int) -> int:
    stalls.sort()                               # sort stalls — mandatory for greedy check
 
    def feasible(min_gap: int) -> bool:
        """Return True if we can place c cows with every gap >= min_gap."""
        count = 1                               # place first cow at the leftmost stall
        prev = stalls[0]                        # track position of last placed cow
 
        for stall in stalls[1:]:               # try each remaining stall in order
            if stall - prev >= min_gap:        # this stall is far enough from the last cow
                count += 1                     # place a cow here
                prev = stall                   # update last placed position
                if count == c:                 # early exit — all cows placed
                    return True
        return count >= c                      # did we place all c cows?
 
    lo = 1                                     # minimum possible gap is 1
    hi = stalls[-1] - stalls[0]               # maximum possible gap is full span
 
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2         # bias right: maximise-the-minimum template
        if feasible(mid):
            lo = mid                           # mid is achievable — try a larger gap
        else:
            hi = mid - 1                       # mid is too large — reduce upper bound
 
    return lo                                  # largest feasible minimum gap

JavaScript#

function aggressiveCows(stalls, c) {
    stalls.sort((a, b) => a - b);              // sort stalls numerically
 
    function feasible(minGap) {
        // Check if we can place c cows with every consecutive gap >= minGap
        let count = 1;                         // first cow at leftmost stall
        let prev = stalls[0];                  // position of last placed cow
 
        for (let i = 1; i < stalls.length; i++) {
            if (stalls[i] - prev >= minGap) {  // stall is far enough
                count++;                       // place cow
                prev = stalls[i];              // update last position
                if (count === c) return true;  // all cows placed — early exit
            }
        }
        return count >= c;                     // check if all c cows were placed
    }
 
    let lo = 1;                                // smallest possible gap
    let hi = stalls[stalls.length - 1] - stalls[0]; // largest possible gap
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo + 1) / 2); // bias right — maximise variant
        if (feasible(mid)) {
            lo = mid;                          // achievable — try larger
        } else {
            hi = mid - 1;                      // too large — shrink upper bound
        }
    }
 
    return lo;                                 // maximum achievable minimum gap
}

Complexity Analysis#

Follow-up Questions#

1. What changes if you want to minimise the maximum gap? Swap to the "minimise" template: mid = lo + (hi - lo) // 2, if feasible(mid): hi = mid else lo = mid + 1. This is the pattern for LC 1760 (Minimum Limit of Balls in a Bag).
2. LC 2064 Magnetic Force Between Two Balls is identical to this problem — same constraints, same code.
3. What if stalls have capacity limits (place multiple cows per stall)? The feasibility function changes; the binary search shell stays the same.
4. Can the binary search be over a continuous domain? Yes — replace integer binary search with a floating-point epsilon loop. Used in LC 786 (Kth Smallest Prime Fraction).

This Pattern Solves#

• SPOJ AGGRCOW / GFG Aggressive Cows (this problem)
• LC 2064 — Minimum Number of Days to Make m Bouquets
• LC 1552 / LC 2064 — Magnetic Force Between Two Balls
• LC 1011 — Capacity to Ship Packages Within D Days
• LC 410 — Split Array Largest Sum
• LC 875 — Koko Eating Bananas
• LC 1870 — Minimum Speed to Arrive on Time
• Any "maximise the minimum" or "minimise the maximum" optimisation problem with a greedy feasibility check

Key Takeaway#

Whenever you see "maximise the minimum" or "minimise the maximum," think binary search on the answer. Define a greedy feasibility function, verify it is monotone (once feasible at d, feasible at all d' < d), then apply the correct upper-bound template with the right-biased midpoint. The stall sorting + greedy placement pair is the canonical two-step for Aggressive Cows and its many disguised variants.

Key Takeaways#

• Aggressive Cows is the canonical "maximise the minimum" binary search on answer problem; its exact logic appears in LC 1552, LC 2064, and many competitive programming problems.
• Feasibility is monotone: if placing cows with a minimum gap of d is possible, then any gap d' < d is also possible — this monotonicity is the prerequisite for binary search.
• The greedy feasibility check: sort stalls, place the first cow at position 0, then each subsequent cow at the earliest stall at least gap away — O(n) per check.
• For maximisation, use the upper-mid formula lo + (hi - lo + 1) // 2 and set lo = mid on success — this prevents infinite loops when lo + 1 == hi.
• Search bounds: lo = 1 (smallest gap), hi = (stalls[-1] - stalls[0]) / (C - 1) (tightest upper bound assuming even spread).
• Sorting the stalls before any binary search or greedy reasoning is mandatory — without sorted positions, the gap calculations are meaningless.
• This template is reused verbatim for LC 1552 (Magnetic Force Between Two Balls), LC 2064 (Distributed Candies), and any "maximise minimum separation" problem.