Data Structures and Algorithms (DSA)  

Aggressive Cows Problem Using Binary Search

Introduction

The Aggressive Cows problem is a famous DSA interview question and a classic example of Binary Search on Answer. At first glance, it looks confusing because it talks about cows and stalls, not numbers.

In simple words, this problem asks you to place cows as far apart as possible so that they do not fight.

This article explains the problem in simple, human language, with real-world meaning, clear logic, and the exact approach interviewers expect.

Real-World Meaning of Aggressive Cows

Imagine placing people on chairs in a long hall:

  • Chairs are fixed at certain positions

  • People do not like sitting too close

  • You want to place everyone so that the minimum distance between any two people is as large as possible

This is exactly what the Aggressive Cows problem is about.

Problem Statement

You are given:

  • Positions of stalls on a line (array of integers)

  • A number k representing cows

Rules:

  • Each stall can hold only one cow

  • Cows should be placed to maximize the minimum distance between any two cows

Example

Stalls: [1, 2, 4, 8, 9]
Cows:   3

Output

Maximum minimum distance = 3

Explanation:

  • Place cows at positions 1, 4, and 8

  • Minimum distance between cows = 3

Before vs After Understanding

Brute Force Thinking (Before)

  • Try all possible placements

  • Calculate minimum distance

  • Extremely slow

Binary Search Thinking (After)

  • Guess a minimum distance

  • Check if placement is possible

  • Adjust guess using binary search

Why Binary Search Works Here

Binary search works because:

  • If cows can be placed with distance d

  • They can also be placed with any distance smaller than d

This monotonic behavior allows binary search on distance.

What Interviewers Are Actually Testing

Interviewers want to see:

  • Can you apply binary search on answer?

  • Can you convert story problems into logic?

  • Can you design a feasibility check?

This problem tests problem modeling and optimization skills.

Key Idea (Very Simple)

  • Sort the stall positions

  • The smallest distance is 1

  • The largest distance is the difference between last and first stall

  • Use binary search to find the best distance

Step-by-Step Logic

  1. Sort the stall positions

  2. Set low = 1, high = last - first

  3. Find mid (possible minimum distance)

  4. Check if cows can be placed with at least mid distance

  5. If possible, move right to try bigger distance

  6. If not possible, move left

Feasibility Check (Very Important)

To check if distance d is possible:

  • Place first cow in the first stall

  • Place next cow in the next stall at least d away

  • Continue until all cows are placed or stalls end

If all cows are placed, distance is possible.

Dry Run Example

Stalls: [1, 2, 4, 8, 9], Cows = 3

lowhighmidpossible?move
184noleft
132yesright
333yesright

Answer = 3

One-Line Logic Before Code

Use binary search to maximize the minimum distance.

Code Implementation (C++)

bool canPlaceCows(vector<int>& stalls, int cows, int dist) {
    int count = 1;
    int lastPos = stalls[0];

    for (int i = 1; i < stalls.size(); i++) {
        if (stalls[i] - lastPos >= dist) {
            count++;
            lastPos = stalls[i];
        }
        if (count == cows)
            return true;
    }
    return false;
}

int aggressiveCows(vector<int>& stalls, int cows) {
    sort(stalls.begin(), stalls.end());
    int low = 1;
    int high = stalls.back() - stalls.front();
    int ans = 0;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (canPlaceCows(stalls, cows, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return ans;
}

Common Beginner Mistakes

  • Forgetting to sort stall positions

  • Wrong low and high values

  • Not understanding feasibility check

Time and Space Complexity

  • Time Complexity: O(n log n)

  • Space Complexity: O(1)

Easy Summary (Explain Like I’m 10)

If cows don’t like standing close, we try placing them far apart. We guess a distance and check if it works. By guessing smartly using binary search, we find the largest distance where all cows can fit.

Summary

The Aggressive Cows problem is a classic example of binary search on answer where the goal is to maximize the minimum distance between placed elements. By sorting stall positions, performing a feasibility check, and narrowing the search space using binary search, you can solve this problem efficiently. This problem is frequently asked in interviews and is essential for mastering optimization-based binary search patterns in DSA.

Membership not found