Aggressive cows

The problem, simply

A barn has n stalls in one long row. You get the position of each stall, like house numbers on a street. You also get c cows. The cows are grumpy and kick each other when they stand close.

Put every cow in its own stall. Look at the two cows that ended up closest together. Make that smallest gap as big as you can, and give back that gap.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every gap, starting at 1 and going up. For each gap, check if all cows fit. The first gap that fails means every bigger gap fails too, so the gap just before it is the answer.

To check one gap, use the sleeping bag trick:

1. Sort the stalls.
2. Put the first cow in the first stall.
3. Walk right. Put the next cow in the first stall that is at least gap away from the last cow.
4. If you placed all c cows, the gap works.

Putting each cow as far left as allowed is never worse, because it leaves the most room for the cows after it.

import java.util.*;

class Solution {
    // Can all cows stand at least gap apart?
    boolean canPlace(int[] stalls, int cows, int gap) {
        int placed = 1, last = stalls[0];       // first cow in the first stall
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - last >= gap) {      // far enough from the last cow
                placed++;
                last = stalls[i];
                if (placed == cows) return true;
            }
        }
        return placed >= cows;
    }

    public int aggressiveCows(int[] stalls, int cows) {
        Arrays.sort(stalls);
        int most = stalls[stalls.length - 1] - stalls[0];
        int best = 0;
        for (int gap = 1; gap <= most; gap++) {
            if (canPlace(stalls, cows, gap)) best = gap;
            else break;                         // bigger gaps fail too
        }
        return best;
    }
}

How long it takes: sorting is O(n log n). Then each gap costs one walk of n stalls, and there can be max - min gaps to try. Stalls can be a billion apart, so O(n * (max - min)) is far too slow. Extra room: O(1).

Way 2: the clever way

The answers line up like a row of switches: small gaps all say yes, big gaps all say no. Somewhere there is a last yes. Finding the edge between yes and no in a sorted row is the job of binary search, so do binary search on the answer instead of on the stalls.

1. Sort the stalls. Let lo = 1 and hi = max - min.
2. Take the middle gap mid. Run the sleeping bag check.
3. If it works, remember mid and look bigger: lo = mid + 1.
4. If it fails, look smaller: hi = mid - 1.
5. When lo passes hi, the remembered gap is the answer.

The bottom row in the animation is the list of gaps we could answer. Gaps marked rejected are too big. Gaps marked done are known to work.

import java.util.*;

class Solution {
    boolean canPlace(int[] stalls, int cows, int gap) {
        int placed = 1, last = stalls[0];
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - last >= gap) {
                placed++;
                last = stalls[i];
                if (placed == cows) return true;
            }
        }
        return placed >= cows;
    }

    public int aggressiveCows(int[] stalls, int cows) {
        Arrays.sort(stalls);
        int lo = 1, hi = stalls[stalls.length - 1] - stalls[0];
        int best = 0;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;   // no overflow
            if (canPlace(stalls, cows, mid)) {
                best = mid;                 // it works, try a bigger gap
                lo = mid + 1;
            } else {
                hi = mid - 1;               // too big, try a smaller gap
            }
        }
        return best;
    }
}

How long it takes: sorting is O(n log n). The guessing game halves the range each time, so it makes about log(max - min) guesses (about 30 for a billion), and each guess walks the stalls once: O(n log(max - min)). Extra room: O(1) besides the sort.

Watch out for

• Moving the wrong pointer. Here a working gap means "try bigger", so lo moves. In "minimize the biggest" problems like book allocation it is the other way round.
• Writing (lo + hi) / 2 with positions near two billion can overflow. Use lo + (hi - lo) / 2.
• Starting lo at 0 is harmless but pointless: a gap of 0 always works.
• Returning lo instead of the remembered answer. With this loop, the answer is best (which equals hi at the end).

What interviewers ask next

• Why is the greedy check correct? Any working layout can slide its first cow to the first stall, then its second cow left to the first far enough stall, and so on, without breaking any gap. So if any layout works, the greedy one works.
• Can you shrink the search range? Yes. With c cows there are c - 1 gaps that add up to at most max - min, so hi = (max - min) / (c - 1).
• Same idea, different story: LeetCode "Magnetic Force Between Two Balls" is this exact problem.
• What if positions are real numbers? Binary search on a double for a fixed number of rounds (say 100), or until hi - lo is tiny.
• How do you spot this pattern? The words "maximize the minimum" or "minimize the maximum", plus a yes or no check that flips only once as the answer grows.

Remember this

Grown-up words: the guessing game is binary search on the answer, the yes then no row is a monotonic predicate, the sleeping bag trick is a greedy feasibility check, and the smallest gap we push up is the max-min distance.