Aggressive Cows Maximum Minimum Distance in DSA Go - 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 loop

↓

Return high 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 Go

positions := []int{1, 2, 8, 4, 9}
cows := 3
sort.Ints(positions)
maxDist := binarySearch(positions, cows)
fmt.Println(maxDist)

Sort stall positions and find max minimum distance to place 3 cows.

Execution Table

Step	Operation	low	high	mid	Can Place?	Action	Visual State (Placed Cows)
1	Sort positions	-	-	-	-	-	[1, 2, 4, 8, 9]
2	Initialize low and high	0	8	-	-	-	Positions sorted
3	Calculate mid	0	8	4	-	-	-
4	Check placement with mid=4	0	8	4	Yes	low = mid + 1 = 5	Cows at 1, 4, 8
5	Calculate mid	5	8	6	-	-	-
6	Check placement with mid=6	5	8	6	No	high = mid - 1 = 5	Cows at 1, 8
7	Calculate mid	5	5	5	-	-	-
8	Check placement with mid=5	5	5	5	Yes	low = mid + 1 = 6	Cows at 1, 4, 9
9	Calculate mid	6	5	-	-	-	-
10	Loop ends	6	5	-	-	-	-

💡 Loop ends when low (6) > high (5), max minimum distance is high = 5

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	Final
low	undefined	0	5	5	6	6
high	undefined	8	8	5	5	5
mid	undefined	-	4	6	5	-
Can Place?	undefined	-	Yes	No	Yes	-

Key Moments - 3 Insights

Why do we update low to mid + 1 when placement is possible?

Because if cows can be placed at distance mid, we try to find a larger minimum distance by increasing low (see Step 4 and Step 8 in execution_table).

Why do we update high to mid - 1 when placement is not possible?

Because if cows cannot be placed at distance mid, we reduce the search space by decreasing high to mid - 1 (see Step 6 in execution_table).

Why does the loop stop when low > high?

Because the search space is exhausted; the maximum minimum distance is the last successful mid stored in high (see Step 10 in execution_table).

Visual Quiz - 3 Questions

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

A 6

B 4

C 5

D 8

💡 Hint

Check the 'mid' column at Step 3 in execution_table.

At which step does the condition 'Can Place?' become No for the first time?

A Step 6

B Step 4

C Step 8

D Step 10

💡 Hint

Look at the 'Can Place?' column in execution_table to find the first 'No'.

If the number of cows was increased to 4, how would the final max minimum distance change?

A It would increase

B It would stay the same

C It would decrease

D Cannot determine from given data

💡 Hint

More cows require placing them closer, so max minimum distance usually decreases.

Concept Snapshot

Aggressive Cows Problem:
- Sort stall positions
- Use binary search on distance (low=0, high=max distance)
- Check if cows fit with mid distance
- If yes, try larger distance (low=mid+1)
- If no, try smaller distance (high=mid-1)
- Return high as 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 move low up to mid plus one to try a bigger distance. If no, we move high down to mid minus one to try a smaller distance. We repeat until low is greater than high. The answer is the last successful mid stored in high. This method efficiently finds the maximum minimum distance.