Aggressive Cows Maximum Minimum Distance in DSA Javascript - Time & Space Complexity

Time Complexity: Aggressive Cows Maximum Minimum Distance

O(n log d)

Understanding Time Complexity

We want to find how fast we can decide the largest minimum distance to place cows in stalls.

How does the time needed grow as the number of stalls and cows increase?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function canPlaceCows(stalls, cows, dist) {
  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, cows) {
  stalls.sort((a, b) => a - b);
  let low = 0, 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;
}
    

This code finds the largest minimum distance to place cows in stalls using binary search and a helper check.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The binary search loop runs while narrowing the distance range.
• Inside each binary search step: The canPlaceCows function loops through all stalls once.
• How many times: Binary search runs about log of the distance range times; each time it scans all stalls once.

How Execution Grows With Input

As the number of stalls (n) grows, the code scans all stalls multiple times during binary search.

Input Size (n)	Approx. Operations
10 stalls	About 10 * log(distance range) operations
100 stalls	About 100 * log(distance range) operations
1000 stalls	About 1000 * log(distance range) operations

Pattern observation: The operations grow linearly with the number of stalls and logarithmically with the distance range.

Final Time Complexity

Time Complexity: O(n log d)

This means the time grows roughly by the number of stalls times the logarithm of the distance range between stalls.

Common Mistake

[X] Wrong: "The binary search alone makes this O(log n) time."

[OK] Correct: Each binary search step requires scanning all stalls, so the total time depends on both the number of stalls and the binary search steps.

Interview Connect

Understanding this time complexity helps you explain how searching with checks works efficiently in real problems.

Self-Check

"What if we used a linear search instead of binary search for the distance? How would the time complexity change?"