Aggressive Cows
Given an array of length ‘N’, where each element denotes the position of a stall. Now you have ‘N’ stalls and an integer ‘K’ which denotes the number of cows that are aggressive. To prevent the cows from hurting each other, you need to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. Return the largest minimum distance.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases. The first line of each test case contains two integers ‘N’ and ‘K’ denoting the number of elements in the array/list and the number of aggressive cows. The second line contains ‘N’ single space-separated integers denoting the elements of the array.

Output format :

For each test case, print the majority element in a separate line.

Note :

You do not need to print anything; it has already been taken care of.

Constraints :

1

Question

Aggressive Cows

Given an array of length ‘N’, where each element denotes the position of a stall. Now you have ‘N’ stalls and an integer ‘K’ which denotes the number of cows that are aggressive. To prevent the cows from hurting each other, you need to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. Return the largest minimum distance.

Input format :

The first line contains a single integer ‘T’ denoting the number of test cases.

The first line of each test case contains two integers ‘N’ and ‘K’ denoting the number of elements in the array/list and the number of aggressive cows.

The second line contains ‘N’ single space-separated integers denoting the elements of the array.

Output format :

For each test case, print the majority element in a separate line.

Note :

You do not need to print anything; it has already been taken care of.

Constraints :

1 <= T <= 5
2 <= N <= 20000
2 <= C <= N
0 <= ARR[i] <= 10 ^ 9

Where ‘T’ is the number of test cases, 'N' is the length of the given array and, ARR[i] denotes the i-th element in the array.

Time Limit: 1 sec.

Accepted Answer

The problem is to assign aggressive cows to stalls in a way that maximizes the minimum distance between any two cows.

Sort the array of stall positions in ascending order.
Use binary search to find the largest minimum distance between cows.
Check if it is possible to assign cows with this minimum distance by iterating through the sorted array.
If it is possible, update the maximum distance and continue binary search for a larger minimum distance.
If it is not possible, continue binary search for a smaller minimum distance.

Accepted Answer

Step 1 -> Gave a brute force solution.
Step 2 -> Interviewer asked me to optimize it.
Step 3 -> Optimized it using Binary Search.

Accepted Answer

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.

Space Complexity: O(logn)Explanation:

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

Time Complexity: O(n^2)Explanation:

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

C++ (g++ 5.4)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(log(N))

    

    Where N is the number of elements in the given array/list.

*/



//    check if a distance of x is possible b/w each cow

bool check(int x, int k, vector &stalls)

{

    //    Greedy approach, put each cow in the first place you can.

    int cowsPlaced = 1, lastPos = stalls[0];



    int n = stalls.size();



    for (int i = 1; i < n; i++)

    {

        if ((stalls[i] - lastPos) >= x)

        {

            cowsPlaced = cowsPlaced + 1;

            if (cowsPlaced == k)

            {

                return true;

            }



            //    Assign current position of stall as the lastPos.

            lastPos = stalls[i];

        }

    }



    return false;

}



int aggressiveCows(vector &stalls, int k)

{

    sort(stalls.begin(), stalls.end());



    int pos = 0;



    //    Iterate through all the stalls and try to find out the largest minimum distance.

    for (int i = 0; i < 1000000000; i++)

    {

        if (check(i, k, stalls))

        {

            pos = i;

        }

        else

        {

            //    Break as soon as it is no more possible to extend the minimum distance.

            break;

        }

    }



    return pos;

}

Java (SE 1.8)

/*

    Time Complexity = O(N^2)

    Space Complexity = O(log(N))



    Where N is the number of elements in the given array/list.

*/



import java.util.ArrayList;

import java.util.Collections;



public class Solution 

{

    //    check if a distance of x is possible b/w each cow

    private static boolean check(int x, int k, ArrayList stalls) 

    {

        //    Greedy approach, put each cow in the first place you can.

        int cowsPlaced = 1, lastPos = stalls.get(0);



        int n = stalls.size();



        for (int i = 1; i < n; i++) 

        {

            

            if ((stalls.get(i) - lastPos) >= x) 

            {

                cowsPlaced = cowsPlaced + 1;

                if (cowsPlaced == k) 

                {

                    return true;

                }



                //    Assign current position of stall as the lastPos.

                lastPos = stalls.get(i);

            }

        }



        return false;

    }



    public static int aggressiveCows(ArrayList stalls, int k) 

    {

        Collections.sort(stalls);



        int pos = 0;



        //    Iterate through all the stalls and try to find out the largest minimum distance.

        for (int i = 0; i < 1000000000; i++) 

        {

            if (check(i, k, stalls)) 

            {

                pos = i;

            } 

            else 

            {

                //    Break as soon as it is no more possible to extend the minimum distance.

                break;

            }

        }



        return pos;

    }

}

Python (3.5)

'''

    Time Complexity = O(N^2)

    Space Complexity = O(log(N))

    

    Where N is the number of elements in the given array/list.

'''



#    check if a distance of x is possible b/w each cow

def check(x, k, stalls):



    #    Greedy approach, put each cow in the first place you can.

    cowsPlaced = 1 

    lastPos = stalls[0]



    n = len(stalls)



    for i in range(1, n):

    

        if ((stalls[i] - lastPos) >= x):

        

            cowsPlaced = cowsPlaced + 1



            if (cowsPlaced == k):

                return True



            #    Assign current position of stall as the lastPos.

            lastPos = stalls[i]

        

    return False



def aggressiveCows(stalls, k):



    stalls.sort()



    pos = 0



    #    Iterate through all the stalls and try to find out the largest minimum distance.

    for i in range(0, 1000000000):



        if (check(i, k, stalls)):

            pos = i



        else:



            #    Break as soon as it is no more possible to extend the minimum distance.

            break



    return pos

Accepted Answer

Binary search

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 Binary Search algorithm on the sorted input, and use our function check(x) to find the largest distance possible.

Steps are as follows :

First of all, consider low and high values for the starting and ending positions of the given array/list.
Let mid be the minimum distance. Check in the sorted array how many positions are available so that the minimum distance between them is this mid.
Now how to do that? Start with the least value in the array and keep ignoring all the elements until you get a difference between the lower element and the current element >= mid or you run out of elements.
Use this idea to find the count of such possible positions. Now if this count is >= c then we already have a possible solution so store it and we now eliminate it from our search space by making low as mid+1, otherwise, we don't store the result as it is not our solution and eliminate it from our search space by making high as mid-1.
Now our only objective is to find the maximum from all the results we have stored until our search space has exhausted.

Space Complexity: O(logn)Explanation:

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

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

Time Complexity: O(nlogn)Explanation:

O(N * log(N)), where ‘N’ is the number of elements in the given array/list.

We are applying a check() function along with the binary search. So the total time complexity will be O(N * log(N)).