Aggressive Cows Maximum Minimum Distance in DSA Typescript - Build from Scratch

Aggressive Cows Maximum Minimum Distance

📖 Scenario: You are managing a farm with several stalls placed along a straight line. You want to place cows in these stalls so that the minimum distance between any two cows is as large as possible. This helps keep the cows calm and happy.

🎯 Goal: Build a program that finds the largest minimum distance possible between cows placed in the stalls.

📋 What You'll Learn

Create an array called stalls with the exact values [1, 2, 8, 4, 9] representing stall positions.

Create a variable called cows and set it to 3 representing the number of cows to place.

Write a function called canPlaceCows that checks if cows can be placed with at least a given minimum distance.

Use binary search to find the maximum minimum distance possible.

Print the final maximum minimum distance.

💡 Why This Matters

🌍 Real World

This problem models placing resources or devices in locations to maximize minimum spacing, useful in network design, agriculture, and facility planning.

💼 Career

Understanding binary search on answer space and greedy placement is important for software engineering roles involving optimization and algorithm design.

1

Create the stalls array

Create an array called stalls with these exact values: [1, 2, 8, 4, 9].

DSA Typescript

# Create the stalls array with the given positions
// Your code here

Hint

Use const stalls = [1, 2, 8, 4, 9]; to create the array.

2

Set the number of cows

Create a variable called cows and set it to 3.

DSA Typescript

const stalls = [1, 2, 8, 4, 9];
// Create the cows variable and set it to 3
// Your code here

Hint

Use const cows = 3; to set the number of cows.

3

Write the function to check placement feasibility

Write a function called canPlaceCows that takes distance as a parameter and returns true if it is possible to place all cows in stalls with at least that distance between them, otherwise false. Use variables count and lastPosition inside the function.

DSA Typescript

const stalls = [1, 2, 8, 4, 9];
const cows = 3;
// Write the canPlaceCows function below
// Your code here

Hint

Sort the stalls first. Then try placing cows starting from the first stall. Increase count when distance condition is met.

4

Find and print the maximum minimum distance

Use binary search between low = 1 and high = max(stalls) - min(stalls) to find the largest minimum distance where canPlaceCows returns true. Print the final maximum minimum distance using console.log.

DSA Typescript

const stalls = [1, 2, 8, 4, 9];
const cows = 3;

function canPlaceCows(distance: number): boolean {
    stalls.sort((a, b) => a - b);
    let count = 1;
    let lastPosition = stalls[0];
    for (let i = 1; i = distance) {
            count++;
            lastPosition = stalls[i];
            if (count === cows) {
                return true;
            }
        }
    }
    return false;
}

// Use binary search to find max minimum distance and print it
// Your code here

Hint

Use binary search on distance. If canPlaceCows(mid) is true, try bigger distance. Otherwise, try smaller.

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