Aggressive Cows Problem Explained | Binary Search on Answer in C++

1. Problem Statement

In Simple Words: Imagine you have a straight road with several barns (stalls) located at specific coordinates. You also have a specific number of cows. These cows are very aggressive. If you put them too close to each other, they will fight. Your goal is to place all the cows into the stalls in such a way that the distance between the two closest cows is as large as possible.

Original Problem Statement:

Given an array of length $N$, where each element denotes the coordinate of a stall, and an integer $C$ representing the number of aggressive cows, assign the cows to the stalls such that the minimum distance between any two cows is maximized.

Input Format:

• An integer array stalls[] of size $N$ representing the coordinates of the stalls.
• An integer $C$ representing the number of cows.

Output Format:

• A single integer representing the maximum possible minimum distance between any two cows.

Constraints:

• $2 \le N \le 10^5$
• $2 \le C \le N$
• $0 \le stalls[i] \le 10^9$

2. Examples

Let's look at a few examples to understand how the placement works in practice.

Example 1

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

Output: 3

Step-by-Step Explanation:

1. First, sort the stalls: [1, 2, 4, 8, 9].
2. We need to place 3 cows.
3. Let's try placing them at indices 0, 2, and 3 (coordinates 1, 4, 8).
4. The distances between adjacent cows are:
   • Between 1 and 4: $4 - 1 = 3$
   • Between 4 and 8: $8 - 4 = 4$
5. The minimum of these distances is 3. We cannot achieve a minimum distance greater than 3. For instance, if we placed them at 1, 4, and 9, the minimum distance is still 3.

Example 2

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

Output: 8

Step-by-Step Explanation:

1. The stalls are already sorted.
2. We only need to place 2 cows. To maximize their distance, we put them at the two extremes.
3. Place cow 1 at coordinate 1.
4. Place cow 2 at coordinate 9.
5. The distance is $9 - 1 = 8$.

Example 3 (Edge Case)

Input: stalls = [1, 10], C = 2

Output: 9

Step-by-Step Explanation:

1. Only two stalls and two cows.
2. Cow 1 goes to stall 1. Cow 2 goes to stall 10.
3. Distance is $10 - 1 = 9$. This shows that the answer can simply be the difference between the maximum and minimum elements if $C = 2$.

3. Key Observations

Before jumping into solutions, we need to extract the hidden truths of the problem:

• Order Matters (Sorting is mandatory): Distance is calculated between adjacent elements on a 1D line. Without sorting, evaluating the distance between physically adjacent stalls is impossible. Sorting brings spatial order to the data.
• "Maximizing the Minimum": Whenever an interview question asks you to maximize a minimum value (or minimize a maximum value), it is a massive hint that you will be dealing with a Binary Search on Answer pattern.
• The Greedy Choice: If you want to place cows as far apart as possible, it always makes sense to put the very first cow in the very first stall. By doing this, you leave the maximum possible amount of runway on the right side to accommodate the remaining cow

4. Intuition

Let's build the intuition without immediately throwing technical jargon at the problem.

Why is checking every combination inefficient?

Imagine choosing $C$ stalls out of $N$ stalls. Mathematically, this is "$N$ choose $C$" or $\binom{N}{C}$. For $N = 10^5$, checking every single arrangement of cows is astronomically large. We need a way to bypass combinations altogether.

Why does the answer lie within a fixed range?

Think about the possible distances:

• What is the absolute smallest distance between any two cows? Assuming stalls can be adjacent, the minimum possible distance is 1 (or the smallest difference between any two sorted stalls).
• What is the absolute largest distance? The distance between the first stall and the last stall.

Therefore, our answer must be a number between $1$ and $(max\_stall - min\_stall)$.

Feasibility Checking (The "Can we do it?" question)

Instead of asking "What is the max distance?", what if we asked a simpler question:

"Given a specific distance $D$, is it possible to place all $C$ cows such that every cow is at least $D$ units apart?"

This is much easier to solve! We can just walk through the sorted stalls and place a cow whenever we find a stall that is $\ge D$ units away from the last cow.

The Monotonic Magic

Let's say our possible distances range from 1 to 10. We ask our feasibility question for each:

• Distance 1? Yes, easily.
• Distance 2? Yes.
• Distance 3? Yes.
• Distance 4? No, the stalls are too cramped.
• Distance 5? No.

The answers always follow a pattern: [Yes, Yes, Yes, No, No, No].

The moment the answer becomes "No", it will forever stay "No" for larger distances. We are looking for the last "Yes". Whenever you have a monotonic function (a sequence of all trues followed by all falses), you can use Binary Search to find the boundary in $O(\log(\text{Search Space}))$ time!

5. Brute Force Solution

Thought Process

If we don't know binary search, how do we solve it? We know the answer lies between 1 and $(max - min)$. We can simply start checking from distance $d = 1$ and keep going up by 1. For every distance, we check if it's possible to place the cows. The last distance that returns true is our answer.

Algorithm

