DSA sheet · Binary Search · Binary search on answer (max of min)

Aggressive Cows

This is the classic "maximise the minimum distance" problem, and the teacher says it is asked a lot in interviews. We are given stall positions and k cows, and we must spread the cows out so that the two closest cows are as far apart as possible. She first builds a slow but simple solution that tries every possible gap one by one (the brute force), shows why it gives TLE, and then replaces that loop with binary search on the answer.

Why it matters: once you understand this page, Magnetic Force Between Two Balls is the same code, and the "minimise the maximum" problems (Allocate Pages, Split Array) are its mirror image. The skill you learn here is how to pick the answer range (low, high), write a yes/no check, and decide which half to keep.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every gap one by one
• Part B · Optimal: binary search on the gap
• Part C · Revision page

Part 0 · Before starting

Normal binary search in one paragraph

Binary search works on something sorted, or more generally on anything where a yes/no question changes its answer only once as you move from left to right. We keep two ends, low and high, look at the middle mid, and from that one look we can throw away half of what's left. Each step halves the search space, so about log₂(size) steps are enough.

How to compute mid, and why that form

mid = low + (high - low) // 2

Mathematically this equals (low + high) // 2. The teacher always writes the first form because in Java or C++, low + high can go past the biggest int (about 2.1 × 10⁹) when both are large, and the result becomes a wrong, negative number. high - low is always small enough, so the safe form never overflows. In Python, integers never overflow, so both forms are fine. We still write the safe form so the habit carries over to other languages.

The pattern: binary search on the answer

In normal binary search we search inside the array. In this pattern we search over all possible answers. Three things make it work:

1. The answer range. Find the smallest answer that could ever make sense (low) and the biggest (high). The real answer is somewhere on this number line.
2. A yes/no check. Write a function that takes one candidate answer and says "possible" or "not possible". It does not find the answer. It only tests one value.
3. Monotonic means the yes/no changes only once. On the number line, all the "yes" values sit on one side and all the "no" values on the other. That is exactly what binary search needs: look at mid, and you know which side the boundary is on.

How do we spot this pattern? A strong hint is that the answer is a number that is not taken from the array (here, a distance), and the question says "maximum of the minimum" or "minimum of the maximum".

Maximise the minimum vs minimise the maximum

Part A · Brute force: try every gap one by one

GeeksforGeeks · Aggressive Cows

1The question in simple words

You get an array stalls. Each number is the position of a stall on a straight line (like house numbers on a road). All positions are different. You also get k, the number of cows. The cows are aggressive: if two of them are close, they fight. So we want to put the k cows into k different stalls so that the smallest distance between any two cows is as large as possible. Return that largest possible smallest distance.

Example: stalls = [1, 2, 4, 8, 9], k = 3.

road:   1  2  .  4  .  .  .  8  9
good:   C        C           C         gaps 3 and 4 → smallest = 3
bad:    C  C     C                     gaps 1 and 2 → smallest = 1

Putting cows at 1, 4, 8 gives distances 3 and 4. The closest pair is 3 apart. You can't do better, so the answer is 3.

Putting them at 1, 2, 4 is allowed (all three fit), but the closest pair is only 1 apart. The question isn't "can they fit", it's "fit them as far apart as possible, and report the smallest distance". That's what "maximise the minimum" means: for one placement, take its minimum gap; across all placements, pick the largest of those minimums.

2What the constraints tell us

• Number of stalls up to 10⁶. So any check that walks over the stalls costs up to 10⁶ steps. We can afford it a few dozen times, but not millions of times.
• Positions up to 10⁸. That fits in a normal int. It also tells us the largest possible gap is about 10⁸, which matters when we count how many gaps the brute force tries.
• k from 2 to n. At least 2 cows, so there is always at least one distance to talk about. And k ≤ n, so all cows can always be placed somewhere. The answer always exists (no −1 case).
• Rule of thumb the teacher uses: more than about 10⁸ simple operations → TLE (Time Limit Exceeded).

3Intuition

Turn the question around. Instead of "where should the cows go?", ask: "if I insist on a minimum gap of g, can I still fit all k cows?" That question is easy to answer: walk along the road and drop a cow at the first stall that is at least g away from the previous cow.

