Aggressive Cows Maximum Minimum Distance in DSA C++ - Execution Trace

Concept Flow - Aggressive Cows Maximum Minimum Distance

Sort stall positions

↓

Set low = 0, high = max distance

↓

While low <= high

↓

Calculate mid = (low + high)/2

↓

Check if cows can be placed with distance mid

↓

Update low = mid+1

↓

Repeat until low > high

↓

Return result as max minimum distance

We sort stall positions, then use binary search on distance to find the largest minimum distance to place all cows.

Execution Sample

DSA C++

int aggressiveCows(vector<int>& stalls, int cows) {
  sort(stalls.begin(), stalls.end());
  int low = 0, high = stalls.back() - stalls.front();
  int result = 0;
  while (low <= high) {
    int mid = (low + high) / 2;

This code sorts stalls and uses binary search on distance to find max minimum distance for placing cows.

Execution Table

Step	Operation	Distance mid	Can place cows?	Update low/high	Result	Visual State (Stalls with cows)
1	Sort stalls	-	-	-	-	[1, 2, 5, 8, 9]
2	Initialize low and high	-	-	-	-	low=0, high=8
3	Calculate mid	4	-	-	-	-
4	Check placement with distance 4	4	Yes	low=5	4	Cows at positions 1, 5, 9
5	Calculate mid	6	-	-	-	-
6	Check placement with distance 6	6	No	high=5	4	Cows at positions 1, 8
7	Calculate mid	5	-	-	-	-
8	Check placement with distance 5	5	No	high=4	4	Cows at positions 1, 8
9	Loop ends	-	-	-	4	Final max minimum distance

💡 Loop ends when low (5) > high (4), returning result 4 as maximum minimum distance.

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
low	0	0	5	5	5	5
high	0	8	8	5	4	4
mid	-	-	4	6	5	-
result	0	0	4	4	4	4

Key Moments - 3 Insights

Why do we update 'low' when cows can be placed at distance mid?

Because placing cows at distance mid is possible, we try to find a larger minimum distance by setting low = mid + 1 (see Step 4 in execution_table).

Why do we update 'high' when cows cannot be placed at distance mid?

If cows can't be placed at distance mid, we reduce the search space by setting high = mid - 1 to try smaller distances (see Steps 6 and 8).

Why do we return 'result' after the loop ends?

Result stores the largest distance where placement was possible. When low > high, no larger distance can be found, so we return result (Step 9).

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at Step 6?

A 4

B 6

C 5

D 8

💡 Hint

Check the 'Distance mid' column at Step 6 in the execution_table.

At which step does the algorithm decide that distance 5 is not possible?

A Step 8

B Step 6

C Step 4

D Step 9

💡 Hint

Look for 'Can place cows?' = No with distance mid = 5 in the execution_table.

If the stalls were [1, 2, 4, 8, 12], how would the initial 'high' value change?

A It would be 12

B It would be 8

C It would be 11

D It would be 10

💡 Hint

High is calculated as stalls.back() - stalls.front(), check the new stall positions.

Concept Snapshot

Aggressive Cows Problem:
- Sort stall positions.
- Use binary search on distance (low=0, high=max distance).
- Check if cows can be placed with mid distance.
- If yes, move low up; if no, move high down.
- Continue until low > high.
- Result is max minimum distance.

Full Transcript

The Aggressive Cows problem finds the largest minimum distance to place cows in stalls. We first sort the stall positions. Then, we use binary search on the distance between cows. We set low to 0 and high to the maximum distance between the first and last stall. In each step, we calculate mid as the average of low and high. We check if cows can be placed with at least mid distance apart. If yes, we try a larger distance by setting low to mid plus one. If no, we try smaller distances by setting high to mid minus one. We repeat this until low is greater than high. The result is the largest minimum distance where placement was possible.