PPractick

The problem

A farmer has n stalls along a straight barn at given positions and c cows that fight when placed close together. He wants to place all c cows in stalls so that the minimum distance between any two cows is as large as possible. Trying all placements is exponential. Flip the question: "Can I place c cows so that every pair is at least d apart?" That's a greedy check (put each cow in the first stall far enough from the previous one), and if distance d is achievable, every smaller distance is too. So binary search the largest achievable d.

Example: stalls [1, 2, 4, 8, 9], c = 3 → 3 (cows at 1, 4 and 8, or 1, 4 and 9).

Function signature

int aggressiveCows(vector<int> stalls, int cows);  // largest possible minimum distance; 2 <= cows <= n

Test cases

Input (stalls, cows)	Output	Explanation
([1, 2, 4, 8, 9], 3)	3	For example 1, 4, 8
([10, 1, 2, 7, 5], 3)	4	Sorted [1, 2, 5, 7, 10]: 1, 5, 10
([2, 12, 11, 3, 26, 7], 5)	1	Five cows force stalls 1 apart
([0, 3, 4, 7, 10, 9], 4)	3	0, 3, 7, 10
([1, 2], 2)	1

(Confirm: stall positions are distinct and unsorted; 2 ≤ cows ≤ number of stalls.)

How interviewers phrase it

• "Aggressive cows" (SPOJ AGGRCOW, GeeksforGeeks).
• "Magnetic force between two balls" (LeetCode 1552) is the same problem.
• The canonical "maximise the minimum" binary search.

Clarifying questions to ask

1. Are the stall positions sorted? (If not, sort first.)
2. Are positions distinct?
3. At least two cows?

Follow-ups to expect

1. "Why is the greedy check correct?"
2. "Why binary search?"
3. "What's the range?"
4. "How is this 'maximise the minimum' different from 'minimise the maximum' (book allocation)?"
5. "Complexity?"

Related questions

• Book Allocation Problem Hard
• Split array - largest sum Hard
• Minimize Max Distance to Gas Station Hard
• Maximum Sum Combination Hard
• Selection Sort Easy
• Bubble Sort Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in