Aggressive Cows Maximum Minimum Distance in DSA Typescript

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.

Stalls: 1   2   3   4   5   6   7   8   9   10
Cows:   C       C           C           C
Distances: 3 4 5 6 (minimum distance between cows)

Dry Run Walkthrough

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

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

Step 1: Sort stalls to [1, 2, 4, 8, 9]

Stalls sorted: [1, 2, 4, 8, 9]

Why: Sorting helps us check distances in order.

Step 2: Set search range for minimum distance: low=1, high=8 (max distance between first and last stall)

low=1, high=8

Why: We try distances between 1 and 8.

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

Try distance=4

Why: Check if 4 is possible.

Step 4: Place first cow at stall 1, next at stall 4 (distance 3 < 4 no), so next at stall 8 (distance 7 >=4), third at stall 9 (distance 1 <4 no)

Placed cows at stalls 1 and 8, only 2 cows placed

Why: Only 2 cows placed, need 3, so distance 4 too big.

Step 5: Reduce high to mid-1=3, new range low=1, high=3

low=1, high=3

Why: Try smaller distance.

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

Try distance=2

Why: Check if 2 is possible.

Step 7: Place cows at stalls 1, 4, 8 successfully (distances 3 and 4 >=2)

Placed cows at stalls 1, 4, 8

Why: All 3 cows placed with distance 2.

Step 8: Increase low to mid+1=3, new range low=3, high=3

low=3, high=3

Why: Try bigger distance.

Step 9: Check mid distance = 3; try placing cows with at least 3 apart

Try distance=3

Why: Check if 3 is possible.

Step 10: Place cows at stalls 1, 4, 8 successfully (distances 3 and 4 >=3)

Placed cows at stalls 1, 4, 8

Why: All 3 cows placed with distance 3.

Step 11: Increase low to mid+1=4, new range low=4, high=3 (low > high, stop)

low=4, high=3

Why: No larger distance possible.

Result:

Maximum minimum distance is 3
Cows placed at stalls 1, 4, 8

Annotated Code

DSA Typescript

class AggressiveCows {
  stalls: number[];
  cows: number;

  constructor(stalls: number[], cows: number) {
    this.stalls = stalls.sort((a, b) => a - b);
    this.cows = cows;
  }

  canPlace(distance: number): boolean {
    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; // placed all cows
        }
      }
    }
    return false; // cannot place all cows with this distance
  }

  maxMinDistance(): number {
    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 distance works
        low = mid + 1; // try bigger distance
      } else {
        high = mid - 1; // try smaller distance
      }
    }
    return result;
  }
}

// Driver code
const stalls = [1, 2, 4, 8, 9];
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; let lastPos = this.stalls[0];

place first cow at first stall

if (this.stalls[i] - lastPos >= distance) { count++; lastPos = this.stalls[i]; if (count === this.cows) return true; }

place next cow if distance condition met; stop if all cows placed

while (low <= high) { const mid = Math.floor((low + high) / 2); if (this.canPlace(mid)) { result = mid; low = mid + 1; } else { high = mid - 1; } }

binary search for maximum minimum distance

Output

3

Complexity Analysis

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

Space: O(n) for storing stalls array

vs Alternative: Naive approach tries all distances without binary search, leading to O(n*d) which is slower

Edge Cases

Only one stall

Maximum distance is 0 because only one cow can be placed

DSA Typescript

let high = this.stalls[this.stalls.length - 1] - this.stalls[0];

Number of cows equals number of stalls

Minimum distance is the smallest gap between consecutive stalls

DSA Typescript

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

All stalls at same position

Maximum distance is 0 because all stalls overlap

DSA Typescript

let high = this.stalls[this.stalls.length - 1] - this.stalls[0];

When to Use This Pattern

When you need to maximize the minimum distance between placed items in sorted positions, use binary search on distance with a feasibility check.

Common Mistakes

Mistake: Not sorting stalls before binary searching distances
Fix: Sort the stalls array before starting the binary search

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 instead of binary search for distance
Fix: Use binary search on the distance range for efficiency

Summary

Find the largest minimum distance to place cows in stalls.

Use when placing items to maximize minimum spacing.

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