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❯

Understanding the Problem

We are given an array representing the positions of stalls along a straight line, such as [1, 2, 4, 8, 9]. Our goal is to place K cows in these stalls such that the **minimum distance between any two cows is as large as possible**.

In simpler words, the cows don't like being too close to each other. So, we have to spread them out in such a way that the closest pair of cows is still as far apart as we can manage — while still placing all cows.

This is a classic case of Binary Search on the Answer, where we don’t search through stall positions directly, but instead we ask: “What’s the largest minimum distance we can guarantee between any two cows?”

Step-by-Step Solution with Example

Step 1: Sort the Stall Positions

We begin by sorting the given array. This ensures that we consider stalls in proper order when placing cows.

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

Step 2: Apply Binary Search on Distance

We want to find the largest minimum distance possible. Let’s define our search space:

low = 1: The minimum possible distance (at least 1 unit apart)
high = max(stalls) - min(stalls) = 9 - 1 = 8: The maximum gap we could try

Step 3: Define the Feasibility Check

We write a helper function to check: "Is it possible to place all cows such that the minimum distance between them is at least mid?"

We try placing the first cow in the first stall, and then greedily place each next cow in the next stall that is at least mid away from the last one. If we can place all cows, return true, else false.

Step 4: Run Binary Search

We run a binary search loop:

Find the middle distance mid = Math.floor((low + high) / 2)
If placing cows with distance mid is possible → move to the right half to try a larger distance
If not possible → move to the left half to reduce distance

Keep track of the largest mid value for which placement worked — that will be our answer.

Step 5: Example Walkthrough

For stalls = [1, 2, 4, 8, 9] and K = 3, here's what the binary search would do:

Try mid = 4: Place cows at 1, 4, 8 → YES → try bigger
Try mid = 6: Place cows at 1, 9 → only 2 cows → NO → try smaller
Try mid = 5: Place cows at 1, 8 → only 2 cows → NO → try smaller
Try mid = 3: Place cows at 1, 4, 8 → YES → try bigger
Try mid = 4 (again): already checked

Eventually, we find that the largest minimum distance that allows all cows to be placed is 3.

Edge Cases

Only One Cow: If K = 1, we can place it anywhere. The answer is 0 since no second cow exists to compare distance.
Stalls Less Than Cows: If K > N, it's impossible to place all cows. We return -1 or throw an error.
All Stalls at Same Position: Example: [5, 5, 5]. No positive distance can be maintained → answer is 0.
Empty Stall List: No stall to place even a single cow → return -1.

Finally

This problem is a perfect example of how binary search can be used in non-obvious ways — not just on arrays, but also on possible “answers”.

It teaches us to focus on feasibility and gradually narrow down the range of possible solutions, ensuring both correctness and efficiency.

Time Complexity: O(N log(MaxDistance)), where N is the number of stalls.

It’s a powerful template for solving optimization problems involving placement, distance, and constraints.

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

Comments

Loading comments...