Aggressive Cows

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.

Print the maximum possible minimum distance. (link)

Leetcode link

Example 1:

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.

Example 2:

Input:
6 4
0 3 4 7 10 9
Output
3

Explanation Example 2: 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.

Example 3 :

Input
5 2
4 2 1 3 6
Output
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.

Solution

We must determine the maximum of the minimum distance between any two stalls once the cows are positioned. The provided array represents the coordinates of the stalls. To enhance clarity, arrange the coordinates in ascending order.

The image above illustrates the arrangement of cows in the designated stalls. It is evident that determining the minimum distance in the distribution can be achieved by calculating the distance between consecutive stalls containing cows. In this particular layout, the minimum distance is 1.

This configuration boasts a minimum distance of 3, and the maximum achievable minimum distance between cow stalls is set at 3.

Answer Range: minimum distance -> [1, scale_length]

Our response falls within the range of 1 to the scale's coordinates because, when considering two cows, the maximum distance between them can be realized by placing one at the first stall and the other at the last stall. Here, the minimum/maximum distance between any two cows corresponds to the scale's range.

scale_length = maximum_coordinate - minimum_coordinate

Brute force approach

In this method, we initiate the process with the number 1 and continue checking up to the maximum distance value where the configuration becomes unfeasible. Our systematic approach always involves initially positioning the cow at the first stall.

Note: We added 1 to the scale_length because the minimum distance between the two cows can also be equal to the scale_length.

Time - O(nlogn) + O(max-min) * O(n)

Space - O(1)

import java.util.Arrays;

public class Solution {
    public static int aggressiveCows(int []stalls, int k) {
        Arrays.sort(stalls);
        int min = stalls[0];
        int max = stalls[stalls.length-1];

        for(int gap=1; gap<=(max-min+1); gap++){
            if(isPossible(stalls, k, gap)){
                continue;
            }else{
                return gap-1;
            }
        }
        return -1;
    }

    public static boolean isPossible(int[] stalls, int k, int gap){
        int last = stalls[0];
        int cowsCount = 1;
        for(int i=1; i<stalls.length; i++){
            if(stalls[i]-last>=gap){
                last = stalls[i];
                cowsCount+=1;
            }
            if(cowsCount==k) return true;
        }

        return false;
    }
}

Optimal Approach

Binary Search is applicable in this case as the solution is within a specific range. Within this range, there exist two segments—one that fulfills the given configuration and another that does not.

If the minimum gap is set to 1, 2, and 3, the cows can comfortably occupy the provided stalls. However, this arrangement is not possible for any remaining gaps.

In the binary search, we position the low at 1 and the high at the scale_length + 1. We compute the midpoint and verify whether it satisfies the condition. If the midpoint is satisfactory, it implies that the values to the left of the midpoint also meet the condition. Therefore, we update the low to mid + 1 to obtain the maximum value. On the other hand, if the midpoint fails to satisfy the condition, we adjust the high to mid - 1.

The reason for returning the high value is that throughout the binary search, high points to the value that fails to meet the specified condition. When the binary search concludes, high points to the value that satisfies the condition, while low points to the value that does not.

Time - O(nlogn) + O(logn) * O(n)

Space - O(1)

import java.util.Arrays;

public class Solution {
    public static int aggressiveCows(int []stalls, int k) {
        Arrays.sort(stalls);
        int min = stalls[0];
        int max = stalls[stalls.length-1];

        int low = 1;
        int high = (max-min+1);

        while(low<=high){
            int mid = (low+high)/2;

            if(isPossible(stalls, k, mid)){
                low = mid+1;
            }else{
                high = mid-1;
            }
        }

        return high;
    }

    public static boolean isPossible(int[] stalls, int k, int gap){
        int last = stalls[0];
        int cowsCount = 1;
        for(int i=1; i<stalls.length; i++){
            if(stalls[i]-last>=gap){
                last = stalls[i];
                cowsCount+=1;
            }
            if(cowsCount==k) return true;
        }
        return false;
    }
}