Aggressive Cows: Maximize the Minimum Distance

102k
0

You are given an array arr of size N which denotes the position of stalls. You are also given an integer k which denotes the number of Aggressive Cows. You are given the task of assigning stalls to k cows such that the minimum distance between any two of them is the maximum possible. Find the maximum possible minimum distance.

Example 1

Input: arr = [1, 2, 4, 8, 9], k = 3

Output: 3

Explanation: We have 3 cows and 5 stalls. If we place cow 1 at stall 1, cow 2 at stall 4, and cow 3 at stall 8, the distances between adjacent cows are (4 - 1) = 3 and (8 - 4) = 4. The minimum distance is 3. We cannot find any other placement that yields a larger minimum distance.

Example 2

Input: arr = [10, 1, 2, 7, 5], k = 3

Output: 4

Explanation: First, we sort the stalls: [1, 2, 5, 7, 10]. We can place cow 1 at stall 1, cow 2 at stall 5, and cow 3 at stall 10. The distances are (5 - 1) = 4 and (10 - 5) = 5. The minimum distance is 4.

Brute Force Approach

The first important step is sorting the stall positions. Sorting allows checking whether a distance is possible using a single greedy linear pass: place the first cow at the first stall, then sequentially place each next cow at the earliest stall that is at least the required distance away.

This works because placing each cow as early as possible preserves the maximum available space for the remaining cows; if this greedy placement cannot accommodate all cows, no other placement strategy at that required distance can succeed.

In brute force, try every possible minimum distance from 1 to max(stalls) - min(stalls). The first distance that becomes impossible tells that the previous distance was the best possible answer, as the maximum distance possible between two cows is when we place them on the first and the last stall.

Algorithm

  • Sort the stall positions first. This is needed because distances between cows make sense only when stalls are checked from left to right.

  • The smallest useful minimum distance is 1, and the largest possible minimum distance is the distance between the first and last stall after sorting.

  • For every possible distance, greedily try to place cows. Put the first cow in the first stall because this leaves the most room for the remaining cows.

  • While scanning the sorted stalls, place another cow whenever the current stall is far enough from the last chosen stall. This keeps every chosen pair at least the required distance apart.

  • If all cows can be placed, keep trying a larger distance. If they cannot be placed, return the previous distance because distances are being tested in increasing order.

Dry Run

Aggressive Cows Brute Dry Run

