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.

Practice

1. What is the main goal of the Aggressive Cows Maximum Minimum Distance problem?

easy

A. To place cows in stalls so that the minimum distance between any two cows is as large as possible

B. To find the maximum number of cows that can fit in a single stall

C. To minimize the total distance cows travel between stalls

D. To arrange cows so that all are in consecutive stalls

Solution

1. Step 1: Understand the problem objective

   The problem asks to place cows in given stalls such that the smallest distance between any two cows is as large as possible.

2. Step 2: Identify the correct goal

   This means maximizing the minimum distance between cows, not minimizing travel or fitting all cows in one stall.

3. Final Answer:

   To place cows in stalls so that the minimum distance between any two cows is as large as possible -> Option A

4. Quick Check:

   Maximize minimum distance = To place cows in stalls so that the minimum distance between any two cows is as large as possible [OK]

Hint: Focus on maximizing the smallest gap between cows [OK]

Common Mistakes:

• Thinking it's about total distance traveled
• Assuming cows must be in consecutive stalls
• Confusing maximum distance with maximum number of cows

2. Which of the following TypeScript function signatures correctly represents the binary search approach used in the Aggressive Cows problem?

easy

A. function maxDistance(cows: number[], stalls: number): number

B. function placeCows(stalls: string[], cows: number): number

C. function canPlaceCows(stalls: number[], cows: number, distance: number): boolean

D. function binarySearch(distance: number[], cows: number): boolean

Solution

1. Step 1: Identify correct parameter types and purpose

   The function should check if cows can be placed in stalls with at least a given distance, so it needs stalls array, number of cows, and distance.

2. Step 2: Match signature to this logic

   function canPlaceCows(stalls: number[], cows: number, distance: number): boolean matches this: stalls as number array, cows count, and distance as number, returning boolean.

3. Final Answer:

   function canPlaceCows(stalls: number[], cows: number, distance: number): boolean -> Option C

4. Quick Check:

   Correct parameters and return type = function canPlaceCows(stalls: number[], cows: number, distance: number): boolean [OK]

Hint: Check parameter types match problem data (numbers, arrays) [OK]

Common Mistakes:

• Using wrong parameter types like string[] for stalls
• Returning wrong data type (e.g., number instead of boolean)
• Mixing order of parameters

3. Given stalls at positions [1, 2, 8, 4, 9] and 3 cows, what is the maximum minimum distance between any two cows?

medium

A. 2

B. 4

C. 5

D. 3

Solution

1. Step 1: Sort stall positions

   Sorted stalls: [1, 2, 4, 8, 9]

2. Step 2: Use binary search to find max minimum distance

   Try distance 3: place first cow at 1, second at 4 (distance 3), third at 8 (distance 4). Works.

3. Step 3: Check if distance 4 works

   Try distance 4: place first at 1, second at 8 (distance 7), third must be at least 4 away from 8, but 9 is only 1 away. Fails.

4. Final Answer:

   3 -> Option D

5. Quick Check:

   Max min distance = 3 [OK]

Hint: Sort stalls first, then binary search distances [OK]

Common Mistakes:

• Not sorting stalls before calculation
• Testing distances incorrectly
• Assuming max distance equals max stall difference

4. Consider this buggy TypeScript snippet for checking if cows can be placed:

function canPlaceCows(stalls: number[], cows: number, dist: number): boolean {
  let count = 1;
  let lastPos = stalls[0];
  for (let i = 1; i < stalls.length; i++) {
    if (stalls[i] - lastPos >= dist) {
      count++;
      lastPos = stalls[i];
    }
  }
  return count >= cows;
}

What is the main bug if stalls array is not sorted?

medium

A. The function will throw a runtime error due to index out of bounds

B. The function may incorrectly count placements because stalls are unsorted

C. The function returns a number instead of boolean

D. The function does not increment count properly

Solution

1. Step 1: Understand the function logic

   The function counts how many cows can be placed with at least 'dist' apart, assuming stalls are sorted.

2. Step 2: Identify effect of unsorted stalls

   If stalls are unsorted, the distance check stalls[i] - lastPos may be incorrect, causing wrong count of cows placed.

3. Final Answer:

   The function may incorrectly count placements because stalls are unsorted -> Option B

4. Quick Check:

   Unsorted stalls cause wrong counting = The function may incorrectly count placements because stalls are unsorted [OK]

Hint: Always sort stalls before placement checks [OK]

Common Mistakes:

• Ignoring sorting requirement
• Assuming function throws error on unsorted input
• Confusing return type or count increment logic

5. You have stalls at positions [1, 8, 15, 22, 25] and 4 cows. Using the binary search method, what is the maximum minimum distance you can place the cows apart?

hard

A. 7

B. 5

C. 8

D. 6

Solution

1. Step 1: Sort stalls (already sorted)

   Stalls: [1, 8, 15, 22, 25]

2. Step 2: Apply binary search on distance range

   Minimum distance can be 1, max distance is 25-1=24. Check mid distances:

3. Step 3: Check distance 9

   Place first cow at 1, next at 15 (distance 14), third at 25 (distance 10). Only 3 cows placed, need 4, so 9 fails.

4. Step 4: Check distance 7

   Place cows at 1, 8, 15, 22. Distances between placed cows are at least 7. 4 cows placed successfully.

5. Step 5: Check distance 8

   Place cows at 1, 15, 25. Only 3 cows placed, 4 needed, so 8 fails.

6. Final Answer:

   7 -> Option A

7. Quick Check:

   Max min distance = 7 [OK]

Hint: Test mid distances with binary search, adjust range accordingly [OK]

Common Mistakes:

• Not testing all mid values carefully
• Assuming max distance equals max stall difference
• Placing cows without checking minimum distance