Aggressive Cows Maximum Minimum Distance in DSA Go - 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.

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

func aggressiveCows(stalls []int, cows int) int {
    sort.Ints(stalls)
    low, high := 0, stalls[len(stalls)-1]-stalls[0]
    result := 0
    for low <= high {
        mid := (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 that tries different distances.
• How many times: About log of the maximum distance between stalls.
• Secondary operation: The canPlaceCows function loops through all stalls each time to check feasibility.
• How many times: Runs once per binary search step, so about log(maxDistance) times.

How Execution Grows With Input

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

Input Size (n stalls)	Approx. Operations
10	10 * log(maxDistance)
100	100 * log(maxDistance)
1000	1000 * log(maxDistance)

Pattern observation: Operations grow linearly with number of 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 binary search alone makes this O(log n) time."

[OK] Correct: Each binary search step runs a full check over all stalls, so the linear scan dominates and multiplies the log steps.

Interview Connect

Understanding this time complexity helps you explain how binary search can be combined with linear checks to solve placement problems efficiently.

Self-Check

What if we used a different method to check feasibility instead of scanning all stalls? How would the time complexity change?