AlgoViz
HomeBinary Search

Aggressive Cows

Hard

Maximize the minimum spacing

In simple words

Guess a spacing between cows; if they all fit that far apart try a bigger gap, otherwise a smaller one.

The idea

If cows fit with a minimum gap g, they also fit with any smaller gap — monotone. Binary search the largest gap that still places all cows.

1
2
3
4
5
6
7
8
0
1
2
3
4
5
6
7
candidates8

Step 1 of 6. Brute force: try every spacing, keep the largest that still seats 3 cows. Values: 1, 2, 3, 4, 5, 6, 7, 8. candidates 8.

1/6
Brute force
timeO(range·n)spaceO(1)

Try every gap.

1let best = -1;2for (let d = maxGap; d >= 1 && best < 0; d--)3  if (canPlace(d)) best = d;4return best;

Input

array
[1, 2, 3, 4, 5, 6, 7, 8]

Memory

try
—
candidates
8

Output

best
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
stalls = [0, 3, 4, 7, 10, 9], cows = 4
Output:
3
Explanation:
Placing 4 cows, the largest minimum gap is 3.

Example 2

Input:
stalls = [1, 2, 4, 8, 9], cows = 3
Output:
3
Explanation:
Best minimum spacing is 3.

Example 3

Input:
stalls = [1, 2, 3], cows = 2
Output:
2
Explanation:
Two cows can sit 2 apart.

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.