Aggressive Cows Problem - Visualization

Arrays - Binary Search

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n log(maxDist))Binary search on the distance (log(max position)) and each check takes O(n).
Average CaseO(n log(maxDist))Each iteration of binary search checks placement for given mid using O(n).
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...