Aggressive Cows Maximum Minimum Distance in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of placing cows with minimum distance 3

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

DSA Typescript

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];
      if (count === cows) return true;
    }
  }
  return false;
}

function aggressiveCows(stalls: number[], cows: number): number {
  stalls.sort((a, b) => a - b);
  let low = 1;
  let high = stalls[stalls.length - 1] - stalls[0];
  let result = 0;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    if (canPlaceCows(stalls, cows, mid)) {
      result = mid;
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return result;
}

console.log(aggressiveCows([1, 2, 4, 8, 9], 3));

A 4

B 3

C 2

D 5

💡 Hint

Try placing cows starting with the smallest distance and increase it using binary search.

The maximum minimum distance to place 3 cows in stalls [1,2,4,8,9] is 3. This is found by binary searching the distance and checking feasibility.

🧠 Conceptual

intermediate

Why do we sort stalls before placing cows?

In the Aggressive Cows problem, why is it necessary to sort the stall positions before applying the binary search approach?

A To reduce the number of stalls to consider by removing duplicates.

B Sorting is not necessary; cows can be placed in any order.

C To ensure we can check distances in increasing order and place cows greedily.

D To make the stalls positions negative for easier calculation.

💡 Hint

Think about how distance checking works between stalls.

Sorting stalls allows us to check distances between adjacent stalls in order and place cows greedily from left to right.

🔧 Debug

advanced

Identify the error in this code snippet

What error will this TypeScript code produce when trying to find the maximum minimum distance for aggressive cows? 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]; if (count === cows) return true; } } return false; } // rest of code omitted for brevity

A The condition 'stalls[i] - lastPos > dist' causes incorrect placement, missing valid positions.

B SyntaxError due to missing semicolon after 'let count = 1'

C TypeError because 'stalls' is not defined

D No error, code runs correctly

💡 Hint

Check the comparison operator in the if condition.

The condition should be '>=' to allow placing cows at exactly the minimum distance, otherwise some valid placements are missed.

🚀 Application

advanced

Maximum minimum distance for large input

Given 5 stalls at positions [10, 20, 30, 40, 50] and 3 cows, what is the maximum minimum distance to place all cows?

A 20

B 10

C 15

D 25

💡 Hint

Try placing cows with distances 10, 15, 20 and check feasibility.

The maximum minimum distance is 20 because cows can be placed at 10, 30, and 50 with minimum distance 20. It is not possible with distance 25 or more.

🧠 Conceptual

expert

Why binary search works on distance, not positions?

In the Aggressive Cows problem, why do we apply binary search on the minimum distance between cows instead of the stall positions themselves?

A Because searching positions directly would require checking all permutations of cow placements.

B Because stall positions are unsorted and cannot be searched.

C Because binary search only works on numeric arrays, not positions.

D Because the answer is a distance value, and binary searching distances narrows down the feasible minimum gap efficiently.

💡 Hint

Think about what the problem is asking to maximize and how binary search helps.

Binary search on distance helps find the largest minimum gap that can be maintained between cows, which is the problem's goal.