Jaspreet singh

Posted on Jun 21

Aggressive Cows

#algorithms #computerscience #interview #java

Problem Statement

Given:

Positions of stalls
k cows

Place the cows in stalls such that:

Minimum distance between any two cows

is maximized.

Return the maximum possible minimum distance.

Brute Force Intuition

In an interview, you can explain it like this:

We can try every possible distance from 1 up to the maximum distance between stalls. For each distance, check whether all cows can be placed while maintaining at least that gap.

This works but is inefficient.

Complexity

Time Complexity: O(N × MaxDistance)
Space Complexity: O(1)

Brute Force Code

for(int dist = 1; dist <= maxDistance; dist++){

    if(canPlaceCows(dist)){
        answer = dist;
    }
}

Moving Towards the Optimal Approach

The important question becomes:

Can we place all cows
such that minimum distance = X ?

If yes:

Try a larger distance

If no:

Try a smaller distance

This monotonic behaviour is perfect for Binary Search.

Pattern Recognition

Whenever you see:

Maximize Minimum
Minimum Distance
Feasibility Check

Think:

Binary Search on Answer

Key Observation

Suppose:

Distance = 3

and we can successfully place all cows.

Then:

Distance = 2
Distance = 1

will also work.

Similarly:

If distance 5 fails,

6
7
8

will also fail.

This creates a monotonic search space.

Optimal Approach

Step 1

Sort the stalls.

Arrays.sort(stalls);

Step 2

Binary Search on distance.

Search Space:

low = 1

high = stalls[n-1] - stalls[0]

Step 3

Check feasibility.

Place first cow at:

First Stall

Then greedily place every next cow at the first stall satisfying:

currentPosition - previousPosition >= distance

Optimal Java Solution

class Solution {

    public static int aggressiveCows(int[] stalls,
                                     int k) {

        Arrays.sort(stalls);

        int low = 1;

        int high =
            stalls[stalls.length - 1]
            - stalls[0];

        while (low <= high) {

            int mid =
                low + (high - low) / 2;

            if (canPlace(stalls, k, mid)) {

                low = mid + 1;

            } else {

                high = mid - 1;
            }
        }

        return high;
    }

    private static boolean canPlace(int[] stalls,
                                    int cows,
                                    int distance) {

        int count = 1;

        int lastPlaced = stalls[0];

        for (int i = 1;
             i < stalls.length;
             i++) {

            if (stalls[i] - lastPlaced >= distance) {

                count++;

                lastPlaced = stalls[i];
            }
        }

        return count >= cows;
    }
}

Dry Run

Input

stalls = [1,2,4,8,9]

k = 3

After Sorting:

1 2 4 8 9

Iteration 1

low = 1
high = 8

mid = 4

Try placing cows:

Cow 1 -> 1

Cow 2 -> 8

Need distance >= 4

Only:

2 cows placed

Not Possible.

Move Left.

high = 3

Iteration 2

mid = 2

Place:

1
4
8

3 cows placed.

Possible.

Try Bigger Distance

low = 3

Iteration 3

mid = 3

Place:

1
4
8

3 cows placed.

Possible.

low = 4

Loop Ends.

Answer

Maximum minimum distance.

Why Binary Search Works?

If:

Distance = 3

works,

then:

1
2

will definitely work.

If:

Distance = 5

fails,

then:

6
7
8

will also fail.

This monotonic property makes Binary Search possible.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N log(MaxDistance))
Space Complexity	O(1)

Interview One-Liner

Binary search the minimum distance and greedily check whether all cows can be placed while maintaining that distance.

Pattern Learned

Maximize Minimum
+
Feasibility Check

=> Binary Search on Answer

Memory Trick