Aggressive Cows Maximum Minimum Distance in DSA Java

Mental Model

We want to place cows in stalls so that the smallest distance between any two cows is as large as possible.

Analogy: Imagine placing friends in seats along a bench so that everyone has as much personal space as possible.

Stalls: [1] -> [2] -> [4] -> [8] -> [9]
Cows placed: C -> null (positions chosen to maximize minimum gap)

Dry Run Walkthrough

Input: stalls: [1, 2, 4, 8, 9], cows: 3

Goal: Place 3 cows in stalls so that the minimum distance between any two cows is as large as possible.

Step 1: Sort stalls to [1, 2, 4, 8, 9]

[1] -> [2] -> [4] -> [8] -> [9]

Why: Sorting helps check distances in order.

Step 2: Set search range low=1, high=8 (max distance between first and last stall)

low=1, high=8

Why: We try distances between 1 and 8.

Step 3: Check mid = (1+8)//2 = 4; try placing cows with min distance 4

Trying distance=4

Why: Test if cows can be placed with at least 4 apart.

Step 4: Place first cow at stall 1

Placed cow at 1

Why: Start placing from first stall.

Step 5: Place second cow at stall 8 (distance 7 from 1)

Cows at 1 and 8

Why: 8 is at least 4 away from 1.

Step 6: Place third cow at stall 9 (distance 1 from 8, less than 4) - cannot place here, try next

Only 2 cows placed, third not placed

Why: 9 is too close to 8, no more stalls left.

Step 7: Cannot place all 3 cows with distance 4, reduce high to mid-1=3

low=1, high=3

Why: Try smaller distance.

Step 8: Check mid = (1+3)//2 = 2; try placing cows with min distance 2

Trying distance=2

Why: Test if cows can be placed with at least 2 apart.

Step 9: Place cows at stalls 1, 4, and 8 successfully

Cows at 1, 4, 8

Why: All cows placed with min distance 2.

Step 10: Increase low to mid+1=3 to try larger distance

low=3, high=3

Why: Try bigger distance.

Step 11: Check mid = (3+3)//2 = 3; try placing cows with min distance 3

Trying distance=3

Why: Test if cows can be placed with at least 3 apart.

Step 12: Place cows at stalls 1, 4, and 8 successfully

Cows at 1, 4, 8

Why: All cows placed with min distance 3.

Step 13: Increase low to mid+1=4

low=4, high=3

Why: Try bigger distance but low > high ends search.

Result:

Final answer: maximum minimum distance = 3
Cows placed at stalls 1, 4, and 8

Annotated Code

DSA Java

import java.util.Arrays;

public class AggressiveCows {

    // Check if it is possible to place cows with at least 'distance' apart
    static boolean canPlaceCows(int[] stalls, int cows, int distance) {
        int count = 1; // place first cow at first stall
        int lastPosition = stalls[0];

        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPosition >= distance) {
                count++; // place another cow
                lastPosition = stalls[i];
                if (count == cows) {
                    return true; // all cows placed
                }
            }
        }
        return false; // not all cows placed
    }

    // Find maximum minimum distance
    static int maxMinDistance(int[] stalls, int cows) {
        Arrays.sort(stalls); // sort stalls

        int low = 1; // minimum possible distance
        int high = stalls[stalls.length - 1] - stalls[0]; // max possible distance
        int result = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2; // middle distance

            if (canPlaceCows(stalls, cows, mid)) {
                result = mid; // update result
                low = mid + 1; // try for bigger distance
            } else {
                high = mid - 1; // try smaller distance
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] stalls = {1, 2, 4, 8, 9};
        int cows = 3;

        int maxDistance = maxMinDistance(stalls, cows);
        System.out.println("Maximum minimum distance: " + maxDistance);
    }
}

Arrays.sort(stalls); // sort stalls

sort stalls to check distances in order

int low = 1; int high = stalls[stalls.length - 1] - stalls[0];

set search range for minimum distance

