Given an array stalls[] representing the positions of stalls and an integer k denoting the number of aggressive cows, place the cows in the stalls such that the minimum distance between any two cows is as large as possible. Return this maximum possible minimum distance.
Examples:
Input: stalls[] = [1, 2, 4, 8, 9], k = 3
Output: 3
Explanation: We can place cow 1 at position 1, cow 2 at position 4 and cow 3 at position 9. So, the maximum possible minimum distance between two cows is 3.Input: stalls[] = [6, 7, 9, 11, 13, 15], k = 4
Output: 2
Explanation: We can place cow 1 at position 6, cow 2 at position 9, cow 3 at position 11 and cow 4 at position 15. So, the maximum possible minimum distance between two cows is 2.
Try it on GfG Practice
Table of Content
[Naive Approach] By iterating over all possible distances
The idea is to place k cows such that the minimum distance between any two is maximized. We sort the stalls and try all possible distances from 1 to the maximum gap between stalls.
For each distance, we check if cows can be placed by assigning the first cow to the first stall, and placing the next cow only if the gap from the last placed cow is at least that distance.
If placement is possible, we update our answer; the largest such distance is returned.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// function to check if we can place k cows
// with at least dist distance apart
bool check(vector<int> &stalls, int k, int dist) {
// Place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < stalls.size(); i++) {
// If the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// Return true if we are able to place all 'k' cows
return (cnt >= k);
}
int aggressiveCows(vector<int> &stalls, int k) {
// sorting the array to ensure stalls in sequence
sort(stalls.begin(), stalls.end());
int res = 0;
// Minimum and maximum possible minimum distance
// between two stalls
int minDist = 1;
int maxDist = stalls.back() - stalls[0];
// Iterating through all possible distances
for (int i = minDist; i <= maxDist; i++) {
// If we can place k cows with the
// current distance i, update the res
if (check(stalls, k, i))
res = i;
}
return res;
}
int main() {
vector<int> stalls = {1, 2, 4, 8, 9};
int k = 3;
int ans = aggressiveCows(stalls, k);
cout << ans;
return 0;
}
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// function to check if we can place k cows
// with at least dist distance apart
int check(int stalls[], int size, int k, int dist) {
// Place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < size; i++) {
// If the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// Return true if we are able to place all 'k' cows
return (cnt >= k);
}
int aggressiveCows(int stalls[], int size, int k) {
// sorting the array to ensure stalls in sequence
qsort(stalls, size, sizeof(int), (int (*)(const void *, const void *))compare);
int res = 0;
// Minimum and maximum possible minimum distance
// between two stalls
int minDist = 1;
int maxDist = stalls[size - 1] - stalls[0];
// Iterating through all possible distances
for (int i = minDist; i <= maxDist; i++) {
// If we can place k cows with the
// current distance i, update the res
if (check(stalls, size, k, i))
res = i;
}
return res;
}
int main() {
int stalls[] = {1, 2, 4, 8, 9};
int k = 3;
int size = sizeof(stalls) / sizeof(stalls[0]);
int ans = aggressiveCows(stalls, size, k);
printf("%d\n", ans);
return 0;
}
import java.util.Arrays;
class GfG {
// function to check if we can place k cows
// with at least dist distance apart
static boolean check(int[] stalls, int k, int dist) {
// Place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < stalls.length; i++) {
// If the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// Return true if we are able to place all 'k' cows
return (cnt >= k);
}
static int aggressiveCows(int[] stalls, int k) {
// sorting the array to ensure stalls in sequence
Arrays.sort(stalls);
int res = 0;
// Minimum and maximum possible minimum distance
// between two stalls
int minDist = 1;
int maxDist = stalls[stalls.length - 1] - stalls[0];
// Iterating through all possible distances
for (int i = minDist; i <= maxDist; i++) {
// If we can place k cows with the
// current distance i, update the res
if (check(stalls, k, i))
res = i;
}
return res;
}
public static void main(String[] args) {
int[] stalls = {1, 2, 4, 8, 9};
int k = 3;
int ans = aggressiveCows(stalls, k);
System.out.println(ans);
}
}
# function to check if we can place k cows
# with at least dist distance apart
def check(stalls, k, dist):
# Place first cow at 0th index
cnt = 1
prev = stalls[0]
for i in range(1, len(stalls)):
# If the current stall is at least dist away
# from the previous one place the cow here
if stalls[i] - prev >= dist:
prev = stalls[i]
cnt += 1
# Return true if we are able to place all 'k' cows
return cnt >= k
def aggressiveCows(stalls, k):
# sorting the array to ensure stalls in sequence
stalls.sort()
res = 0
# Minimum and maximum possible minimum distance
# between two stalls
minDist = 1
maxDist = stalls[-1] - stalls[0]
# Iterating through all possible distances
for i in range(minDist, maxDist + 1):
# If we can place k cows with the
# current distance i, update the res
if check(stalls, k, i):
res = i
return res
if __name__ == "__main__":
stalls = [1, 2, 4, 8, 9]
k = 3
ans = aggressiveCows(stalls, k)
print(ans)
using System;
class GfG {
// function to check if we can place k cows
// with at least dist distance apart
static bool check(int[] stalls, int k, int dist) {
// Place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < stalls.Length; i++) {
// If the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// Return true if we are able to place all 'k' cows
return (cnt >= k);
}
static int aggressiveCows(int[] stalls, int k) {
// sorting the array to ensure stalls in sequence
Array.Sort(stalls);
int res = 0;
// Minimum and maximum possible minimum distance
// between two stalls
int minDist = 1;
int maxDist = stalls[stalls.Length - 1] - stalls[0];
// Iterating through all possible distances
for (int i = minDist; i <= maxDist; i++) {
// If we can place k cows with the
// current distance i, update the res
if (check(stalls, k, i))
res = i;
}
return res;
}
static void Main() {
int[] stalls = {1, 2, 4, 8, 9};
int k = 3;
int ans = aggressiveCows(stalls, k);
Console.WriteLine(ans);
}
}
// function to check if we can place k cows
// with at least dist distance apart
function check(stalls, k, dist) {
// Place first cow at 0th index
let cnt = 1;
let prev = stalls[0];
for (let i = 1; i < stalls.length; i++) {
// If the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// Return true if we are able to place all 'k' cows
return (cnt >= k);
}
function aggressiveCows(stalls, k) {
// sorting the array to ensure stalls in sequence
stalls.sort((a, b) => a - b);
let res = 0;
// Minimum and maximum possible minimum distance
// between two stalls
let minDist = 1;
let maxDist = stalls[stalls.length - 1] - stalls[0];
// Iterating through all possible distances
for (let i = minDist; i <= maxDist; i++) {
// If we can place k cows with the
// current distance i, update the res
if (check(stalls, k, i))
res = i;
}
return res;
}
// Driver Code
let stalls = [1, 2, 4, 8, 9];
let k = 3;
let ans = aggressiveCows(stalls, k);
console.log(ans);
Output
3
Time Complexity: O(n × (max(stalls) - min(stalls))), where n is the size of the array, max(stalls) is the maximum element in the array and min(stalls) is minimum element in the array.
Auxiliary Space: O(1).
[Expected Approach] Using Binary Search on Answer
The minimum distance between cows follows a monotonic property, which makes binary search possible.
- If we can place all cows with a minimum distance d, then placing them with any smaller distance is also possible because allowing smaller gaps gives us more flexibility and space to place cows closer together.
- On the other hand, if we can’t place all cows with distance d, then any larger distance also won’t work—since increasing the gap makes placement even harder.
So, we apply binary search on the distance range to find the largest minimum distance possible.
To check if a distance works, we place the first cow at the first stall and place each next cow only if it’s at least d units away from the last one. If all cows fit, it’s a valid distance.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// function to check if we can place k cows
// with at least dist distance apart
bool check(vector<int> &stalls, int k, int dist) {
// place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < stalls.size(); i++) {
// if the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// return true if we are able to place all 'k' cows
return (cnt >= k);
}
int aggressiveCows(vector<int> &stalls, int k) {
// sorting the array to ensure stalls in sequence
sort(stalls.begin(), stalls.end());
int res = 0;
// Search Space for Binary Search
int lo = 1;
int hi = stalls.back() - stalls[0];
while(lo <= hi) {
int mid = lo + (hi - lo)/2;
// If the mid ditance is possible, update
// the result and search for larger ditance
if(check(stalls, k, mid)) {
res = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return res;
}
int main() {
vector<int> stalls = {1, 2, 4, 8, 9};
int k = 3;
int ans = aggressiveCows(stalls, k);
cout << ans;
return 0;
}
#include <stdio.h>
int compare(const void *a, const void *b) {
return (*(int*)a - *(int*)b);
}
// function to check if we can place k cows
// with at least dist distance apart
int check(int stalls[], int n, int k, int dist) {
// place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < n; i++) {
// if the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// return true if we are able to place all 'k' cows
return (cnt >= k);
}
int aggressiveCows(int stalls[], int n, int k) {
// sorting the array to ensure stalls in sequence
qsort(stalls, n, sizeof(int), compare);
int res = 0;
// search Space for Binary Search
int lo = 1;
int hi = stalls[n - 1] - stalls[0];
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
// If the mid distance is possible, update
// the result and search for larger distance
if(check(stalls, n, k, mid)) {
res = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return res;
}
int main() {
int stalls[] = {1, 2, 4, 8, 9};
int k = 3;
int n = sizeof(stalls) / sizeof(stalls[0]);
int ans = aggressiveCows(stalls, n, k);
printf("%d\n", ans);
return 0;
}
import java.util.Arrays;
class GfG {
// function to check if we can place k cows
// with at least dist distance apart
static boolean check(int[] stalls, int k, int dist) {
// place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < stalls.length; i++) {
// if the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// return true if we are able to place all 'k' cows
return (cnt >= k);
}
static int aggressiveCows(int[] stalls, int k) {
// sorting the array to ensure stalls in sequence
Arrays.sort(stalls);
int res = 0;
// Search Space for Binary Search
int lo = 1;
int hi = stalls[stalls.length - 1] - stalls[0];
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
// If the mid distance is possible, update
// the result and search for larger distance
if(check(stalls, k, mid)) {
res = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return res;
}
public static void main(String[] args) {
int[] stalls = {1, 2, 4, 8, 9};
int k = 3;
int ans = aggressiveCows(stalls, k);
System.out.println(ans);
}
}
def check(stalls, k, dist):
# place first cow at 0th index
cnt = 1
prev = stalls[0]
for i in range(1, len(stalls)):
# if the current stall is at least dist away
# from the previous one place the cow here
if stalls[i] - prev >= dist:
prev = stalls[i]
cnt += 1
# return true if we are able to place all 'k' cows
return cnt >= k
def aggressiveCows(stalls, k):
# sorting the array to ensure stalls in sequence
stalls.sort()
res = 0
# search Space for Binary Search
lo = 1
hi = stalls[-1] - stalls[0]
while lo <= hi:
mid = lo + (hi - lo) // 2
# If the mid distance is possible, update
# the result and search for larger distance
if check(stalls, k, mid):
res = mid
lo = mid + 1
else:
hi = mid - 1
return res
if __name__ == "__main__":
stalls = [1, 2, 4, 8, 9]
k = 3
ans = aggressiveCows(stalls, k)
print(ans)
using System;
class GfG {
// function to check if we can place k cows
// with at least dist distance apart
static bool check(int[] stalls, int k, int dist) {
// place first cow at 0th index
int cnt = 1;
int prev = stalls[0];
for (int i = 1; i < stalls.Length; i++) {
// if the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// return true if we are able to place all 'k' cows
return (cnt >= k);
}
static int aggressiveCows(int[] stalls, int k) {
// sorting the array to ensure stalls in sequence
Array.Sort(stalls);
int res = 0;
// search Space for Binary Search
int lo = 1;
int hi = stalls[stalls.Length - 1] - stalls[0];
while(lo <= hi) {
int mid = lo + (hi - lo) / 2;
// if the mid distance is possible, update
// the result and search for larger distance
if(check(stalls, k, mid)) {
res = mid;
lo = mid + 1;
}
else {
hi = mid - 1;
}
}
return res;
}
static void Main() {
int[] stalls = {1, 2, 4, 8, 9};
int k = 3;
int ans = aggressiveCows(stalls, k);
Console.WriteLine(ans);
}
}
function check(stalls, k, dist) {
// place first cow at 0th index
let cnt = 1;
let prev = stalls[0];
for (let i = 1; i < stalls.length; i++) {
// if the current stall is at least dist away
// from the previous one place the cow here
if (stalls[i] - prev >= dist) {
prev = stalls[i];
cnt++;
}
}
// return true if we are able to place all 'k' cows
return (cnt >= k);
}
function aggressiveCows(stalls, k) {
// sorting the array to ensure stalls in sequence
stalls.sort((a, b) => a - b);
let res = 0;
// search Space for Binary Search
let lo = 1;
let hi = stalls[stalls.length - 1] - stalls[0];
while (lo <= hi) {
let mid = Math.floor(lo + (hi - lo) / 2);
// if the mid distance is possible, update
// the result and search for larger distance
if (check(stalls, k, mid)) {
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
return res;
}
// Driver Code
const stalls = [1, 2, 4, 8, 9];
const k = 3;
const ans = aggressiveCows(stalls, k);
console.log(ans);
Output
3
Time Complexity: O(n log d), we first sort the stalls array, which takes O(n log n) time. After that, we perform a binary search on the distance range, from 1 to the maximum possible distance between the farthest stalls, which gives us log d steps (where d = stalls[n-1] - stalls[0] or max(stalls) - min(stalls) ). For each distance in the binary search, we run the check() function to verify if cow placement is possible, which takes O(n) time in the worst case.
Auxiliary Space: O(1)