Aggressive Cows Maximum Minimum Distance in DSA Javascript

Mental Model

We want to place cows in stalls so that the smallest distance between any two cows is as large as possible.

Analogy: Imagine placing friends in seats along a bench so that everyone has as much personal space as possible between them.

Stalls: 1 -> 2 -> 4 -> 8 -> 9 -> 12 -> null
Cows to place: 3
Goal: Maximize minimum distance between cows

Dry Run Walkthrough

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

Goal: Place 3 cows in stalls so that the smallest distance between any two cows is as large as possible

Step 1: Sort stalls and set search range for distance: low=1, high=11

Stalls: 1 -> 2 -> 4 -> 8 -> 9 -> 12 -> null
Search range: low=1, high=11

Why: We need to search for the largest minimum distance between cows

Step 2: Check mid distance = (1+11)//2 = 6; try placing cows with at least 6 apart

Place cow at 1
Next cow at stall ≥ 1+6=7 -> stall 8
Next cow at stall ≥ 8+6=14 -> no stall
Cows placed: 2 < 3 needed

Why: Distance 6 too large, cannot place all cows

Step 3: Reduce high to mid-1 = 5; check mid = (1+5)//2 = 3

Place cow at 1
Next cow at stall ≥ 1+3=4 -> stall 4
Next cow at stall ≥ 4+3=7 -> stall 8
Cows placed: 3 = needed

Why: Distance 3 works, try larger distance

Step 4: Increase low to mid+1 = 4; check mid = (4+5)//2 = 4

Place cow at 1
Next cow at stall ≥ 1+4=5 -> stall 8
Next cow at stall ≥ 8+4=12 -> stall 12
Cows placed: 3 = needed

Why: Distance 4 works, try larger distance

Step 5: Increase low to mid+1 = 5; check mid = (5+5)//2 = 5

Place cow at 1
Next cow at stall ≥ 1+5=6 -> stall 8
Next cow at stall ≥ 8+5=13 -> no stall
Cows placed: 2 < 3 needed

Why: Distance 5 too large, reduce

Step 6: Reduce high to mid-1 = 4; low=5 > high=4, stop search

Final max minimum distance = 4

Why: Search ends when low > high; last valid distance is 4

Result:

Max minimum distance = 4

Annotated Code

DSA Javascript

class AggressiveCows {
  constructor(stalls, cows) {
    this.stalls = stalls.sort((a, b) => a - b);
    this.cows = cows;
  }

  canPlace(distance) {
    let count = 1; // place first cow at first stall
    let lastPos = this.stalls[0];
    for (let i = 1; i < this.stalls.length; i++) {
      if (this.stalls[i] - lastPos >= distance) {
        count++;
        lastPos = this.stalls[i];
        if (count === this.cows) return true;
      }
    }
    return false;
  }

  maxMinDistance() {
    let low = 1;
    let high = this.stalls[this.stalls.length - 1] - this.stalls[0];
    let result = 0;

    while (low <= high) {
      const mid = Math.floor((low + high) / 2);
      if (this.canPlace(mid)) {
        result = mid; // mid works, try bigger
        low = mid + 1;
      } else {
        high = mid - 1; // mid too big, try smaller
      }
    }
    return result;
  }
}

// Driver code
const stalls = [1, 2, 4, 8, 9, 12];
const cows = 3;
const aggressiveCows = new AggressiveCows(stalls, cows);
console.log(aggressiveCows.maxMinDistance());

this.stalls = stalls.sort((a, b) => a - b);

sort stalls to check distances in order

let count = 1; // place first cow at first stall

start placing first cow at first stall

if (this.stalls[i] - lastPos >= distance) {

check if current stall is far enough from last placed cow

if (count === this.cows) return true;

all cows placed successfully with given distance

while (low <= high) {

binary search over possible distances

if (this.canPlace(mid)) {

if cows can be placed with mid distance, try bigger

else { high = mid - 1; }

if cannot place, try smaller distance

Output

4

Complexity Analysis

Time: O(n log d) because we do binary search on distance range (d) and check placement in O(n)

Space: O(n) for storing stalls array

vs Alternative: Naive approach tries all distances linearly O(n*d), binary search reduces to O(n log d)

Edge Cases

Only one stall

Distance is zero because only one cow can be placed

DSA Javascript

if (count === this.cows) return true;

Number of cows equals number of stalls

Minimum distance is the smallest gap between consecutive stalls

DSA Javascript

this.stalls = stalls.sort((a, b) => a - b);

Cows more than stalls

Cannot place all cows, result is zero

DSA Javascript

if (count === this.cows) return true;

When to Use This Pattern

When asked to maximize minimum distance between placed items in sorted positions, use binary search on distance combined with a greedy check.

Common Mistakes

Mistake: Not sorting stalls before binary searching distances
Fix: Always sort stalls first to ensure correct distance checks

Mistake: Checking placement incorrectly by not updating last placed position
Fix: Update last placed stall position only when a cow is placed

Mistake: Using linear search for distance instead of binary search
Fix: Use binary search on distance range for efficiency

Summary

Find the largest minimum distance to place all cows in stalls.

Use when you need to space items as far apart as possible in a sorted set of positions.

Binary search on distance combined with greedy placement check is the key insight.