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

Time Complexity: Aggressive Cows Maximum Minimum Distance

O(n log d)

Understanding Time Complexity

We want to find the largest minimum distance to place cows in stalls. Analyzing time complexity helps us understand how the solution scales as the number of stalls grows.

How does the number of stalls affect the time taken to find this distance?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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 = 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;
}
    

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

Identify Repeating Operations

• Primary operation: The binary search loop runs while narrowing the distance range.
• How many times: Binary search runs about log of the distance range times.
• Inside each binary search step: The canPlaceCows function loops through all stalls once (linear scan).
• Dominant operation: The linear scan inside each binary search step dominates the time.

How Execution Grows With Input

As the number of stalls increases, the linear scan inside each binary search step grows linearly. The binary search steps grow with the distance range.

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

Pattern observation: Operations grow linearly with stalls and logarithmically with distance range.

Final Time Complexity

Time Complexity: O(n log d)

This means the time grows linearly with the number of stalls and logarithmically with the distance range between stalls.

Common Mistake

[X] Wrong: "The solution is just linear because we scan stalls once."

[OK] Correct: The binary search repeats the linear scan multiple times, so the total time is more than just one pass.

Interview Connect

Understanding how binary search combines with linear checks is a key skill. It shows how to handle problems where searching over a range is needed efficiently.

Self-Check

"What if we used a different method than binary search to find the distance? How would the time complexity change?"