Problem Statement

Given an array nums of size n, which denotes the positions of stalls, and an integer k, which denotes the number of aggressive cows, assign stalls to k cows such that the minimum distance between any two cows is the maximum possible. Find the maximum possible minimum distance.

Examples

Example 1:

Input: nums = [0, 3, 4, 7, 10, 9], k = 4
Output: 3

Explanation: The maximum possible minimum distance between any two cows will be
3 and 4 cows are placed at positions [0, 3, 7, 10].
Here the distances between cows are 3, 4, and 3 respectively. We cannot make the minimum distance greater than 3 in any ways.

Example 2:

Input: nums = [4, 2, 1, 3, 6], k = 2
Output: 5

Explanation:
First sort the array: [1, 2, 3, 4, 6] to make it easier to calculate
the distances between stalls.

We have to place two cows.
For distance 1: c1 can be at 1 and c2 be at 2, the difference is 1
For distance 2: c1 can be at 1 and c2 be at 3, the difference is 2
For distance 3: c1 can be at 1 and c2 be at 4, the difference is 3
For distance 5: c1 can be at 1 and c2 be at 6, the difference is 5

The largest possible minimum distance between any two cows is 5,
achieved by placing one cow at position 1 and the other at position 6.

Different Approaches

1️⃣ Brute Force (Linear Search):

Intuition:

The extremely naive approach is to use linear search to check all possible distances from 1 to (max-min), where max is the maximum element of the array and min is the minimum element of the array. The maximum distance for which the cows can be placed, will be our answer.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to check if we can place 'cows' cows
    with at least 'dist' distance apart in 'stalls' */
    bool canWePlace(vector<int> &nums, int dist, int cows) {
        
        // Size of array
        int n = nums.size(); 
        
        // Number of cows placed
        int cntCows = 1; 
        
        // Position of last placed cow
        int last = nums[0]; 
        
        for (int i = 1; i < n; i++) {
            if (nums[i] - last >= dist) {
                
                // Place next cow
                cntCows++; 
                
                // Update the last location
                last = nums[i]; 
            }
            if (cntCows >= cows) return true;
        }
        return false;
    }

public:
    /* Function to find the maximum possible minimum
    distance 'k' cows can have between them in 'stalls' */
    int aggressiveCows(vector<int> &nums, int k) {
        
        // Size of array
        int n = nums.size(); 
        // Sort the nums
        sort(nums.begin(), nums.end());

        int limit = nums[n - 1] - nums[0];
        for (int i = 1; i <= limit; i++) {
            if (canWePlace(nums, i, k) == false) {
                return (i - 1);
        }
    }
    //Retrun the answer
    return limit;
    }
};

int main() {
    vector<int> nums = {0, 3, 4, 7, 10, 9};
    int k = 4;

    // Create an instance of the Solution class
    Solution sol;

    int ans = sol.aggressiveCows(nums, k);

    // Output the result
    cout << "The maximum possible minimum distance is: " << ans << "\n";

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N log N) + O(N * (max - min)), where N is size of the array, max is the maximum element in array, min is the minimum element in array.
  • O(N log N) for sorting the array.
  • The outer loop runs for 1 to (max-min) to check all possible distances.
  • The inner loop runs for N times.
• Space Complexity: O(1)

2️⃣ Binary Search

This is the starting of another pattern of the binary search on answer

• min of max
• max of min

Intuition:

The idea is to use binary search as the search range from [1, max - min] is sorted.

Dry Run:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to check if we can place 'cows' cows
    with at least 'dist' distance apart in 'stalls' */
    bool canWePlace(vector<int> &nums, int dist, int cows) {
        
        // Size of array
        int n = nums.size(); 
        
        // Number of cows placed
        int cntCows = 1; 
        
        // Position of last placed cow
        int last = nums[0]; 
        
        for (int i = 1; i < n; i++) {
            if (nums[i] - last >= dist) {
                
                // Place next cow
                cntCows++; 
                
                // Update the last location
                last = nums[i]; 
            }
            if (cntCows >= cows) return true;
        }
        return false;
    }

public:
    /* Function to find the maximum possible minimum
    distance 'k' cows can have between them in 'stalls' */
    int aggressiveCows(vector<int> &nums, int k) {
        
        // Size of array
        int n = nums.size(); 
        // Sort the nums
        sort(nums.begin(), nums.end());
        
        int low = 1, high = nums[n - 1] - nums[0];

        //Apply binary search:
        while (low <= high) {
            int mid = (low + high) / 2;
            if (canWePlace(nums, mid, k) == true) {
                low = mid + 1;
            }
            else high = mid - 1;
        }
        return high;
    }
};

int main() {
    vector<int> nums = {0, 3, 4, 7, 10, 9};
    int k = 4;

    // Create an instance of the Solution class
    Solution sol;

    int ans = sol.aggressiveCows(nums, k);

    // Output the result
    cout << "The maximum possible minimum distance is: " << ans << "\n";

    return 0;
}

Complexity Analysis:

• Time Complexity: O(N log N) + O(N * log(max-min)), where N is the size of the array, max is the maximum element in array, min is the minimum element in array.
  • O(N logN): for sorting the array.
  • O(log (max-min)): The outer loop.
  • O(N): The inner loop runs for N times.
• Space Complexity: O(1)