Aggressive Cows Problem Optimal Binary Search Solution

Problem Statement❯

Given N stalls represented by their positions on a number line (sorted or unsorted), and K cows to place in these stalls, the goal is to place the cows such that the minimum distance between any two cows is as large as possible.

You must place exactly K cows in N stalls.
Each cow must be placed in a different stall.
The objective is to maximize the minimum distance between any two cows.

If the number of cows exceeds the number of stalls, it’s not possible to place all cows.

Examples❯

Stall Positions	No. of Cows (K)	Output	Description
[1, 2, 4, 8, 9]	3	3	We can place cows at positions 1, 4, and 8 — min distance = 3
[1, 2, 4, 8, 9]	2	8	Place cows at positions 1 and 9 — max possible distance
[5, 17, 100, 111]	2	106	Place cows at 5 and 111 — max min distance is 106
[5, 17, 100, 111]	4	6	All cows must be placed, closest pair ends up at 6 units apart
[10]	1	0	Only one cow, no distance to maximize
[10]	2	-1	Not enough stalls to place 2 cows
[]	2	-1	Empty array, no stalls available
[2, 4, 6]	0	0	Zero cows, so minimum distance is trivially zero

Visualization Player

Solution❯

The Aggressive Cows problem is a classic example where we want to use binary search on the answer. Instead of searching through positions, we ask: what is the largest possible minimum distance we can achieve between cows placed in stalls?

Understanding the Problem

We are given stall positions — say [1, 2, 4, 8, 9] — and asked to place K cows in them. The twist is: we want to maximize the minimum distance between any two cows. That means, the cows should be as far apart as possible, but we still need to fit all of them into the stalls.

Different Scenarios to Consider

Exact fit: If the number of cows equals the number of stalls, the only option is one cow per stall, and the smallest distance between any two is what we return.
Single cow: If there’s only one cow to place, we can put it anywhere. There’s no pair to measure distance, so the answer is 0.
Too many cows: If K > N, we cannot place all cows — so we return -1 or some invalid flag.
Empty stalls: If the stall list is empty, there’s no way to place any cows — again, return -1.

How the Strategy Works

First, we sort the stall positions to ensure they're in order. Then, we try to guess the minimum distance between cows (starting from 1 up to the max difference between stalls) using binary search.

At each step, we check: "Can we place all K cows such that the gap between any two is at least mid?"

If yes → maybe we can do even better, so try a bigger distance.
If no → that distance is too much, reduce the range.

We keep narrowing the range until we find the largest distance that works — that’s our answer.

Efficiency

This method is very efficient: we’re doing a binary search on distance (which ranges from 1 to max stall gap), and for each guess, we do a linear pass to see if placement is possible. This gives us an overall time complexity of O(N log(MaxDistance)).

It’s an excellent real-world inspired problem that blends greedy thinking with binary search — ideal for learning how to "search on the answer".

Algorithm Steps❯

Sort the arr in increasing order.
Set low = 1 (smallest possible min distance) and high = arr[n - 1] - arr[0] (largest possible).
Use binary search: while low ≤ high:
→ Compute mid = (low + high) / 2.
→ Check if it's possible to place k cows with at least mid distance between them.
→ If yes, store mid as a candidate and try for a larger value (low = mid + 1).
→ If not, reduce the distance (high = mid - 1).
Return the largest valid mid found.

Code

Java

Python

JavaScript

C++

Kotlin

Swift

Php

import java.util.Arrays;

public class AggressiveCows {
    public static boolean canPlace(int[] stalls, int cows, int minDist) {
        int count = 1; // Place first cow at the first stall
        int lastPlaced = stalls[0];
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPlaced >= minDist) {
                count++;
                lastPlaced = stalls[i];
                if (count == cows) return true;
            }
        }
        return false;
    }

    public static int solve(int n, int k, int[] arr) {
        Arrays.sort(arr);
        int low = 1, high = arr[n - 1] - arr[0];
        int result = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canPlace(arr, k, mid)) {
                result = mid; // Try for a bigger answer
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] stalls = {1, 2, 4, 8, 9};
        int k = 3;
        System.out.println("Max Min Distance: " + solve(stalls.length, k, stalls));
    }
}

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(n log(maxDist))	Binary search on the distance (log(max position)) and each check takes O(n).
Average Case	O(n log(maxDist))	Each iteration of binary search checks placement for given mid using O(n).
Worst Case	O(n log(maxDist))	In the worst case, binary search runs log(max distance) steps and each step scans the stalls.

Space Complexity❯

O(1)

Explanation: No extra space apart from a few variables; we sort in-place and use constant memory.

⬅ Previous TopicKth Missing Positive Number

Next Topic ⮕Allocate Minimum Number of Pages