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

Time Complexity: Aggressive Cows Maximum Minimum Distance

O(n log d)

Understanding Time Complexity

We want to find how fast the algorithm finds 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.

bool canPlaceCows(int stalls[], int n, int cows, int dist) {
    int count = 1, last_pos = stalls[0];
    for (int i = 1; i < n; i++) {
        if (stalls[i] - last_pos >= dist) {
            count++;
            last_pos = stalls[i];
            if (count == cows) return true;
        }
    }
    return false;
}

int aggressiveCows(int stalls[], int n, int cows) {
    sort(stalls, stalls + n);
    int low = 1, high = stalls[n-1] - stalls[0], ans = 0;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canPlaceCows(stalls, n, cows, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}
    

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 that tries different distances.
• How many times: The binary search runs about log of the distance range times.
• Secondary operation: The canPlaceCows function scans all stalls each time to check feasibility.
• How many times: It runs once per binary search step, scanning all stalls (n times).

How Execution Grows With Input

As the number of stalls (n) grows, the check runs over all stalls each binary search step.

Input Size (n)	Approx. Operations
10 stalls	About 10 * log(distance range)
100 stalls	About 100 * log(distance range)
1000 stalls	About 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.

Common Mistake

[X] Wrong: "The algorithm is just linear because it scans stalls once."

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

Interview Connect

Understanding this time complexity helps you explain how binary search can speed up searching over ranges combined with linear checks.

Self-Check

"What if we used a different method to check feasibility that was faster than scanning all stalls? How would the time complexity change?"