Aggressive Cows Maximum Minimum Distance in DSA Javascript - Execution Trace

Concept Flow - Aggressive Cows Maximum Minimum Distance

Sort stall positions

↓

Set low = 0, high = max distance

↓

While low <= high

↓

Calculate mid = Math.floor((low + high) / 2)

↓

Check if cows can be placed with distance mid

↓

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 Javascript

function canPlaceCows(stalls, cows, dist) {
  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;
}

This function checks if cows can be placed in stalls with at least 'dist' distance apart.

Execution Table

Step	Operation	mid (distance)	Can Place?	low	high	Visual State (Stalls with cows)
1	Sort stalls	-	-	-	-	Stalls: [1, 2, 5, 8, 9]
2	Initialize low and high	-	-	0	8	low=0, high=9-1=8
3	Calculate mid	4	-	0	8	-
4	Check placement with dist=4	4	Yes	0	8	Cows at positions 1, 5, 9
5	Update low = mid + 1	-	-	5	8	-
6	Calculate mid	6	-	5	8	-
7	Check placement with dist=6	6	No	5	8	Cows at positions 1, 8 (only 2 cows placed, need 3)
8	Update high = mid - 1	-	-	5	5	-
9	Calculate mid	5	-	5	5	-
10	Check placement with dist=5	5	No	5	5	Cows at positions 1, 8 (only 2 cows placed)
11	Update high = mid - 1	-	-	5	4	-
12	Exit loop	-	-	5	4	low > high, stop
13	Return high	-	-	-	-	Max minimum distance = 4

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

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 7	After Step 8	After Step 10	After Step 11	Final
low	0	0	5	5	5	5	5	5
high	8	8	8	5	5	5	4	4
mid	-	4	4	6	6	5	5	-
Can Place?	-	Yes	Yes	No	No	No	No	-

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 5 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 high to mid - 1 to try smaller distances (see step 8 and 11).

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

When low > high, 'high' holds the largest distance where placement was possible (step 13).

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the minimum distance 'mid' tested and can cows be placed?

A mid = 5, No

B mid = 4, Yes

C mid = 6, No

D mid = 8, Yes

💡 Hint

Check the 'mid (distance)' and 'Can Place?' columns at step 4 in execution_table.

At which step does the condition 'low > high' become true, ending the loop?

A Step 12

B Step 10

C Step 8

D Step 13

💡 Hint

Look at the 'low' and 'high' values in execution_table rows and find when low exceeds high.

If the number of cows to place was 2 instead of 3, how would the maximum minimum distance change?

A It would stay the same as 4

B It would decrease because fewer cows need less space

C It would increase, possibly up to the largest gap between stalls

D It would be zero

💡 Hint

Refer to how 'Can Place?' changes with distance and number of cows in variable_tracker and execution_table.

Concept Snapshot

Aggressive Cows Problem:
- Sort stall positions
- Use binary search on distance (low, high)
- Check if cows fit with mid distance
- If yes, increase low to mid+1
- If no, decrease high to mid-1
- Loop ends when low > high
- 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 possible distance. 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 + 1. If no, we try smaller distances by setting high to mid - 1. 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.