while (low <= high) { int mid = low + (high - low) / 2;

binary search over possible distances

if (canPlaceCows(stalls, cows, mid)) { result = mid; low = mid + 1; }

if placement possible, try bigger distance

else { high = mid - 1; }

if not possible, try smaller distance

int count = 1; int lastPosition = stalls[0];

place first cow at first stall

if (stalls[i] - lastPosition >= distance) { count++; lastPosition = stalls[i]; }

place next cow if distance condition met

if (count == cows) { return true; }

all cows placed successfully

Output

Maximum minimum distance: 3

Complexity Analysis

Time: O(n log d) because we sort n stalls and binary search over distance d, checking placement in O(n) each time

Space: O(1) because we use only fixed extra space besides input

vs Alternative: Naive approach tries all distances linearly, costing O(n*d), which is slower than binary search

Edge Cases

Only one stall

Can place only one cow, max distance is 0

DSA Java

int high = stalls[stalls.length - 1] - stalls[0];

Number of cows equals number of stalls

Cows placed in every stall, min distance is minimum gap between adjacent stalls

DSA Java

if (count == cows) { return true; }

All stalls at same position

Max distance is 0 because no space between stalls

DSA Java

int high = stalls[stalls.length - 1] - stalls[0];

When to Use This Pattern

When asked to maximize minimum distance between placed items in sorted positions, use binary search on distance with a feasibility check.

Common Mistakes

Mistake: Not sorting stalls before binary searching distances
Fix: Always sort stalls first to check distances in order

Mistake: Checking placement incorrectly by not updating last placed position
Fix: Update lastPosition only when a cow is placed to maintain correct distance checks

Summary

Find the largest minimum distance to place cows in stalls.

Use when you need to maximize minimum spacing between items in sorted positions.

Binary search on distance combined with a greedy feasibility check is the key insight.

Practice

1. What is the main goal of the Aggressive Cows Maximum Minimum Distance problem?

easy

A. To place cows in stalls so that the minimum distance between any two cows is maximized

B. To find the maximum number of cows that can fit in a single stall

C. To minimize the total distance cows travel between stalls

D. To arrange cows so that all are placed in consecutive stalls

Solution

1. Step 1: Understand the problem objective

   The problem asks to place cows in stalls such that the smallest distance between any two cows is as large as possible.

2. Step 2: Identify the key goal

   This means maximizing the minimum distance between cows, not minimizing or counting cows in one stall.

3. Final Answer:

   To place cows in stalls so that the minimum distance between any two cows is maximized -> Option A

4. Quick Check:

   Maximize minimum distance = place cows far apart [OK]

Hint: Maximize the smallest gap between cows placed [OK]

Common Mistakes:

• Thinking the goal is to minimize distance
• Trying to put all cows in one stall
• Confusing maximum distance with maximum number of cows

2. Which of the following Java code snippets correctly initializes the binary search boundaries for the aggressive cows problem given an array stalls sorted in ascending order?

easy

A. int low = stalls.length; int high = stalls[0];

B. int low = 0; int high = stalls[stalls.length - 1] - stalls[0];

C. int low = 1; int high = stalls.length;

D. int low = stalls[0]; int high = stalls[stalls.length - 1];

Solution

1. Step 1: Determine the search space for distance

   The minimum distance can be 0 and maximum distance is the difference between the last and first stall positions.

2. Step 2: Set binary search boundaries accordingly

   So, low = 0 and high = stalls[stalls.length - 1] - stalls[0] correctly sets the search range.

3. Final Answer:

   int low = 0; int high = stalls[stalls.length - 1] - stalls[0]; -> Option B

4. Quick Check:

   Distance range = 0 to max stall gap [OK]

Hint: Low = 0, High = max stall position difference [OK]

Common Mistakes:

• Setting low or high to stall positions instead of distances
• Using stall count as high boundary
• Reversing low and high values

3. Given the sorted stalls array [1, 2, 8, 12, 17] and 3 cows, what is the maximum minimum distance between any two cows?

medium

A. 5

B. 6

C. 8

D. 7

Solution

1. Step 1: Check feasibility for distances

   Try placing cows with minimum distance 7: Place first cow at 1, second at 8 (distance 7), third at 17 (distance 9). All distances >= 7, so 7 is possible.

2. Step 2: Check if larger distance is possible

   Try 8: Place first at 1, second at 8 (distance 7) fails, so 8 not possible. Therefore, 7 is possible but we need to check if 6 is also possible.

3. Step 3: Check 6

   Try 6: Place first at 1, second at 8 (distance 7), third at 17 (distance 9). All distances >= 6, so 6 is possible.

4. Step 4: Maximum minimum distance is 7, but since 7 is possible, the maximum minimum distance is 7.

5. Final Answer:

   7 -> Option D

6. Quick Check:

   Max min distance = 7 [OK]

Hint: Test distances by placing cows greedily [OK]

Common Mistakes:

• Choosing the largest stall difference directly
• Not verifying placement feasibility
• Confusing maximum distance with stall count

4. Identify the error in this Java method snippet for checking if cows can be placed with at least dist distance:

boolean canPlace(int[] stalls, int cows, int dist) {
  int count = 1, lastPos = stalls[0];
  for (int i = 1; i < stalls.length; i++) {
    if (stalls[i] - lastPos >= dist) {
      count++;
      lastPos = stalls[i];
    }
  }
  return count >= cows;
}

medium

A. No error; the method correctly checks placement feasibility

B. The initial count should be 0 instead of 1

C. The loop should start from i = 0 instead of i = 1

D. The return condition should be count > cows instead of count >= cows

Solution

1. Step 1: Analyze initial count and last position

   Count starts at 1 because first cow is placed at stalls[0]. lastPos is set to stalls[0] correctly.

2. Step 2: Check loop and return condition

   Loop starts at 1 to check next stalls. If distance condition meets, count increments. Return true if count >= cows means enough cows placed.

3. Final Answer:

   No error; the method correctly checks placement feasibility -> Option A

4. Quick Check:

   Initial count 1 and correct loop start [OK]

Hint: First cow placed before loop; count starts at 1 [OK]

Common Mistakes:

• Starting count at 0 causing off-by-one error
• Loop starting at 0 causing redundant check
• Using > instead of >= in return condition

5. You have stalls at positions [0, 7, 14, 21, 28] and 4 cows. Using binary search, what is the maximum minimum distance you can place the cows apart?

hard

A. 5

B. 6

C. 7

D. 8

Solution

1. Step 1: Set binary search boundaries

   Minimum distance low = 0, high = 28 - 0 = 28.

2. Step 2: Use binary search to find max min distance

   Check mid = 7: Place cows at 0, 7 (distance 7), 14 (7), 21 (7). Cows placed: 4 successfully.

3. Step 3: Try higher distance 8

   Place cows at 0, 14 (14), 28 (14) only 3 cows placed, fails.

4. Final Answer:

   7 -> Option C

5. Quick Check:

   Max min distance = 7 by binary search [OK]

Hint: Use binary search on distance, check feasibility each step [OK]

Common Mistakes:

• Not updating binary search boundaries correctly
• Miscounting cows placed at each distance
• Choosing distance without feasibility check