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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of placing cows with minimum distance 3

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

DSA Javascript

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

function aggressiveCows(stalls, cows) {
  stalls.sort((a, b) => a - b);
  let low = 0;
  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, 8, 4, 9], 3));

A 4

B 2

C 3

D 5

💡 Hint

Think about binary searching the minimum distance and checking feasibility.

The maximum minimum distance that can be placed between 3 cows in stalls [1,2,4,8,9] is 3, but the binary search finds 5 as feasible and tries higher distances. The highest feasible minimum distance is 5, so the output is 5.

❓ Predict Output

intermediate

Output for stalls [10, 20, 30, 40, 50] and 2 cows

What is the maximum minimum distance between 2 cows placed in stalls at positions [10, 20, 30, 40, 50]?

DSA Javascript

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

function aggressiveCows(stalls, cows) {
  stalls.sort((a, b) => a - b);
  let low = 0;
  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([10, 20, 30, 40, 50], 2));

A 40

B 20

C 30

D 10

💡 Hint

With only 2 cows, place them at the farthest stalls.

With 2 cows, placing them at the first and last stall gives the maximum minimum distance of 40 (50 - 10).

🔧 Debug

advanced

Identify the error in the canPlaceCows function

What error will the following code cause when running aggressiveCows([1, 2, 4, 8, 9], 3)?

DSA Javascript

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

function aggressiveCows(stalls, cows) {
  stalls.sort((a, b) => a - b);
  let low = 0;
  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 The function returns false always because count starts at 0 instead of 1

B SyntaxError due to missing semicolon

C TypeError because stalls is undefined

D No error, output is 3

💡 Hint

Check the initial count of placed cows.

The count should start at 1 because the first cow is placed at stalls[0]. Starting at 0 causes the function to underestimate cows placed and return false incorrectly.

🧠 Conceptual

advanced

Why use binary search in Aggressive Cows problem?

Why is binary search used to find the maximum minimum distance in the Aggressive Cows problem?

A Because binary search sorts the stalls automatically

B Because the search space of distances is sorted and we can check feasibility efficiently

C Because it finds the exact positions of cows directly

D Because it reduces the number of cows needed

💡 Hint

Think about the range of possible distances and how to test them.

Binary search is used on the range of possible distances because it is sorted and checking if cows can be placed at a given distance is efficient, allowing us to find the maximum feasible distance quickly.

🚀 Application

expert

Maximum minimum distance for large input

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

DSA Javascript

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

function aggressiveCows(stalls, cows) {
  stalls.sort((a, b) => a - b);
  let low = 0;
  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, 12, 15, 18, 20, 25], 4));

A 8

B 5

C 6

D 7

💡 Hint

Use binary search and feasibility check to find the answer.

The maximum minimum distance for placing 4 cows in the given stalls is 6. Distances like 7 or 8 are not feasible because cows cannot be placed with that spacing.