Aggressive Cows

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

3

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

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

Similar Problems

• Aggressive Cows


• Allocate Minimum Pages


• Painter's Partition


• Capacity To Ship Packages


• Koko Eating Bananas


• Minimum Days To Make Bouquets

Memory Trick

Think:

Can I place all cows

with minimum distance X ?

YES

→ Try Bigger Distance



NO

→ Try Smaller Distance

Mental Model

Minimize Maximum

→ Allocate Pages



Maximize Minimum

→ Aggressive Cows

Whenever you hear:

"Maximum possible minimum distance"

your brain should immediately think:

Binary Search on Answer + Greedy Placement 🚀