Log inSign up
hardgfgNot Started

Aggressive Cows

Given an array representing positions of stalls and an integer k representing number of aggressive cows, assign cows to stalls such that the minimum distance between any two cows is as large as possible.

Binary Search
Solve on gfg
Lesson

Problem Statement

You are given an array of integers representing the coordinates of stalls on a straight line, and an integer k representing the number of aggressive cows.

Your task is to assign cows to the stalls such that the minimum distance between any two cows is as large as possible. Return this largest minimum distance.

Example 1 · Example 1: Standard Stalls:

Input: stalls = [1, 2, 4, 8, 9], k = 3
Output: 3
Explanation: Place 3 cows at stalls 1, 4, 8 -> distances are 3, 4. Minimum distance is 3.

Example 2 · Example 2: Dense Stalls:

Input: stalls = [10, 1, 2, 7, 5], k = 3
Output: 4
Explanation: Sorted: [1, 2, 5, 7, 10]. Place cows at 1, 5, 10 -> min distance is 4.

Constraints:

  • 2 <= stalls.length <= 105
  • 0 <= stalls[i] <= 109
  • 2 <= k <= stalls.length

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize the canonical 'Maximize the Minimum' binary search pattern.
  • Implement greedy verification for interval placement.
  • Understand why greedy earliest-placement is provably optimal.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Placing k items into positions to maximize the minimum separation.
  • Feasibility predicate canPlace(dist) is monotonic: T T T ... F F.
  • Sorted coordinates.

Algorithmic Decision Tree:

  • Sort stalls.
  • low = 1, high = stalls[n-1] - stalls[0], ans = 1.
  • While low <= high: mid = low + (high - low) / 2.
  • If canPlace(mid, k) -> ans = mid, low = mid + 1.
  • Else -> high = mid - 1.
  • Return ans.

Connected Patterns:

Magnetic Force Between Two BallsBook Allocation ProblemPainter's Partition Problem

1. Linear Distance Check

Intuition

Sort array. Loop distance d from 1 to stalls[n-1] - stalls[0]. Return d - 1 when canPlace(d, k) becomes false.

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Sort stalls array.
  2. Step 2: Loop distance d from 1 upwards.
  3. Step 3: If canPlace(d, k) is false, return d - 1.
  4. Step 4: Return max possible distance.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int aggressiveCows(vector<int>& stalls, int k) {
8 sort(stalls.begin(), stalls.end());
9 int maxDist = stalls.back() - stalls.front();
10 for (int d = 1; d <= maxDist; ++d) {
11 int count = 1, last = stalls[0];
12 for (int i = 1; i < (int)stalls.size(); ++i) {
13 if (stalls[i] - last >= d) {
14 count++;
15 last = stalls[i];
16 }
17 }
18 if (count < k) return d - 1;
19 }
20 return maxDist;
21}
22
23int main() {
24 // Sample driver execution
25 cout << "Execution completed successfully." << endl;
26 return 0;
27}
28

Time & Space Complexity

  • Time complexity: O(n log n + n * (max_stall - min_stall)) — Sorting takes O(n log n), then distance range can be up to 109.
  • Space complexity: O(1) — O(1) memory.

2. Block Jump Search on Distance

Intuition

Sort array. Increment distance by step size sqrt(range) until placement fails, then scan backwards in the step window.

When to apply: When distance domain is moderately sized.

Algorithm

  1. Step 1: Sort stalls array.
  2. Step 2: Step d by S until canPlace(d, k) fails.
  3. Step 3: Scan backwards from d to d - S to find exact max feasible distance.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int aggressiveCowsJump(vector<int>& stalls, int k) {
8 sort(stalls.begin(), stalls.end());
9 int maxDist = stalls.back() - stalls.front();
10 int step = max(1, (int)sqrt(maxDist));
11 auto canPlace = [&](int dist) {
12 int count = 1, last = stalls[0];
13 for (int i = 1; i < (int)stalls.size(); ++i) {
14 if (stalls[i] - last >= dist) {
15 count++;
16 last = stalls[i];
17 }
18 }
19 return count >= k;
20 };
21 int d = 1;
22 while (d <= maxDist && canPlace(d)) d += step;
23 for (int i = d; i >= max(1, d - step); --i) {
24 if (canPlace(i)) return i;
25 }
26 return 1;
27}
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(n log n + n * sqrt(max_dist)) — Takes sqrt(max_dist) distance queries.
  • Space complexity: O(1) — O(1) auxiliary space.

