Aggressive Cows

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
943 upvotes
Asked in companies
AdobeGoldman SachsDunzo

Problem statement

You are given an array 'arr' consisting of 'n' integers which denote the position of a stall.


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.



Example:
Input: 'n' = 3, 'k' = 2 and 'arr' = {1, 2, 3}

Output: 2

Explanation: The maximum possible minimum distance will be 2 when 2 cows are placed at positions {1, 3}. Here distance between cows is 2.
Detailed explanation ( Input/output format, Notes, Images )
Input format :
The first line contains two integers ‘n’ and ‘k’ denoting the number of elements in the array and the number of aggressive cows.

The second line contains ‘n’ single space-separated integers denoting the position of the stalls.


Output format :
Return the largest possible minimum distance between cows.


Note :
You do not need to print anything; it has already been handled.
Sample Input 1 :
6 4
0 3 4 7 10 9


Sample Output 1 :
3


Explanation to Sample Input 1 :
The maximum possible minimum distance between any two cows will be 3 when 4 cows are placed at positions {0, 3, 7, 10}. Here distance between cows are 3, 4 and 3 respectively.


Sample Input 2 :
5 2
4 2 1 3 6


Sample Output 2 :
5


Expected time complexity:
Can you solve this in O(n * log(n)) time complexity?


Constraints :
2 <= 'n' <= 10 ^ 5
2 <= 'k' <= n
0 <= 'arr[i]' <= 10 ^ 9
Time Limit: 1 sec.
Hint

Place all the ‘k’ cows in the ‘n’ stalls such that the minimum distance between any two of them is as large as possible.

Approaches (2)
Naive Approach

What we are looking for is that we need to place all the ‘k’ cows in the ‘n’ stalls such that the minimum distance between any two of them is as large as possible.

We need to define a check() function that checks if a distance ‘x’ is possible between each of the cows. We can use a greedy approach here by placing cows at the leftmost possible stalls such that they are at least 'x' distance away from the last-placed cow.

We need to sort the given array/list so once we have our sorted array, we can apply the whole array of the sorted input, and use our function check(x) to find the largest distance possible. And as soon as you reach a position from where it’s not possible to find a distance from which cows could be safe so we basically break the loop.

Time Complexity

O(n ^ 2), where ‘n’ is the number of elements in the given array.

We are applying a check() function along with the binary search. So the total time complexity will be O(n ^ 2).

Space Complexity

O(log(n)), where ‘n’ is the number of elements in the given array.

The array when sorted will take log(n) space, so the overall space complexity will be O(log(n)).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Aggressive Cows
Full screen
Console