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

Yes No↓

low=mid+1

↓

Repeat until low > high

↓

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 Typescript

function canPlaceCows(stalls: number[], cows: number, dist: number): boolean {
  let count = 1, lastPos = stalls[0];
  for (let i = 1; i < stalls.length; i++) {
    if (stalls[i] - lastPos >= dist) {
      count++;
      lastPos = stalls[i];
    }
  }
  return count >= cows;
}

Checks if cows can be placed in stalls with at least 'dist' distance apart.

Execution Table

Step	Operation	low	high	mid	Can Place?	Action	Visual State (Placed Cows)
1	Sort stalls	-	-	-	-	-	[1, 2, 5, 8, 9]
2	Initialize low and high	0	8	-	-	-	-
3	Calculate mid	0	8	4	-	-	-
4	Check placement with dist=4	0	8	4	Yes	low = mid + 1 = 5	[1, 5, 9]
5	Calculate mid	5	8	6	-	-	-
6	Check placement with dist=6	5	8	6	No	high = mid - 1 = 5	[1, 8]
7	Calculate mid	5	5	5	-	-	-
8	Check placement with dist=5	5	5	5	Yes	low = mid + 1 = 6	[1, 5, 9]
9	Exit loop	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	-	0	5	5	6	6
high	-	8	8	5	5	5
mid	-	-	4	6	5	-
Can Place?	-	-	Yes	No	Yes	-
Placed Cows	-	-	[1,5,9]	[1,8]	[1,5,9]	-

Key Moments - 3 Insights

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

Because if cows fit at distance 'mid', 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'?

Because distance 'mid' is too large to place all cows, so we reduce the search space by setting high = mid - 1 (see Step 6).

Why do we return 'high' as the answer after the loop ends?

Because 'high' holds the largest distance where cows could still be placed, as loop ends when low > high (Step 9).

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the value of 'mid' and was placement possible?

A mid=4, placement not possible

B mid=4, placement possible

C mid=5, placement possible

D mid=5, placement not possible

💡 Hint

Check columns 'mid' and 'Can Place?' at Step 4 in execution_table

At which step does the condition 'canPlaceCows' return 'No' for the first time?

A Step 4

B Step 8

C Step 6

D Step 9

💡 Hint

Look at 'Can Place?' column in execution_table rows

If the stalls array was [1, 2, 4, 8, 12], how would the maximum minimum distance change compared to the current example?

A It would increase

B It would decrease

C It would stay the same

D Cannot determine without more info

💡 Hint

Consider that the max distance between stalls increases from 8 to 11, so max minimum distance can increase

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 bigger 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. 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 + 1 to try a bigger distance. If no, we move high down to mid - 1 to try a smaller distance. We repeat until low is greater than high. The answer is the last successful distance stored in high. This approach efficiently finds the maximum minimum distance for placing cows.