Aggressive Cows Problem

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.

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.

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

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int canPlace(int stalls[], int n, int cows, int minDist) {
    int count = 1, lastPlaced = stalls[0];
    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPlaced >= minDist) {
            count++;
            lastPlaced = stalls[i];
            if (count == cows) return 1;
        }
    }
    return 0;
}

int solve(int stalls[], int n, int k) {
    qsort(stalls, n, sizeof(int), compare);
    int low = 1, high = stalls[n - 1] - stalls[0], result = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (canPlace(stalls, n, k, mid)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    int stalls[] = {1, 2, 4, 8, 9};
    int k = 3;
    int n = sizeof(stalls) / sizeof(stalls[0]);
    printf("Max Min Distance: %d\n", solve(stalls, n, k));
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;

bool canPlace(int stalls[], int n, int cows, int minDist) {
    int count = 1, lastPlaced = stalls[0];
    for (int i = 1; i < n; i++) {
        if (stalls[i] - lastPlaced >= minDist) {
            count++;
            lastPlaced = stalls[i];
            if (count == cows) return true;
        }
    }
    return false;
}

int solve(int stalls[], int n, int k) {
    sort(stalls, stalls + n);
    int low = 1, high = stalls[n - 1] - stalls[0], result = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (canPlace(stalls, n, k, mid)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

int main() {
    int stalls[] = {1, 2, 4, 8, 9};
    int k = 3;
    int n = sizeof(stalls) / sizeof(stalls[0]);
    cout << "Max Min Distance: " << solve(stalls, n, k) << endl;
    return 0;
}

def can_place(stalls, cows, min_dist):
    count = 1
    last_pos = stalls[0]
    for i in range(1, len(stalls)):
        if stalls[i] - last_pos >= min_dist:
            count += 1
            last_pos = stalls[i]
            if count == cows:
                return True
    return False

def solve(n, k, stalls):
    stalls.sort()
    low, high = 1, stalls[-1] - stalls[0]
    result = 0
    while low <= high:
        mid = (low + high) // 2
        if can_place(stalls, k, mid):
            result = mid
            low = mid + 1
        else:
            high = mid - 1
    return result

stalls = [1, 2, 4, 8, 9]
k = 3
print("Max Min Distance:", solve(len(stalls), k, stalls))

import java.util.Arrays;

public class AggressiveCows {
    public static boolean canPlace(int[] stalls, int cows, int minDist) {
        int count = 1;
        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;
                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));
    }
}

function canPlace(stalls, cows, minDist) {
    let count = 1;
    let lastPlaced = stalls[0];
    for (let i = 1; i < stalls.length; i++) {
        if (stalls[i] - lastPlaced >= minDist) {
            count++;
            lastPlaced = stalls[i];
            if (count === cows) return true;
        }
    }
    return false;
}

function solve(n, k, stalls) {
    stalls.sort((a, b) => a - b);
    let low = 1, high = stalls[n - 1] - stalls[0];
    let result = 0;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canPlace(stalls, k, mid)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

const stalls = [1, 2, 4, 8, 9];
const k = 3;
console.log("Max Min Distance:", solve(stalls.length, k, stalls));

package main

import (
    "fmt"
    "sort"
)

func canPlace(stalls []int, cows, minDist int) bool {
    count := 1
    lastPlaced := stalls[0]
    for i := 1; i < len(stalls); i++ {
        if stalls[i]-lastPlaced >= minDist {
            count++
            lastPlaced = stalls[i]
            if count == cows {
                return true
            }
        }
    }
    return false
}

func solve(stalls []int, k int) int {
    sort.Ints(stalls)
    low, high := 1, stalls[len(stalls)-1]-stalls[0]
    result := 0
    for low <= high {
        mid := (low + high) / 2
        if canPlace(stalls, k, mid) {
            result = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}

func main() {
    stalls := []int{1, 2, 4, 8, 9}
    k := 3
    fmt.Println("Max Min Distance:", solve(stalls, k))
}

fn can_place(stalls: &Vec<i32>, cows: i32, min_dist: i32) -> bool {
    let mut count = 1;
    let mut last_placed = stalls[0];
    for &stall in stalls.iter().skip(1) {
        if stall - last_placed >= min_dist {
            count += 1;
            last_placed = stall;
            if count == cows {
                return true;
            }
        }
    }
    false
}

fn solve(mut stalls: Vec<i32>, k: i32) -> i32 {
    stalls.sort();
    let (mut low, mut high) = (1, stalls[stalls.len()-1] - stalls[0]);
    let mut result = 0;
    while low <= high {
        let mid = (low + high) / 2;
        if can_place(&stalls, k, mid) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    result
}

fn main() {
    let stalls = vec![1, 2, 4, 8, 9];
    let k = 3;
    println!("Max Min Distance: {}", solve(stalls, k));
}

fun canPlace(stalls: List<Int>, cows: Int, minDist: Int): Boolean {
    var count = 1
    var lastPlaced = stalls[0]
    for (i in 1 until stalls.size) {
        if (stalls[i] - lastPlaced >= minDist) {
            count++
            lastPlaced = stalls[i]
            if (count == cows) return true
        }
    }
    return false
}

fun solve(stalls: List<Int>, k: Int): Int {
    val sortedStalls = stalls.sorted()
    var low = 1
    var high = sortedStalls.last() - sortedStalls.first()
    var result = 0
    while (low <= high) {
        val mid = (low + high) / 2
        if (canPlace(sortedStalls, k, mid)) {
            result = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}

fun main() {
    val stalls = listOf(1, 2, 4, 8, 9)
    val k = 3
    println("Max Min Distance: ${solve(stalls, k)}")
}

func canPlace(_ stalls: [Int], _ cows: Int, _ minDist: Int) -> Bool {
    var count = 1
    var lastPlaced = stalls[0]
    for i in 1..<stalls.count {
        if stalls[i] - lastPlaced >= minDist {
            count += 1
            lastPlaced = stalls[i]
            if count == cows {
                return true
            }
        }
    }
    return false
}

func solve(_ stalls: [Int], _ k: Int) -> Int {
    let sorted = stalls.sorted()
    var low = 1
    var high = sorted.last! - sorted.first!
    var result = 0
    while low <= high {
        let mid = (low + high) / 2
        if canPlace(sorted, k, mid) {
            result = mid
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return result
}

let stalls = [1, 2, 4, 8, 9]
let k = 3
print("Max Min Distance: \(solve(stalls, k))")

function canPlace(stalls: number[], cows: number, minDist: number): boolean {
    let count = 1;
    let lastPlaced = stalls[0];
    for (let i = 1; i < stalls.length; i++) {
        if (stalls[i] - lastPlaced >= minDist) {
            count++;
            lastPlaced = stalls[i];
            if (count === cows) return true;
        }
    }
    return false;
}

function solve(n: number, k: number, stalls: number[]): number {
    stalls.sort((a, b) => a - b);
    let low = 1, high = stalls[n - 1] - stalls[0];
    let result = 0;
    while (low <= high) {
        let mid = Math.floor((low + high) / 2);
        if (canPlace(stalls, k, mid)) {
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return result;
}

const stalls = [1, 2, 4, 8, 9];
const k = 3;
console.log("Max Min Distance:", solve(stalls.length, k, stalls));

Time complexity

Space complexity

O(1)

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