Now try g = 1, 2, 3, … one by one. Small gaps are easy to satisfy. As g grows, it gets harder, and at some point the cows no longer fit. The biggest g that still works is our answer.

4Building the logic from examples

The teacher tries each gap on [1, 2, 4, 8, 9], k = 3

• gap 1: cow at 1. Stall 2 is 1 away, which is ≥ 1, so cow there. Stall 4 is 2 away from 2, so cow there. All 3 fit → yes.
• gap 2: cow at 1. Stall 2 is only 1 away → skip. Stall 4 is 3 away (≥ 2) → cow. Stall 8 is 4 away from 4 → cow. 3 cows → yes.
• gap 3: cow at 1. 2 is 1 away → skip. 4 is 3 away (exactly 3 is enough) → cow. 8 is 4 away → cow. 3 cows → yes.
• gap 4: cow at 1. 2 is 1 away → skip. 4 is 3 away → skip. 8 is 7 away → cow. 9 is only 1 away from 8 → skip. We ran out of stalls with only 2 cows → no.

Gaps 1, 2 and 3 all work. 4 doesn't. The question wants the largest working gap → 3.

The yes/no line over every possible gap

Notice the shape: all yes, then all no. It flips only once. That's no accident:

Choosing low: why start at 1?

A gap of 0 would mean two cows standing on the same stall, which isn't allowed (one cow per stall, and all positions are different). So the smallest distance that can ever happen between two different stalls is at least 1. low = 1.

Choosing high: why last − first?

The teacher could have used the biggest value the constraints allow, but she wants the tightest range. Think of the easiest case, k = 2 (the minimum the constraints allow). With only two cows, you'd put one at the first stall and one at the last stall. The gap is then 9 − 1 = 8. With more cows, the closest pair can only get closer. So no answer can ever be bigger than last − first.

For 2 cows on our road: (1, 2) gives 1, (1, 4) gives 3, (1, 8) gives 7, (1, 9) gives 8. The corners win. high = stalls[-1] - stalls[0].

The check function: canPlace(stalls, k, gap)

• Put the first cow in the first stall. Start cows = 1 and remember its position in last = stalls[0].
• Walk from index 1 to the end. For each stall, compare with the most recent cow: if stalls[i] - last >= gap, there's enough room → place a cow (cows += 1) and move last to this stall.
• If the distance is smaller than gap, skip this stall and look at the next one.
• At the end: if cows >= k → yes. More than k is fine too (we can just leave the extras out).

Going from low to high: don't return on the first yes!

While writing the loop, the teacher stops and asks: if we go from gap 1 upward and return as soon as the check says yes, what happens? Gap 1 says yes right away, and we'd return 1. That's wrong, because 2 and 3 also work and we want the largest. So there are two correct ways:

• Low to high: on yes, save the gap in answer and keep going. Save 1, then 2, then 3. On the first no (gap 4), stop and return the saved 3. Since all bigger gaps are also no, there's no point continuing.
• High to low: try 8, 7, 6, 5, 4 → all no. 3 → yes. The first yes from the top is the largest, so return it immediately. No answer variable needed.

5Approach steps

1. Sort the stalls.
2. low = 1, high = stalls[-1] - stalls[0].
3. For each gap from low to high: if canPlace says yes, save it as the answer; otherwise stop.
4. Return the saved answer.

6Code (Python)

class Solution:
    def aggressiveCows(self, stalls, k):
        stalls.sort()
        low = 1
        high = stalls[-1] - stalls[0]
        answer = 0
        for gap in range(low, high + 1):
            if self.canPlace(stalls, k, gap):
                answer = gap        # works, but a bigger one might too
            else:
                break               # first "no": every bigger gap fails too
        return answer

    def canPlace(self, stalls, k, gap):
        cows = 1                    # first cow in the first stall
        last = stalls[0]            # position of the most recent cow
        for i in range(1, len(stalls)):
            if stalls[i] - last >= gap:
                cows += 1
                last = stalls[i]
        return cows >= k