1. Sort the stalls array.
2. Find max_distance = stalls[N-1] - stalls[0].
3. Loop d from 1 to max_distance.
4. For each d, use a helper function canPlaceCows(stalls, C, d) to check if placement is valid.
5. If canPlaceCows returns false, it means distance d is impossible. Because we are increasing d one by one, the previous valid distance d-1 must be the maximum possible minimum distance.
6. Return d-1.
   

CPP CODE:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// Helper function to check if placement is possible
bool canPlaceCows(vector<int>& stalls, int C, int dist) {
    int cowsPlaced = 1;       // Place the first cow
    int lastPos = stalls[0];  // at the very first stall

    for (int i = 1; i < stalls.size(); i++) {
        if (stalls[i] - lastPos >= dist) {
            cowsPlaced++;       // Place the next cow
            lastPos = stalls[i]; // Update the position of the last placed cow
            if (cowsPlaced == C) return true; // We successfully placed all cows
        }
    }
    return false;
}

int aggressiveCowsBruteForce(vector<int>& stalls, int C) {
    sort(stalls.begin(), stalls.end());
    int n = stalls.size();
    
    int max_dist = stalls[n - 1] - stalls[0];
    
    // Linear search on the answer space
    for (int d = 1; d <= max_dist; d++) {
        if (!canPlaceCows(stalls, C, d)) {
            return d - 1; 
        }
    }
    return max_dist; 
}

Dry Run

• Stalls = [1, 2, 4, 8, 9], C = 3. Max distance = 8.
• Try $d=1$: Can place at 1, 2, 4. (Valid)
• Try $d=2$: Can place at 1, 4, 8. (Valid)
• Try $d=3$: Can place at 1, 4, 8. (Valid)
• Try $d=4$: Place at 1. Next $\ge 5$ is 8. Place at 8. Next $\ge 12$ doesn't exist. Only placed 2 cows. (Invalid)
• Since $d=4$ failed, answer is 3.

Complexity

• Time Complexity: $O(N \log N)$ for sorting + $O(N \times (Max - Min))$ for the linear search. In the worst case, $Max - Min$ is $10^9$, making this $O(N \times 10^9)$, which will result in a Time Limit Exceeded (TLE) error.
• Space Complexity: $O(1)$ auxiliary space.

Drawbacks

The linear search is simply too slow when coordinates are large.

Optimal Solution (Binary Search on Answer)

Instead of a linear search, we use Binary Search on the range of possible answers.

Search Space

• Low: 1 (The absolute minimum possible distance).
• High: stalls[N-1] - stalls[0] (The maximum theoretical distance).

Why Binary Search is Valid

As established in the Intuition section, the feasibility predicate is monotonic. It yields a sequence like [True, True, True, False, False]. Binary search is perfect for finding the boundary between True and False in $O(\log(\text{Search Space}))$.

The Logic

1. Calculate mid = low + (high - low) / 2.
2. Check if we can place cows with at least mid distance.
3. If Yes (canPlaceCows is true): This mid is a potential answer. We store it. However, we want to maximize this distance, so we abandon the smaller half and search the right half by setting low = mid + 1.
4. If No (canPlaceCows is false): The distance mid is too large. We can't even place them this far apart, so we certainly can't place them further. We discard the right half by setting high = mid - 1.

8. Feasibility Function in Detail

The core engine of this optimal approach is the canPlaceCows function. Let's break it down:

bool canPlaceCows(vector<int>& stalls, int C, int dist) {
    int cowsPlaced = 1;       
    int lastPos = stalls[0];  
    
    for (int i = 1; i < stalls.size(); i++) {
        if (stalls[i] - lastPos >= dist) {
            cowsPlaced++;       
            lastPos = stalls[i]; 
            if (cowsPlaced == C) return true; 
        }
    }
    return false;
}

• Why sorting is necessary: The for loop sweeps from left to right. This only works if stalls[i] is strictly greater than lastPos. If the array wasn't sorted, we'd be jumping back and forth across the number line.
• Why the first cow is at stalls[0]: This is the greedy choice. By taking the leftmost slot, you consume the least amount of "number line real estate", leaving the maximum possible space for the remaining $C-1$ cows.
• Why placing earlier never hurts: If you decide to put the first cow in stalls[1] instead, you are just shrinking your available search space on the right for absolutely no benefit.

Algorithm

1. Sort the array stalls.
2. Define the search space:
   • low = 1
   • high = stalls[N-1] - stalls[0]
3. Initialize a variable ans = 0.
4. While low <= high:
   • Calculate mid = low + (high - low) / 2.
   • Check if canPlaceCows(stalls, C, mid) is true.
   • If true: Update ans = mid and search right (low = mid + 1).
   • If false: Search left (high = mid - 1).
5. Return ans.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
    // Feasibility function to check if we can place C cows with at least 'dist' gap
    bool canPlaceCows(const vector<int>& stalls, int cows, int dist) {
        int cowsPlaced = 1;       // Always place the first cow
        int lastPos = stalls[0];  // at the very first stall

        for (int i = 1; i < stalls.size(); i++) {
            // If the current stall is far enough from the last placed cow
            if (stalls[i] - lastPos >= dist) {
                cowsPlaced++;
                lastPos = stalls[i];
                
                // If we've successfully placed all cows, return true early
                if (cowsPlaced == cows) {
                    return true;
                }
            }
        }
        // Could not place all cows with the given minimum distance
        return false;
    }

