Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
2.2.
Analyzing the Problem Statement
3.
Naive/Brute Force Approach
3.1.
Algorithm
3.2.
Dry Run
3.3.
C++ Implementation
3.4.
Java Implementation
3.5.
Python Implementation
3.6.
Output
3.7.
Time Complexity
3.8.
Space Complexity
4.
Binary Search Approach
4.1.
Algorithm
4.2.
Dry Run
4.2.1.
Case 1
4.2.2.
Case 2
4.2.3.
Case 3
4.2.4.
Case 4
4.3.
C++ Implementation
4.4.
Java Implementation
4.5.
Python Implementation
4.6.
Output
4.7.
Time Complexity
4.8.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is binary search?
5.2.
When can Binary Search be utilized on an array?
5.3.
What is the time complexity of the optimal approach for the Aggressive Cows problem?
5.4.
How can you implement a binary search algorithm?
5.5.
What are some of the search algorithms?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Aggressive Cows

Author Kartik Kukreja
6 upvotes
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

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.

Aggressive Cows

Let’s first understand the problem statement in depth to get a better understanding.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Problem Statement

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.

 

Please try to solve this problem on your own before moving on to further discussion.

Analyzing the Problem Statement

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Dry run

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;
}

Java Implementation

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;
	}
}

Python Implementation

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))

Output

Output

Time Complexity

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.

Read More - Time Complexity of Sorting Algorithms

Binary Search Approach

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 1

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 2

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 3

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. 

Case 4

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;
}

Java Implementation

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;
	}
}

Python Implementation

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))

Output

Output

Time Complexity

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-  

 

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning, Ninjas!

Previous article
Maximize Subarray Sum of Given Array by Adding X in the Range [L, R] for Q queries
Next article
Book Allocation Problem
Live masterclass