☕ DSA Java Articles

Topics › Binary Search › BS on Answers

Aggressive Cows

Hard TUF ID 73 A2ZSDE

Java source ↗ Edit this article ↗

Problem

A farmer has n stalls at positions stalls[0..n-1] along a straight line (not necessarily sorted) and cows aggressive cows. Each cow must be placed in a different stall. To stop them fighting, the farmer wants the minimum distance between any two cows to be as large as possible. Return that largest possible minimum distance.

This is the classic SPOJ problem AGGRCOW; LeetCode’s “Magnetic Force Between Two Balls” is the same problem with balls and baskets.

Constraints: 2 ≤ cows ≤ n ≤ 10^5, 0 ≤ stalls[i] ≤ 10^9, all positions distinct.

Example 1

stalls = [0, 3, 4, 7, 10, 9], cows = 4
answer = 3          // place cows at 0, 3, 7, 10: the closest pair is 3 apart; no placement achieves 4

Example 2

stalls = [4, 2, 1, 3, 6], cows = 2
answer = 5          // two cows go to the extreme stalls 1 and 6

The feasibility check

Fix a candidate distance dist and ask: can all cows be placed so that every pair is at least dist apart? Sort the stalls first. Then greedily put the first cow in the leftmost stall and every subsequent cow in the leftmost stall that is at least dist away from the previously placed cow. Count how many cows fit. Greedy is optimal because placing a cow as far left as legally possible leaves the most room for the remaining cows; any valid placement can be shifted left stall by stall into the greedy one without reducing the count.

static boolean canPlace(int[] stalls, int cows, int dist) {
    int count = 1, last = stalls[0];
    for (int i = 1; i < stalls.length; i++) {
        if (stalls[i] - last >= dist) {
            count++;
            last = stalls[i];
        }
    }
    return count >= cows;
}

O(n) per call, assuming stalls is already sorted.

Approach 1: Brute force, try every distance

Intuition. The answer is at least 1 (positions are distinct integers) and at most max - min (the two extreme stalls). If the cows can be placed with minimum distance d, they can certainly be placed with minimum distance d - 1 (the same placement still works), so feasibility is true for small d and becomes false at some point and stays false. The brute force walks d = 1, 2, 3, ... and stops at the first infeasible value; the previous one is the answer.

Algorithm.

  1. Copy and sort the stalls.
  2. For d = 1, 2, ..., max - min: if canPlace(sorted, cows, d), remember d; otherwise stop.
  3. Return the last feasible d.
static int bruteForce(int[] stalls, int cows) {
    int[] a = stalls.clone();
    Arrays.sort(a);
    int n = a.length;
    int best = 0;
    for (int d = 1; d <= a[n - 1] - a[0]; d++) {
        if (canPlace(a, cows, d)) best = d;
        else break;
    }
    return best;
}

Complexity. Time O(n log n + n * answer): sorting plus one O(n) scan per distance up to the answer, which can be about 10^9. Space O(n) for the sorted copy.

Approach 2: Optimal, binary search on the distance

Intuition. The feasibility pattern over d = 1, ..., max - min is T T T ... T F F F. Unlike the minimisation problems in this section, we want the last T, because we are maximising. The binary search is the mirror image: when mid is feasible, record it and look for a bigger distance (lo = mid + 1); when it is infeasible, every larger distance is also infeasible, so look smaller (hi = mid - 1).

Algorithm.

  1. Copy and sort the stalls.
  2. Set lo = 1, hi = max - min, ans = 0.
  3. While lo ≤ hi:
    • mid = lo + (hi - lo) / 2.
    • If canPlace(sorted, cows, mid): ans = mid, lo = mid + 1.
    • Else: hi = mid - 1.
  4. Return ans.
static int optimal(int[] stalls, int cows) {
    int[] a = stalls.clone();
    Arrays.sort(a);
    int n = a.length;
    int lo = 1, hi = a[n - 1] - a[0], ans = 0;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(a, cows, mid)) { ans = mid; lo = mid + 1; }
        else hi = mid - 1;
    }
    return ans;
}

Dry run on stalls = [0, 3, 4, 7, 10, 9], cows = 4. Sorted: [0, 3, 4, 7, 9, 10], hi = 10.

lo hi mid greedy placement cows placed feasible? ans next
1 10 5 0, 7 2 no 0 [1, 4]
1 4 2 0, 3, 7, 9 4 yes 2 [3, 4]
3 4 3 0, 3, 7, 10 4 yes 3 [4, 4]
4 4 4 0, 4, 9 3 no 3 [4, 3] stop

Result 3.

Complexity. Time O(n log n + n log(max - min)): the sort dominates for small coordinate ranges; the search itself is about 30 scans of the array. Space O(n) for the sorted copy (or O(1) extra if sorting in place is allowed).

Minimise versus maximise

Compare this with Koko eating bananas or the book allocation problem. There the predicate is F ... F T ... T and a feasible mid moves hi left. Here it is T ... T F ... F and a feasible mid moves lo right. Everything else, the ans variable, the loop condition, the midpoint formula, is unchanged. A reliable way to remember the direction: after recording a feasible candidate, move towards the side where you would like to find an even better candidate. For a maximum that side is the right, for a minimum it is the left.

Edge cases and pitfalls