Aggressive Cows Maximum Minimum Distance in DSA Rust

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 -> C -> null -> C

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 stall positions to [1, 2, 4, 8, 9]

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

Why: We need sorted stalls to check distances in order.

Step 2: Set search range for distance: low=1, high=8 (max-min)

low=1, high=8

Why: We try distances between 1 and 8 to find max minimum distance.

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

Trying distance=4

Why: Midpoint helps binary search the answer.

Step 4: Place first cow at stall 1

Placed cow at 1

Why: Start placing cows from first stall.

Step 5: Skip stall 2 (dist 1 <4) and stall 4 (dist 3 <4)

Still only cow at 1

Why: Need at least 4 distance, stalls 2 and 4 too close.

Step 6: Place next cow at stall 8 (dist 7 from 1 >=4)

Cows at 1, 8

Why: Placed second cow with sufficient distance.

Step 7: stall 9 (dist 1 <4) skip; only 2 cows placed

low=1, high=3

Why: Distance 4 not possible, try smaller distance.

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

Trying distance=2

Why: Check if distance works.

Step 9: Place first at 1, skip 2 (1<2), place at 4 (3>=2), place at 8 (4>=2)

Cows at 1, 4, 8; all 3 placed

Why: Can place all cows with min distance 2.

Step 10: Distance 2 possible, update result=2, low=3

low=3, high=3

Why: Try bigger distance to maximize minimum.

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

Trying distance=3

Why: Check if larger distance works.

Step 12: Place first at 1, skip 2 (1<3), place at 4 (3>=3), place at 8 (4>=3)

Cows at 1, 4, 8; all 3 placed

Why: Can place all cows with min distance 3.

Step 13: Distance 3 possible, update result=3, low=4

low=4, high=3

Why: Search ends because low > high.

Result:

Maximum minimum distance = 3
Final placement: cows at stalls 1, 4, 8

Annotated Code

DSA Rust

use std::io;

fn can_place_cows(stalls: &Vec<i32>, cows: i32, dist: i32) -> bool {
    let mut count = 1; // place first cow at first stall
    let mut last_position = stalls[0];
    for &stall in stalls.iter().skip(1) {
        if stall - last_position >= dist {
            count += 1; // place another cow
            last_position = stall;
            if count == cows {
                return true; // all cows placed
            }
        }
    }
    false
}

fn aggressive_cows_max_min_distance(mut stalls: Vec<i32>, cows: i32) -> i32 {
    stalls.sort(); // sort stalls
    let mut low = 1;
    let mut high = stalls[stalls.len() - 1] - stalls[0];
    let mut result = 0;

    while low <= high {
        let mid = (low + high) / 2;
        if can_place_cows(&stalls, cows, mid) {
            result = mid; // mid distance possible
            low = mid + 1; // try bigger distance
        } else {
            high = mid - 1; // try smaller distance
        }
    }
    result
}

fn main() {
    let stalls = vec![1, 2, 4, 8, 9];
    let cows = 3;
    let max_distance = aggressive_cows_max_min_distance(stalls, cows);
    println!("Maximum minimum distance = {}", max_distance);
}

stalls.sort(); // sort stalls

sort stalls to check distances in order

