Aggressive Cows | GeeksforGeeks Solution Explained | Binary Search

The “Aggressive Cows” problem is a classic binary search question that is often asked in coding interviews.

It teaches you how to optimize placement problems using binary search. In this blog, we’ll explain the problem, walk you through both brute force and optimal solutions, and make everything easy to understand with code comments, dry runs, and clear explanations.

Here’s the [Problem Link] to begin with.

Problem Statement

You are given an array with unique elements of stalls[], which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. Your task is to assign stalls to k cows such that the minimum distance between any two of them is the maximum possible.

Examples :

Input: stalls[] = [1, 2, 4, 8, 9], k = 3
Output: 3
Explanation: The first cow can be placed at stalls[0], 
the second cow can be placed at stalls[2] and 
the third cow can be placed at stalls[3]. 
The minimum distance between cows, in this case, is 3, which also is the largest among all possible ways.

Input: stalls[] = [10, 1, 2, 7, 5], k = 3
Output: 4
Explanation: The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4, which also is the largest among all possible ways.

Input: stalls[] = [2, 12, 11, 3, 26, 7], k = 5
Output: 1
Explanation: Each cow can be placed in any of the stalls, as the no. of stalls are exactly equal to the number of cows.
The minimum distance between cows, in this case, is 1, which also is the largest among all possible ways.

Constraints:
2 <= stalls.size() <= 10⁶
0 <= stalls[i] <= 10⁸
2 <= k <= stalls.size()

Brute Force Solution (Try Every Possible Distance)

Intuition and Approach

Let’s solve the problem in the most straightforward way:

1. Try Every Distance:
   Try every possible minimum distance from 1 up to the maximum possible (difference between the farthest and closest stall).
2. Check If Placement Is Possible:
   For each distance, check if it is possible to place all cows with at least that much distance between them.
3. Return the Largest Valid Distance:
   The largest distance for which placement is possible is our answer.
4. Why does this work?
   We check every possible distance, so we’re sure to find the largest one that works.

This approach is easy to understand but not efficient for large inputs.

Code Implementation

class Solution:

    def canWePlace(self, stalls, dist, cows):
        # Size of array
        n = len(stalls)

        # Number of cows placed
        cntCows = 1

        # Position of last placed cow
        last = stalls[0]
        for i in range(1, n):
            if stalls[i] - last >= dist:
                # Place next cow
                cntCows += 1

                # Update the last location
                last = stalls[i]
            if cntCows >= cows:
                return True

        return False

    def aggressiveCows(self, stalls, k):
        # Size of list
        n = len(stalls)

        # Sort the nums
        stalls.sort()

        limit = stalls[-1] - stalls[0]
        for i in range(1, limit + 1):
            if not self.canWePlace(stalls, i, k):
                return i - 1

        # Return the answer
        return limit

Code Explanation

• For each possible distance from 1 to the maximum possible, check if you can place all cows.
• The helper function canWePlace tries to place cows with at least dist distance apart.
• Return the largest distance for which placement is possible.

Dry Run

Input:
stalls = [1], k = 3

• Try distance = 1: possible
• Try distance = 2: possible
• Try distance = 3: possible
• Try distance = 4: not possible (can’t place all cows)
• Return 3

Final Output:
3

Time and Space Complexity

• Time Complexity: O((max(stalls) – min(stalls)) * n)
  For each distance, we check all stalls.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The brute force approach is simple and works for small inputs, but it’s too slow for large values.

Optimal Solution (Binary Search)

Intuition and Approach

We can do much better using binary search:

1. Binary Search on Distance:
   The answer lies between 1 and the difference between the farthest and closest stall. Use binary search to find the largest minimum distance.
2. Check If Placement Is Possible:
   For each mid value (distance), check if it’s possible to place all cows.
3. Adjust Search Window:
   • If placement is possible, try a larger distance.
   • If not, try a smaller distance.
4. Why does this work?
   The placement function is monotonic: as the distance increases, it becomes harder to place all cows. Binary search is perfect for this.

Code Implementation

class Solution:

    def canWePlace(self, stalls, dist, cows):
        # Size of array
        n = len(stalls)

        # Number of cows placed
        cntCows = 1

        # Position of last placed cow
        last = stalls[0]
        for i in range(1, n):
            if stalls[i] - last >= dist:
                # Place next cow
                cntCows += 1

                # Update the last location
                last = stalls[i]
            if cntCows >= cows:
                return True

        return False

    def aggressiveCows(self, stalls, k):
        # Sort the stalls to place cows in sorted positions
        stalls.sort()

        # Binary search for the maximum minimum distance
        low = 1  # Minimum possible distance
        high = stalls[-1] - stalls[0]  # Maximum possible distance

        result = 0

        while low <= high:
            mid = (low + high) // 2  # Try this distance

            if self.canWePlace(stalls, mid, k):
                # If we can place cows with at least `mid` distance, try for a larger distance
                result = mid
                low = mid + 1
            else:
                # If we can't place cows with at least `mid` distance, try for a smaller distance
                high = mid - 1

        return result

Code Explanation

• Use binary search between 1 and the maximum possible distance.
• For each mid distance, check if you can place all cows.
• If you can, store the distance and try a larger one.
• If not, try a smaller distance.
• Return the largest valid distance found.

Dry Run

Input:
stalls = [1], k = 3

• low = 1, high = 8
• mid = 4: can’t place all cows → high = 3
• mid = 2: can place all cows → result = 2, low = 3
• mid = 3: can place all cows → result = 3, low = 4

Loop ends, answer is 3.

Time and Space Complexity

• Time Complexity: O(n * log(max(stalls) – min(stalls)))
  Binary search on distance, checking all stalls for each guess.
• Space Complexity: O(1)
  Only variables for counting.

Conclusion

The optimal solution is efficient and works well for large arrays and high values. It’s the best approach for interviews and practical use.

Final Thoughts

The “Aggressive Cows” problem is a great example of how to optimize from brute force to an efficient binary search solution. Start with brute force to understand the basics, then use binary search for best performance.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.