Aggressive Cows

Intuition

Binary search on the minimum distance between any two cows. For a given minimum distance d, greedily check if k cows can be placed: place first cow at stall 0, then each next cow at the first stall at distance â‰¥ d from the previous.

Algorithm

1Sort stalls.
2Binary search lo=1, hi=stalls[n-1]âˆ’stalls[0].
3For each mid: check if k cows can be placed with min distance mid.
4Canplace(d): place first cow at stalls[0]. For each stall: if gap â‰¥ d, place cow here, count++. Return count >= k.
5If canplace(mid): lo=mid+1 (try larger). Else: hi=midâˆ’1.
6Return loâˆ’1.

Example Walkthrough

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

1.lo=1,hi=8. mid=4: place at 1,4? gap=3<4. mid=3: place at 1,4,8. 3 cows âœ“ â†’ lo=4.
2.mid=6: can we? 1,8(gap=7â‰¥6),next? No more. Only 2 â†’ hi=5.
3.mid=4: same â†’ lo=5. lo>hi. Answer=4.

Output: 3 (minimum distance = 3)

Common Pitfalls

•Sort stalls first. Binary search on the ANSWER (distance), not the index.

Aggressive Cows.java

Java

// Approach: Binary search on the minimum distance between cows.
// For a given distance, greedily check if we can place all k cows in sorted stalls.
// Time: O(n log(max-min)) Space: O(1)
class Solution {
    public static int aggressiveCows(int[] stalls, int k) {
        Arrays.sort(stalls); // Sort stall positions to enable binary search
        int low = 1; // Minimum possible distance
        int high = stalls[stalls.length - 1] - stalls[0]; // Maximum possible distance
        int result = 0;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (canPlaceCows(stalls, k, mid)) {
                result = mid; // Update the result as we have a valid configuration
                low = mid + 1; // Try for a larger minimum distance
            } else
                high = mid - 1; // Reduce the search space
        }

        return result;
    }

    private static boolean canPlaceCows(int[] stalls, int cows, int minDis) {
        int count = 1; // Place the first cow at the first stall
        int lastPosition = stalls[0];

        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPosition >= minDis) {
                count++; // Place another cow
                lastPosition = stalls[i];
                if (count == cows)
                    return true; // If all cows are placed, return true
            }
        }

        return false;
    }
}

Was this solution helpful?