Aggressive cows

Problem Statement

Given an array of N stall positions and C cows, assign C cows to N stalls such that the minimum distance between any two cows is maximized. Return this maximum possible minimum distance.

Constraints:

• 2 ≤ N ≤ 10^5
• 2 ≤ C ≤ N
• 0 ≤ stalls[i] ≤ 10^9

Example:

• Input: stalls = [1, 2, 4, 8, 9], cows = 3
• Output: 3
• Explanation: Place cows at positions 1, 4, 8. Minimum distance = min(4-1, 8-4) = 3

Example 2:

• Input: stalls = [10, 1, 2, 7, 5], cows = 3
• Output: 4
• Explanation: Sorted: [1, 2, 5, 7, 10]. Place at 1, 5, 10. Min distance = 4

Approach 1: Brute Force (Try All Distances)

Intuition

Try all possible minimum distances from 1 to (max_position - min_position) and find the maximum distance where we can still place all cows.

Algorithm

1. Sort the stalls array
2. For each possible distance d from 1 to max-min:
   • Check if we can place C cows with at least distance d
3. Return the maximum valid distance

import java.util.*;

public class Solution {
    private boolean canPlaceCows(int[] stalls, int cows, int minDist) {
        int n = stalls.length;
        int cowsPlaced = 1;
        int lastPosition = stalls[0];
        
        for (int i = 1; i < n; i++) {
            if (stalls[i] - lastPosition >= minDist) {
                cowsPlaced++;
                lastPosition = stalls[i];
                
                if (cowsPlaced == cows) {
                    return true;
                }
            }
        }
        
        return cowsPlaced >= cows;
    }
    
    public int aggressiveCows(int[] stalls, int cows) {
        Arrays.sort(stalls);
        int n = stalls.length;
        
        int maxDist = stalls[n - 1] - stalls[0];
        int result = 0;
        
        for (int d = 1; d <= maxDist; d++) {
            if (canPlaceCows(stalls, cows, d)) {
                result = d;
            } else {
                break;
            }
        }
        
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(n² × (max-min)) - Checking each distance takes O(n)
• Space Complexity: O(1) - Only using variables

Approach 2: Binary Search on Answer (Optimal)

Intuition

The answer has a monotonic property: if we can place cows with minimum distance d, we can also place them with any distance < d. This allows us to binary search on the answer.

Key Observations:

1. Minimum possible distance = 1 (adjacent stalls)
2. Maximum possible distance = (stalls[n-1] - stalls[0]) / (cows - 1)
3. If distance d works, try larger; if not, try smaller
4. Greedy placement: always place cow at earliest valid position

Algorithm

1. Sort the stalls array
2. Binary search on distance in range [1, max_dist]
3. For each mid distance, greedily check if placement is possible
4. Maximize the distance

import java.util.*;

public class AggressiveCows {
    private boolean canPlaceCows(int[] stalls, int cows, int minDist) {
        int cowsPlaced = 1;
        int lastPosition = stalls[0];
        
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPosition >= minDist) {
                cowsPlaced++;
                lastPosition = stalls[i];
                
                if (cowsPlaced == cows) {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    public int maxMinDistance(int[] stalls, int cows) {
        Arrays.sort(stalls);
        int n = stalls.length;
        
        int low = 1;
        int high = stalls[n - 1] - stalls[0];
        int result = 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (canPlaceCows(stalls, cows, mid)) {
                result = mid;
                low = mid + 1;  // Try for larger distance
            } else {
                high = mid - 1; // Reduce distance
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        AggressiveCows ac = new AggressiveCows();
        int[] stalls = {1, 2, 4, 8, 9};
        int cows = 3;
        System.out.println(ac.maxMinDistance(stalls, cows));  // Output: 3
    }
}

Dry Run Example

Complexity Analysis

• Time Complexity: O(n log n + n log(max-min))
  • O(n log n) for sorting
  • O(log(max-min)) binary search iterations
  • O(n) for each canPlaceCows check
• Space Complexity: O(1) - Only using variables (excluding sort space)

Similar Problems

Magnetic Force Between Two Balls (LeetCode 1552)

Key Takeaways

1. Binary Search on Answer: When searching for maximum of minimum (or vice versa), binary search on the answer space
2. Monotonic Property: If distance d works, all smaller distances work; if d fails, all larger fail
3. Greedy Verification: Place cows greedily at earliest valid position to maximize chances
4. Search Space: [1, (max - min) / (cows - 1)] is a tighter bound but [1, max - min] also works
5. Pattern Recognition: "Maximize minimum" or "Minimize maximum" often indicates binary search on answer
6. Sorting Prerequisite: Always sort positions before applying binary search
7. Similar Problems: Book allocation, painters partition, split array largest sum