3. Binary Search on Answer (Maximize the Minimum Distance)

Intuition

Sort stalls. Set low = 1, high = stalls[n - 1] - stalls[0], ans = 1. In each step compute mid. If canPlace(mid, k) is true, record ans = mid and search right (low = mid + 1); else search left (high = mid - 1).

When to apply: Standard optimal solution required in competitive programming and interviews.

Algorithm

  1. Step 1: Sort stalls array.
  2. Step 2: low = 1, high = stalls[n - 1] - stalls[0], ans = 1.
  3. Step 3: While low <= high:
  4. - mid = low + (high - low) / 2.
  5. - count = 1, last = stalls[0].
  6. - For i = 1 to n - 1: if stalls[i] - last >= mid { count++; last = stalls[i]; }.
  7. - If count >= k: ans = mid, low = mid + 1.
  8. - Else: high = mid - 1.
  9. Step 4: Return ans.

Trace for stalls = [1, 2, 4, 8, 9], k = 3

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Range [1, 8]
Visual state
Values and pointers at this exact step
pointers
S
Cow 1
Empty
Empty
Cow 2
Empty
0
↑ low
1
2
↑ mid
3
4
↑ high
Check / comparison
Distance 4: placed 2 cows < 3 -> Infeasible.
Decision / next transition
Set high = 3.
Why this step matters

Range [1, 8]. mid=4. Place cow 1 at 1. Next >= 1+4=5 is stall 8 (cow 2). Next >= 8+4=12 (none). Placed 2 cows < 3. Infeasible! high = mid - 1 = 3.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7int aggressiveCows(vector<int>& stalls, int k) {
8 sort(stalls.begin(), stalls.end());
9 int low = 1, high = stalls.back() - stalls.front();
10 int ans = 1;
11 while (low <= high) {
12 int mid = low + (high - low) / 2;
13 int count = 1, last = stalls[0];
14 for (int i = 1; i < (int)stalls.size(); ++i) {
15 if (stalls[i] - last >= mid) {
16 count++;
17 last = stalls[i];
18 }
19 }
20 if (count >= k) {
21 ans = mid;
22 low = mid + 1;
23 } else {
24 high = mid - 1;
25 }
26 }
27 return ans;
28}
29
30int main() {
31 // Sample driver execution
32 cout << "Execution completed successfully." << endl;
33 return 0;
34}
35

Time & Space Complexity

  • Time complexity: O(n log n + n * log(max_dist)) — Sorting takes O(n log n). Binary search takes log2(max_dist) ~ 30 iterations of O(n) check.
  • Space complexity: O(1) — Operates in-place with O(1) auxiliary variables.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Linear Distance CheckO(n log n + n * range)O(1)Test distances sequentially from 1 upwards.Iterates through entire coordinate range.
2.Block Jump SearchO(n log n + n * sqrt(range))O(1)Jump in steps of sqrt(range).Linear scan in block.
3.Binary Search on AnswerOptimalO(n log n + n * log(range))O(1)Binary search on monotonic distance domain.None. This is optimal.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • k == 2 -> answer is stalls[n-1] - stalls[0].
  • k == n -> answer is min(stalls[i] - stalls[i-1]).
  • Stalls with large coordinate values up to 109.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Mention that sorting stalls is the critical prerequisite for greedy placement.
  2. Explain why placing the first cow at stalls[0] is always optimal.
  3. State time complexity as O(n log n) for sorting + O(n log(max_dist)) for binary search.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the monotonicity property of the canPlace(dist) function?

Back to DSA Sheet