while low <= high {

binary search over possible distances

if can_place_cows(&stalls, cows, mid) {

check if mid distance is possible

result = mid; // mid distance possible

update result with feasible distance

low = mid + 1; // try bigger distance

try to maximize minimum distance

high = mid - 1; // try smaller distance

reduce distance if mid not possible

for &stall in stalls.iter().skip(1) {

iterate stalls to place cows

if stall - last_position >= dist {

place 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(n) for storing stall positions

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

Edge Cases

Only one stall

Place one cow only, max distance is 0

DSA Rust

if count == cows { return true; }

Number of cows equals number of stalls

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

DSA Rust

if stall - last_position >= dist {

All stalls at same position

Max distance is 0 because no space between stalls

DSA Rust

stalls.sort();

When to Use This Pattern

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

Common Mistakes

Mistake: Not sorting stalls before binary searching distances
Fix: Always sort stalls first to ensure correct distance checks

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

Summary

Find the largest minimum distance to place cows in stalls.

Use when you want to spread items evenly with maximum minimum gap.

Binary search on distance combined with greedy placement 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 as large as possible

B. To place cows in stalls so that the maximum distance between any two cows is as small as possible

C. To find the total number of cows that can fit in all stalls

D. To calculate the average distance between all cows placed in stalls

Solution

1. Step 1: Understand the problem objective

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

2. Step 2: Clarify the goal

   This means maximizing the minimum distance between cows, ensuring they are as far apart as possible.

3. Final Answer:

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

4. Quick Check:

   Maximize minimum distance = To place cows in stalls so that the minimum distance between any two cows is as large as possible [OK]

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

Common Mistakes:

• Confusing maximum minimum distance with minimum maximum distance
• Thinking the problem is about total cows fitting
• Assuming average distance is the goal

2. Which of the following Rust code snippets correctly sorts the stall positions stored in a vector stalls for the Aggressive Cows problem?

easy

A. stalls.sort_by(|a, b| b.cmp(a));

B. stalls.sorted();

C. stalls.sort();

D. stalls.order();

Solution

1. Step 1: Identify the correct Rust method to sort a vector

   In Rust, the method sort() sorts a vector in ascending order in place.

2. Step 2: Check other options

   sorted() does not exist on vectors, sort_by with reversed order sorts descending, and order() is invalid.

3. Final Answer:

   stalls.sort(); -> Option C

4. Quick Check:

   Use sort() to sort vector in Rust [OK]

Hint: Use stalls.sort() to sort vector ascending in Rust [OK]

Common Mistakes:

• Using non-existent methods like sorted()
• Sorting in descending order by mistake
• Trying to assign result of sort() which returns ()

3. Given the Rust code below, what is the output printed?

let stalls = vec![1, 2, 8, 4, 9];
let cows = 3;

let mut sorted_stalls = stalls.clone();
sorted_stalls.sort();

fn can_place_cows(stalls: &Vec<i32>, cows: i32, dist: i32) -> bool {
    let mut count = 1;
    let mut last_pos = stalls[0];
    for &pos in stalls.iter().skip(1) {
        if pos - last_pos >= dist {
            count += 1;
            last_pos = pos;
            if count == cows {
                return true;
            }
        }
    }
    false
}

let mut low = 1;
let mut high = sorted_stalls[sorted_stalls.len() - 1] - sorted_stalls[0];
let mut result = 0;

while low <= high {
    let mid = (low + high) / 2;
    if can_place_cows(&sorted_stalls, cows, mid) {
        result = mid;
        low = mid + 1;
    } else {
        high = mid - 1;
    }
}

println!("{}", result);

medium

A. 4

B. 6

C. 5

D. 3

Solution

1. Step 1: Sort stalls and set search range

   Sorted stalls: [1, 2, 4, 8, 9]. Search distance range low=1, high=8 (9-1).

2. Step 2: Binary search for max minimum distance

   mid=4: places 1,8 (count=2<3) fails, high=3.
   mid=2: places 1,4,8 succeeds, result=2, low=3.
   mid=3: places 1,4,8 (dists 3,4 >=3) succeeds, result=3, low=4>3 end. Prints 3.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   Max min distance = 3 [OK]

Hint: Binary search distances, check feasibility with can_place_cows [OK]

Common Mistakes:

• Not sorting stalls before binary search
• Incorrect binary search boundaries
• Miscounting cows placed in can_place_cows

4. Identify the bug in the following Rust function used in the Aggressive Cows problem and select the correct fix:

fn can_place_cows(stalls: &Vec<i32>, cows: i32, dist: i32) -> bool {
    let mut count = 0;
    let mut last_pos = stalls[0];
    for &pos in stalls.iter() {
        if pos - last_pos >= dist {
            count += 1;
            last_pos = pos;
            if count == cows {
                return true;
            }
        }
    }
    false
}

medium

A. Initialize count to cows instead of 0

B. Both A and B

C. Start loop from stalls.iter().skip(1) instead of stalls.iter()

D. No bug, function is correct

Solution

1. Step 1: Analyze initial count and loop start

   Count should start at 1 because first cow is placed at stalls[0]. Loop should skip first stall to avoid counting it twice.

2. Step 2: Fix both initialization and loop

   Set count = 1 and loop with stalls.iter().skip(1) to correctly count cows placed.

3. Final Answer:

   Both A and B -> Option B

4. Quick Check:

   Count=1 and skip first stall in loop [OK]

Hint: Start count at 1 and skip first stall in loop [OK]

Common Mistakes:

• Starting count at 0 causes off-by-one error
• Looping from first stall counts first cow twice
• Returning false incorrectly due to wrong count

5. You have stalls at positions [2, 5, 11, 15, 17, 20] and want to place 4 cows. Using the Aggressive Cows approach, what is the maximum minimum distance you can achieve between any two cows?

hard

A. 4

B. 5

C. 7

D. 8

Solution

1. Step 1: Sort stalls and set binary search range

   Stalls sorted: [2, 5, 11, 15, 17, 20]. Low=1, High=18 (20-2).

2. Step 2: Binary search for max minimum distance

   mid=9: place cows at 2,11,20 (3 cows <4) fails, high=8.
   mid=4: place at 2,11,15,20 (dists 9,4,5 >=4, 4 cows) succeeds, result=4, low=5.
   mid=6: 2,11,17 (9,6 >=6, 20-17=3<6, 3 cows) fails, high=5.
   mid=5: 2,11,17 (9,6>=5, 20-17=3<5, 3 cows) fails, high=4.
   Max distance is 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Max min distance = 4 [OK]

Hint: Use binary search and feasibility check to find max distance [OK]

Common Mistakes:

• Not updating binary search bounds correctly
• Misplacing cows during feasibility check
• Assuming max distance equals max stall gap