Aggressive Cows Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks if all cows can be placed while keeping
at least distance gap between every pair.
*/
bool canPlace(vector<int>& stalls, int k, int distance) {
// The first cow is placed at the first stall
// to leave maximum room for the remaining cows.
int cowsPlaced = 1;
// This stores the position of the most recently placed cow.
int lastPosition = stalls[0];
for (int i = 1; i < (int)stalls.size(); i++) {
// Place a cow only when this stall is far enough
// from the last chosen stall.
if (stalls[i] - lastPosition >= distance) {
cowsPlaced++;
lastPosition = stalls[i];
// Once all cows are placed, this distance is possible.
if (cowsPlaced == k) {
return true;
}
}
}
return false;
}
/*
Returns the largest minimum distance by
checking every possible distance one by one.
*/
int aggressiveCows(vector<int>& stalls, int k) {
sort(stalls.begin(), stalls.end());
// This is the largest distance two cows can ever have.
int maxDistance = stalls.back() - stalls.front();
for (int distance = 1; distance <= maxDistance; distance++) {
// If this distance fails, the previous distance
// is the largest one that worked.
if (!canPlace(stalls, k, distance)) {
return distance - 1;
}
}
return maxDistance;
}
};
// Driver code starts
int main() {
vector<int> stalls = {1, 2, 4, 8, 9};
int k = 3;
Solution obj;
cout << obj.aggressiveCows(stalls, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O((N x log2 N) + (N x MaxDistance)), because sorting takes O(N x log2 N) and every possible distance may scan all stalls where the maximum possible distance is MaxDistance. MaxDistance is the distance between the earliest stall and the last stall, as this is the maximum distance possible between 2 cows after placement.

Space Complexity: O(1), because constant extra space is used apart from sorting.

Optimal Approach

The main observation is monotonic. If it is possible to place all cows with at least X distance between them, then it is also possible with any smaller distance. Smaller gaps are easier to satisfy.

If it is not possible to place all cows with at least X distance, then any larger distance will also be impossible. Larger gaps need more space.

So possible distances form a pattern like this: possible, possible, possible, not possible, not possible

The answer is the last possible distance. To check one distance, the greedy idea works nicely. Sort the stalls, place the first cow at the first stall, and then place each next cow at the earliest stall that is far enough from the previous cow. Early placement is helpful because it leaves more stalls available for the cows still waiting.

Algorithm

  • Sort the stall positions first. This converts the problem into checking distances from left to right.

  • Set low = 1 because the minimum distance between two different stall positions starts from at least 1 in the usual version of this problem.

  • Set high = last stall - first stall because no two cows can be farther apart than the two extreme stalls.

  • Pick mid as the minimum distance to test. Use the greedy helper to check whether all k cows can be placed with at least mid gap.

  • If mid is possible, store it as the current answer and move low to mid + 1. This is done because the goal is to maximize the minimum distance.

  • If mid is not possible, move high to mid - 1. This is done because the required gap is too large, so smaller distances must be tried.

  • When the search ends, return the stored answer.

Dry Run

Aggressive Cows Optimal Dry Run

Aggressive Cows Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Checks if all cows can be placed while keeping
at least distance gap between every pair.
*/
bool canPlace(vector<int>& stalls, int k, int distance) {
// The first cow is placed at the first stall
// to leave maximum room for the remaining cows.
int cowsPlaced = 1;
// This stores the position of the most recently placed cow.
int lastPosition = stalls[0];
for (int i = 1; i < (int)stalls.size(); i++) {
// Place a cow only when this stall is far enough
// from the last chosen stall.
if (stalls[i] - lastPosition >= distance) {
cowsPlaced++;
lastPosition = stalls[i];
// Once all cows are placed, this distance is possible.
if (cowsPlaced == k) {
return true;
}
}
}
return false;
}
/*
Returns the largest minimum distance
using binary search on possible distances.
*/
int aggressiveCows(vector<int>& stalls, int k) {
sort(stalls.begin(), stalls.end());
// Distance smaller than 1 is not useful
// when all stall positions are unique.
int low = 1;
// This is the largest distance two cows can ever have.
int high = stalls.back() - stalls.front();
// This stores the largest possible distance found so far.
int answer = 0;
while (low <= high) {
// mid is the minimum distance currently being tested.
int mid = low + (high - low) / 2;
// If mid works, try a larger minimum distance.
if (canPlace(stalls, k, mid)) {
answer = mid;
low = mid + 1;
} else {
// If mid fails, larger distances will also fail.
high = mid - 1;
}
}
return answer;
}
};
// Driver code starts
int main() {
vector<int> stalls = {1, 2, 4, 8, 9};
int k = 3;
Solution obj;
cout << obj.aggressiveCows(stalls, k) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O((N x log N) + (N x log2 MaxDistance)), Sorting the stalls takes O(N x log N) time. The binary search operates over the search space of possible distances from 1 to MaxDistance, requiring O(log2(MaxDistance) iterations. In each iteration, checking whether the cows can be placed requires scanning all N stalls in O(N) time.

Space Complexity: O(1), because constant extra space is used apart from sorting.

Interview follow-up Questions

To accurately determine distances between adjacent cows, the stalls must be evaluated in their natural physical order on the number line. Without sorting, calculating the gap between index i and i-1 would be mathematically meaningless and could result in placing a cow backward.

Two PointerBinary SearchGreedyMathsArrays

Read Similar Blogs

Arrays

Row wise traversal

Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then second row prints as 4 5 6 . Input: mat = [[10, 20], [30, 40], [50, 60]] Output: 10 20 30 40 50...

61.7k
Arrays

Main Diagonal Print

tuf-examples-1 Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0] , mat[1][1] , and mat[2][2] . Input: mat = [[10, 20, 30], [40, 50, 60]] Ou...

67k
Arrays

Search Element in Matrix

Given a matrix with N rows and M columns and a target value X , search for X in the matrix. Return the position of the first occurrence of X as {row, col} . Return {-1, -1} when the t...

98.4k
Comments0