Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello Ninjas! How is your preparation going? To brush up on your Data structures Skills, we are back with a famous problem. In this article, we will discuss the problem of Aggressive Cows. We will see both the naive approach and the optimized version of the solution. If you find this problem tricky, then do read till the end because here you will understand every step logically.
Let’s first understand the problem statement in depth to get a better understanding.
You are given an array of length ‘N,’ where each element denotes the position of a stall. These ‘N’ stalls are located along a straight line at positions x1, x2, x3…, xn. The integer ‘K’ represents the number of cows that are aggressive. You need to assign the cows to the stalls such that they don’t hurt each other. This can be done by maximizing the minimum distance between them. What is the largest minimum distance?
Example
Input
N = 5
K = 3
X = [ 1, 3, 5, 6, 10]
Where ‘N’ is the number of stalls, ‘K’ represents the number of aggressive cows and ‘X’ is the positions array.
Output
4
Explanation
The first cow can be placed at position 1, the second cow at position 5, and the third cow at position 10. So the largest minimum distance will be a minimum of (5 - 1, 10 - 5 ), i.e., 4.
Let’s analyze the problem and write down some important points that will help you reach the solutions.
What can be the minimum distance between two cows?
Since two cows can’t be placed in the same stall, the minimum possible distance can be 1.
What can be the largest distance between the cows?
If max(POS) and min(POS) are the maximum and minimum of all the positions, respectively, in the POS array, then the maximum possible distance between the cows can be equal to max(POS) - min(POS).
Note: The above maximum and minimum distances might not be possible to arrange the cows. These values only determine the range in which the largest minimum distance will lie.
So we can say that the distance between two cows will always lie in the range [1, max(POS)-min(POS)].
We need to minimize the distance between the cows such that it is the largest minimum distance possible among all the possible arrangements of cows. Say the required distance is D, then there can’t be any arrangement of cows such that the minimum distance between any two cows in this arrangement is greater than D.
Considering the above points, Let’s have a look at the naive approach.
Naive/Brute Force Approach
The range of the distance between any two cows is [1, max(POS)-min(POS)]. The idea is to check if placing the cows at each possible distance is possible.
Algorithm
Sort the given positions to maximize the distance between two positions.
Iterate for each possible distance from 1 to the maximum distance, i.e., max(POS)-min(POS) and call the function to check if the arrangement is possible.
For each distance, start placing cows from the 1st position and check if curr_pos - prev_pos >= distance.
If it is possible to place the cow in that position, update the previous position as the current position and check further.
Update the count whenever we place a cow; if count >= number of cows, the arrangement is possible.
Repeat the same steps for the next distance. Stop when it is not possible to arrange and return the answer.
Dry Run
Suppose the following input is given:
Cows = 3
Positions = [ 1, 3, 5, 6, 10 ]
Let’s see the arrangement of cows for each possible distance.
Minimum distance- 1: We can place the first cow at position 1 and the second cow at position 3 as 3-1 >=1. Similarly, the third cow can be placed at position 5. Hence answer can be 1.
Minimum distance- 2: We can place the first cow at position 1 and the second cow at position 3. The third cow can be placed at position 5. Hence answer can be 2.
Minimum distance- 3: We can place the first cow at position 1, the second cow at position 5, and the third cow at position 10. Hence arrangement is possible.
Minimum distance- 4: We can place the first cow at position 1, the second cow at position 5, and the third cow at position 10. Hence answer can be 4.
Minimum distance- 5: We can place the first cow at position 1 and the second cow at position 6, but we can’t place the third cow as the distance will be less than 5. So no arrangement is possible.
Since for distance = 5, the arrangement is not possible; Hence the answer is 4.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
bool isPossible(vector<int>& pos, int dist, int N, int K) {
int count = 1;
int prev = pos[0];
for(auto curr:pos) {
if(curr - prev >= dist) {
prev = curr;
count++;
}
}
if (count >= K) return true;
return false;
}
int main() {
int N = 5, K = 3;
vector<int> pos = { 1, 3, 5, 6, 10 };
int ans = -1;
sort(pos.begin(), pos.end());
// maximum element from the position array
int max_dist = pos[N-1];
/*
try out each possible distance
from 1 to max_dist
store the distance in ans,
if the arrangement is possible
otherwise, break.
*/
for (int dist = 1; dist <= max_dist; dist++) {
if (isPossible(pos, dist, N, K)) {
ans = dist;
}
else {
break;
}
}
// print the answer
cout << "The largest minimum distance is: "<< ans << endl;
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
public class main {
public static void main(String[] args) {
int N = 5, K = 3;
int[] pos = { 1, 3, 5, 6, 10 };
Arrays.sort(pos);
int ans = -1, max_dist = pos[N - 1];
/*
try out each possible distance
from 1 to max_dist
store the distance in ans,
if the arrangement is possible
otherwise, break.
*/
for (int dist = 1; dist <= max_dist; dist++) {
if (isPossible(pos, dist, N, K)) {
ans = dist;
}
else {
break;
}
}
System.out.println("The largest minimum distance is: " + ans);
}
public static boolean isPossible(int[] pos, int dist, int N, int K) {
int count = 1;
// place a cow at 1st position
int prev = pos[0];
for (int curr_pos = 0; curr_pos < N; curr_pos++) {
int curr = pos[curr_pos];
// check if we can place a cow at that position
if (curr - prev >= dist) {
prev = curr;
count++;
}
}
// all the cows are placed
if (count >= K)
return true;
return false;
}
}
You can also try this code with Online Java Compiler
def isPossible(pos, dist, N, K ):
count=1
# place a cow at 1st position
prev = pos[0]
for curr_pos in range(1,N):
curr = pos[curr_pos]
# check if we can place a cow at that position
if(curr - prev >= dist):
prev = curr
count = count+1
# all the cows are placed
if(count >= K):
return True
return False
N = 5
K = 3
pos = [1,3, 5, 6, 10]
pos.sort()
ans = -1
max_dist = pos[N-1]
# try out each possible distance from 1 to max_dist
for dist in range(1,max_dist+1):
# store the distance in ans, if the arrangement is possible
if(isPossible(pos, dist, N, K)):
ans = dist
else:
# arrangement is not possible for further distance
break
print("The largest minimum distance is: " + str(ans))
You can also try this code with Online Python Compiler
Two loops are being used in the solution. The outer loop runs from minDist to maxDist, and in each iteration, we call the function isPossible, whose time complexity is O(N). So, the total time complexity is O(M*N), where N is the size of the position array and M is the maxDist at which the stall can be placed.
Space Complexity
The array, when sorted, will take log(N) space so that the overall space complexity will be O(log(N)), where N represents the number of elements in the given array.
We can reduce the time complexity by reducing the number of comparisons using binary search. For the range 1 to max distance, we can find a mid distance and check if the arrangement is possible. If the arrangement is possible for a certain distance, we will only check for a higher distance or else for a lower distance.
Algorithm
Sort the given positions to maximize the distance between two positions.
Take a low element as 1 and a high as the maximum possible distance, i.e. max(POS) - min(POS), and apply a binary search algorithm.
Find mid = low + ( high - low ) / 2. Now check if it’s possible to arrange cows for this distance.
Start placing cows from the 1st position and check if curr_pos - prev_pos >= distance.
If it is possible to place the cow in that position, update the previous position as the current position and check further.
Update the count whenever we place a cow; if count >= number of cows, the arrangement is possible.
If the arrangement is not possible, search for a lower distance by updating high = mid-1; if possible, update low = mid + 1; this will search for a higher distance.
Dry Run
Take a low and a high element to perform a binary search. Initialize low = 1 and high = 10-1, i.e., 9.
Case 1
Low = 1, High = 9, Mid = 1 + (9-1) / 2 = 5. For minimum distance = 5, we can place the first cow at position 1, and the second cow at position 6 as 6-1 >= 5. We cannot place the third cow; hence the arrangement is not possible. Update High = Mid - 1, i.e., High = 4.
Case 2
Low = 1, High = 4, Mid = 1 + (4-1) / 2 = 2. For minimum distance = 2, we can place the first cow at position 1, and the second cow at position 3 as 3-1 >= 2. The third cow can be placed at position 5. Hence arrangement is possible. Update Low = Mid + 1, i.e., Low = 3.
Case 3
Low = 3, High = 4, Mid = 3 + (4-3) / 2 = 3. For minimum distance = 3, we can place the first cow at position 1, and the second cow at position 5 as 5-1 >= 3. The third cow can be placed at position 10. Hence arrangement is possible. Update Low = Mid + 1, i.e., Low = 4.
Case 4
Low = 4, High = 4, Mid = 4 + (4-4) / 2 = 4. For minimum distance = 4, we can place the first cow at position 1, and the second cow at position 5 as 5-1 >= 4. The third cow can be placed at position 10. Hence arrangement is possible. Update Low = Mid + 1, i.e., Low = 5.
Since Low > High, Stop the binary search and return the answer as 4.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
bool isPossible(vector<int>& pos, int dist, int N, int K) {
int count = 1;
int prev = pos[0];
for(auto curr:pos) {
if(curr - prev >= dist) {
prev = curr;
count++;
}
}
if (count >= K) return true;
return false;
}
int main() {
int N = 5, K = 3;
vector<int> pos = { 1, 3, 5, 6, 10 };
int ans = -1;
sort(pos.begin(), pos.end());
// maximum element from the position array
int max_dist = pos[N-1];
// take a low and high element
int low = 1, high = max_dist;
while(low <= high) {
int mid = low + (high-low) / 2;
/*
store the distance in ans,
if the arrangement is possible
and update the low to search
for greater distance
otherwise, update the high
to search for lower distance.
*/
if (isPossible(pos, mid, N, K)) {
ans = mid;
low = mid+1;
}
else {
high = mid-1;
}
}
// print the answer
cout << "The largest minimum distance is: "<< ans << endl;
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
public class main {
public static void main(String[] args) {
int N = 5, K = 3;
int[] pos = { 1, 3, 5, 6, 10 };
Arrays.sort(pos);
int ans = -1, max_dist = pos[N - 1];
int low = 1, high = max_dist;
while (low <= high) {
int mid = low + (high-low) / 2;
/*
store the distance in ans,
if the arrangement is possible
and update the low to search
for greater distance
otherwise, update the high
to search for lower distance.
*/
if (isPossible(pos, mid, N, K)) {
ans = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
System.out.println("The largest minimum distance is: " + ans);
}
public static boolean isPossible(int[] pos, int dist, int N, int K) {
int count = 1;
// place a cow at 1st position
int prev = pos[0];
for (int curr_pos = 0; curr_pos < N; curr_pos++) {
int curr = pos[curr_pos];
// check if we can place a cow at that position
if (curr - prev >= dist) {
prev = curr;
count++;
}
}
// all the cows are placed
if (count >= K)
return true;
return false;
}
}
You can also try this code with Online C++ Compiler
def isPossible(pos, dist, N, K ):
count=1
# place a cow at 1st position
prev = pos[0]
for curr_pos in range(1,N):
curr = pos[curr_pos]
# check if we can place a cow at that position
if(curr - prev >= dist):
prev = curr
count = count+1
# all the cows are placed
if(count >= K):
return True
return False
N = 5
K = 3
pos = [1, 3, 5, 6, 10]
pos.sort()
ans = -1
# maximum element from the position array
max_dist = pos[N-1]
# take a low and high element
low = 1
high = max_dist
while(low <= high):
mid = low + (high - low) // 2
if(isPossible(pos, mid, N, K)):
# store the distance in ans, if the arrangement is possible
ans = mid
# update the low to search for greater distance
low = mid+1
else:
high = mid-1
print("The largest minimum distance is: " + str(ans))
You can also try this code with Online C++ Compiler
We are calling the isPossible() function along with the binary search. The binary search takes O(log M) (where M is the maximum distance) time, and in each iteration, we call the isPossible() function having O(N) (where N is the size of the positions array) time complexity. So the total time complexity will be O(N * log(M)).
Space Complexity
The array, when sorted, will take log(N) space so that the overall space complexity will be O(log(N)), where ‘N’ represents the number of elements in the given array/list.
Frequently Asked Questions
What is binary search?
A binary search is used to find an element’s position in a sorted array. In this algorithm, the search interval is repeatedly divided in half. The comparison is made with the middle element, and accordingly, the left or right half of the array is searched.
When can Binary Search be utilized on an array?
A binary search can be performed on an array in sorted order. O(log(N)) is the time complexity of the binary search algorithm, where 'N' represents the size of the array.
What is the time complexity of the optimal approach for the Aggressive Cows problem?
The most optimal approach for this problem involves using Binary Search. The overall time complexity for the approach is O(N* (log M) ), where N is the number of stalls and M is the maximum distance at which cows can be placed.
How can you implement a binary search algorithm?
The binary search implementation involves the iterative method and the Recursive method. The space complexity of the Iterative method is O(1), while that of the recursive approach is O(log N).
What are some of the search algorithms?
There are many different algorithms for searching. Here are a few common ones: Linear Search, Binary Search, Depth-first search (DFS), Breadth-first search, etc.
Conclusion
In this article, we have solved quite an interesting problem: Aggressive Cows. It is very important to completely understand the problem statement, which we did by taking some examples. We discussed the naive approach first and then optimized the solution by binary search as the problem had monotonic properties. With this problem, you must have got an idea of when to use binary search.
Some of the problems which you can practice based on binary search-
7+ registered 