class Solution:
    def aggressiveCows(self, stalls, k):
        stalls.sort()
        for gap in range(stalls[-1] - stalls[0], 0, -1):
            if self.canPlace(stalls, k, gap):
                return gap          # the first yes from the top is the largest
        return 1

    def canPlace(self, stalls, k, gap):
        cows, last = 1, stalls[0]
        for i in range(1, len(stalls)):
            if stalls[i] - last >= gap:
                cows += 1
                last = stalls[i]
        return cows >= k

7Code line by line

8Dry run (hand table)

stalls = [1, 2, 4, 8, 9], k = 3. low = 1, high = 8.

Return 3 ✓. (With gap 1 the walk places 5 cows, more than k. That still counts as yes.)

9Complexity & remember

• Time: sorting is O(n log n). Then up to (high − low) gaps, each with an O(n) check. In the worst case, high ≈ 10⁸ and n ≈ 10⁶, which is about 10⁸ × 10⁶ = 10¹⁴ steps. Far over 10⁸ → TLE.
• Space: O(1) extra (apart from what sorting uses).

Which loop can we shrink? The teacher's reasoning: the inner walk over the stalls can't be skipped, because we must look at each stall to decide whether a cow goes there. But the outer loop runs over the numbers 1, 2, 3, …, high, which are already sorted, and the yes/no answers flip only once. That is a perfect place for binary search.

Part B · Optimal: binary search on the gap

1The question

Same as Part A. Same low, same high, same canPlace. The only change: instead of walking the gaps one at a time, jump to the middle gap and throw away half the range each time.

2Constraints

Same as Part A. Now the outer part costs about log₂(10⁸) ≈ 27 checks instead of 10⁸.

3Intuition

The gaps 1 … high form a sorted number line, and the check gives Y Y Y … Y N N … N. We want the last Y. Pick the middle gap:

• If mid is yes: mid might be the answer, so save it. But a bigger gap might also work, and we want the biggest. So look right: low = mid + 1.
• If mid is no: mid is too big, and so is everything to its right. Look left: high = mid - 1.

4Building the logic

The answer range shrinking (stalls [1, 2, 4, 8, 9], k = 3)

5Approach steps

1. Sort the stalls. low = 1, high = stalls[-1] - stalls[0], answer = 0.
2. While low <= high: mid = low + (high - low) // 2.
3. If canPlace(stalls, k, mid): answer = mid, low = mid + 1.
4. Else: high = mid - 1.
5. Return answer.

6Code (Python)

class Solution:
    def aggressiveCows(self, stalls, k):
        stalls.sort()
        n = len(stalls)
        low = 1
        high = stalls[n - 1] - stalls[0]
        answer = 0
        while low <= high:
            mid = low + (high - low) // 2      # a candidate minimum gap
            if self.canPlace(stalls, k, mid):
                answer = mid                   # works: save it...
                low = mid + 1                  # ...and try a bigger gap
            else:
                high = mid - 1                 # too big: try smaller gaps
        return answer

    def canPlace(self, stalls, k, gap):
        cows = 1
        last = stalls[0]
        for i in range(1, len(stalls)):
            if stalls[i] - last >= gap:
                cows += 1
                last = stalls[i]
        return cows >= k

Optional speed-up: inside canPlace you can return True as soon as cows == k. It doesn't change the big-O, it just stops early.

7Code line by line

8Dry run (hand table)

stalls = [1, 2, 4, 8, 9] (already sorted), k = 3.

Only 3 checks instead of 4 here. With high = 10⁸, it's about 27 checks instead of 10⁸.

9Complexity & remember

• Time O(n log n + n · log(max − min)): sorting, plus about log₂(10⁸) ≈ 27 checks of O(n) each. Roughly 27 × 10⁶ ≈ 2.7 × 10⁷ steps. That's under 10⁸ → passes.
• Space O(1) extra (apart from sorting).

Part C · Revision page

s = Solution()
print(s.aggressiveCows([1, 2, 4, 8, 9], 3))     # 3
print(s.aggressiveCows([10, 1, 2, 7, 5], 3))    # 4  (cows at 1, 5, 10)
print(s.aggressiveCows([2, 12, 11, 3, 26, 7], 5))  # 1
print(s.aggressiveCows([0, 100000000], 2))      # 100000000

Based on this video: Aggressive Cows | Binary Search on Answer