Aggressive Cows

Problem Statement

Given:

• Positions of stalls
• k cows

Place the cows in stalls such that:

Minimum distance between any two cows

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Moving Towards the Optimal Approach

The important question becomes:

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

Enter fullscreen mode Exit fullscreen mode

If yes:

Try a larger distance

Enter fullscreen mode Exit fullscreen mode

If no:

Try a smaller distance

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

and we can successfully place all cows.

Then:

Distance = 2
Distance = 1

Enter fullscreen mode Exit fullscreen mode

will also work.

Similarly:

If distance 5 fails,

6
7
8

Enter fullscreen mode Exit fullscreen mode

will also fail.

This creates a monotonic search space.

Optimal Approach

Step 1

Sort the stalls.

Arrays.sort(stalls);

Enter fullscreen mode Exit fullscreen mode

Step 2

Binary Search on distance.

Search Space:

low = 1

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

Enter fullscreen mode Exit fullscreen mode

Step 3

Check feasibility.

Place first cow at:

First Stall

Enter fullscreen mode Exit fullscreen mode

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

currentPosition - previousPosition >= distance

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

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

k = 3

Enter fullscreen mode Exit fullscreen mode

After Sorting:

1 2 4 8 9

Enter fullscreen mode Exit fullscreen mode

Iteration 1

low = 1
high = 8

mid = 4

Enter fullscreen mode Exit fullscreen mode

Try placing cows:

Cow 1 -> 1

Cow 2 -> 8

Need distance >= 4

Enter fullscreen mode Exit fullscreen mode

Only:

2 cows placed

Enter fullscreen mode Exit fullscreen mode

Not Possible.

Move Left.

high = 3

Enter fullscreen mode Exit fullscreen mode

Iteration 2

mid = 2

Enter fullscreen mode Exit fullscreen mode

Place:

1
4
8

Enter fullscreen mode Exit fullscreen mode

3 cows placed.

Possible.

Try Bigger Distance

Enter fullscreen mode Exit fullscreen mode

low = 3

Enter fullscreen mode Exit fullscreen mode

Iteration 3

mid = 3

Enter fullscreen mode Exit fullscreen mode

Place:

1
4
8

Enter fullscreen mode Exit fullscreen mode

3 cows placed.

Possible.

low = 4

Enter fullscreen mode Exit fullscreen mode

Loop Ends.

Answer

3

Enter fullscreen mode Exit fullscreen mode

Maximum minimum distance.

Why Binary Search Works?

If:

Distance = 3

Enter fullscreen mode Exit fullscreen mode

works,

then:

1
2

Enter fullscreen mode Exit fullscreen mode

will definitely work.

If:

Distance = 5

Enter fullscreen mode Exit fullscreen mode

fails,

then:

6
7
8

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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 ?

Enter fullscreen mode Exit fullscreen mode

YES
→ Try Bigger Distance

NO
→ Try Smaller Distance

Enter fullscreen mode Exit fullscreen mode

Mental Model

Minimize Maximum
→ Allocate Pages

Maximize Minimum
→ Aggressive Cows

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Maximum possible minimum distance”

your brain should immediately think:

Binary Search on Answer + Greedy Placement 🚀