public:
    int aggressiveCows(vector<int>& stalls, int k) {
        // Step 1: Sort the array to process stalls linearly
        sort(stalls.begin(), stalls.end());
        
        int n = stalls.size();
        int low = 1;
        int high = stalls[n - 1] - stalls[0];
        int ans = 0;

        // Step 2: Binary Search on the Answer space
        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (canPlaceCows(stalls, k, mid)) {
                // If possible, store answer and look for a LARGER distance
                ans = mid;
                low = mid + 1;
            } else {
                // If not possible, look for a SMALLER distance
                high = mid - 1;
            }
        }
        
        return ans;
    }
};

Here is the clean, interview-ready implementation:

9. Dry Run of the Optimal Solution

Let's dry run Binary Search.

• stalls = [1, 2, 4, 8, 9], C = 3
• low = 1
• high = 9 - 1 = 8
• ans = 0

Iteration 1:

• mid = 1 + (8 - 1) / 2 = 4
• canPlaceCows(4):
  • Cow 1 at 1.
  • Next needed: $1 + 4 = 5$. Stall 8 works. Cow 2 at 8.
  • Next needed: $8 + 4 = 12$. None left.
  • Total cows placed: 2. Need 3. Result: False.
• Decision: Distance 4 is too large. high = mid - 1 = 3.

Iteration 2:

• low = 1, high = 3.
• mid = 1 + (3 - 1) / 2 = 2
• canPlaceCows(2):
  • Cow 1 at 1.
  • Next needed: $1 + 2 = 3$. Stall 4 works. Cow 2 at 4.
  • Next needed: $4 + 2 = 6$. Stall 8 works. Cow 3 at 8.
  • Total cows placed: 3. Result: True.
• Decision: Distance 2 is possible. Store ans = 2. Try for larger distance. low = mid + 1 = 3.

Iteration 3:

• low = 3, high = 3.
• mid = 3 + (3 - 3) / 2 = 3
• canPlaceCows(3):
  • Cow 1 at 1.
  • Next needed: $1 + 3 = 4$. Stall 4 works. Cow 2 at 4.
  • Next needed: $4 + 3 = 7$. Stall 8 works. Cow 3 at 8.
  • Total cows placed: 3. Result: True.
• Decision: Distance 3 is possible. Update ans = 3. Try for larger. low = mid + 1 = 4.

Termination:

• low (4) is now greater than high (3). Loop breaks.
• Final Answer: 3.

Complexity Analysis

• Sorting Complexity: $O(N \log N)$ where $N$ is the number of stalls.
• Binary Search Complexity: The search space size is $Max - Min$ (let's call this $M$). Binary search takes $O(\log M)$ iterations.
• Feasibility Check Complexity: In each binary search iteration, we run canPlaceCows, which iterates through the array once, taking $O(N)$ time.
• Overall Time Complexity: $O(N \log N + N \log M)$. Given the constraints ($N \le 10^5$, $M \le 10^9$), $N \log M \approx 10^5 \times 30 = 3 \times 10^6$ operations, which easily passes within the 1-second execution limit.
• Auxiliary Space Complexity: $O(1)$ (ignoring the memory used by the sorting algorithm under the hood, which is typically $O(\log N)$ in C++ std::sort).

Correctness Proof

Why are we absolutely sure this works?

1. Greedy Correctness: Suppose an optimal configuration exists where the first cow is not at stalls[0], but at stalls[1]. If we shift this cow back to stalls[0], the distance to the second cow strictly increases or remains the same. Shifting it left frees up space, meaning our greedy strategy of picking the leftmost valid stall will never invalidate a correct placement.
2. Binary Search Correctness: If $D$ is a valid minimum distance, it implies we can place cows at least $D$ apart. Consequently, any distance smaller than $D$ is also valid. If $D$ is invalid, any distance larger than $D$ must also be invalid. This forms a strict boolean sequence (Monotonicity) allowing binary search to flawlessly pinpoint the highest valid $D$.
3. No Answer Skipped: Because we only shrink our bounds after logically proving half the search space is useless, it is mathematically impossible to skip the optimal answer.

Pattern Recognition

How do you know an unseen problem uses this exact logic? Look for the "Binary Search on Answer" pattern.

Indicators:

1. The problem asks you to maximize a minimum or minimize a maximum.
2. The problem involves finding a threshold value (e.g., "least weight capacity", "minimum time").
3. Given a proposed answer, it is much easier to check if it's valid (using a greedy approach) than it is to construct the optimal answer directly.
4. The validity of answers forms a monotonic sequence (e.g., YYYYNNNN or NNNNYYYY).

Problem link: Aggressive Cows | Practice | GeeksforGeeks

video: