Aggressive Cows

You are given an array with unique elements of stalls[],which denote the position of a stall. You are also given an integer k which denotes the number of aggressive cows. Your task is to assign stalls to k cows such that the minimum distance between any two of them is the maximum possible.

Examples :

Input: stalls[] = [1, 2, 4, 8, 9], k = 3
Output: 3
Explanation: The first cow can be placed at stalls[0], 
the second cow can be placed at stalls[2] and
the third cow can be placed at stalls[3].
The minimum distance between cows, in this case, is 3, which also is the largest among all possible ways.

Input: stalls[] = [10, 1, 2, 7, 5], k = 3
Output: 4
Explanation: The first cow can be placed at stalls[0],
the second cow can be placed at stalls[1] and
the third cow can be placed at stalls[4].
The minimum distance between cows, in this case, is 4, which also is the largest among all possible ways.

Input: stalls[] = [2, 12, 11, 3, 26, 7], k = 5
Output: 1
Explanation: Each cow can be placed in any of the stalls, as the no. of stalls are exactly equal to the number of cows.
The minimum distance between cows, in this case, is 1, which also is the largest among all possible ways.

Constraints:
2 <= stalls.size() <= 10⁶
0 <= stalls[i] <= 10⁸
1 <= k <= stalls.size()

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int aggressiveCows(vector<int>& stalls, int k) {
        sort(stalls.begin(), stalls.end());
        
        auto canPlaceCows = [&](int minDistance) {
            int lastPosition = -1e9;
            int placedCows = 0;
            
            for (int stall : stalls) {
                if (stall - lastPosition >= minDistance) {
                    lastPosition = stall;
                    placedCows++;
                    if (placedCows == k) {
                        return true;
                    }
                }
            }
            return false;
        };
        
        int left = 1;
        int right = stalls.back() - stalls.front();
        
        while (left < right) {
            int midDistance = left + (right - left) / 2;
            if (canPlaceCows(midDistance)) {
                left = midDistance + 1;
            } else {
                right = midDistance;
            }
        }
        
        return left - 1;
    }
};

class Solution:
    def aggressiveCows(self, stalls, k):
        stalls.sort()
        
        def canPlaceCows(minDistance):
            lastPosition = -float('inf')
            placedCows = 0
            
            for stall in stalls:
                if stall - lastPosition >= minDistance:
                    lastPosition = stall
                    placedCows += 1
                    if placedCows == k:
                        return True
            return False
        
        left = 1
        right = stalls[-1] - stalls[0]
        
        while left < right:
            midDistance = left + (right - left) // 2
            if canPlaceCows(midDistance):
                left = midDistance + 1
            else:
                right = midDistance
        
        return left - 1

Time Complexity

• Sorting the Stalls:
  • Sorting the array of stalls requires \(O(n \log n)\), where \(n\) is the number of stalls.
• Binary Search:
  • The range for the binary search is from \(1\) to \((stalls.back() – stalls.front())\), which is the maximum possible distance. Let this range be \(D\).
  • Each step of the binary search halves the range, so the number of iterations is \(O(\log D)\).
• Placement Check:
  • For each mid-distance during binary search, the canPlaceCows function is called.
  • The function iterates through all \(n\) stalls, taking \(O(n)\) per call.
  • The total cost of placement checks is \(O(n \cdot \log D)\).
• Overall Time Complexity:

  The total time complexity is \(O(n \log n + n \cdot \log D)\), where \(O(n \log n)\) is for sorting and \(O(n \cdot \log D)\) is for binary search with placement checks.

Space Complexity

• Input Storage:
  • The stalls array is used as input and sorted in place, requiring \(O(n)\) space.
• Auxiliary Variables:
  • Binary search uses a few integer variables (\(left\), \(right\), \(midDistance\)) and loop counters, consuming \(O(1)\) space.
  • The lambda function canPlaceCows uses a few additional variables, also requiring \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the input array.