Skip to main content

Binary Search

Aggressive Cows Leetcode Solution

Aggressive Cows Problem Description:

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.
aggressive-cows-Problem Description

Aggressive Cows Example :

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.
The minimum distance between cows, in this case, is 1, which also is the largest among all possible ways.

Constraints:

2 <= stalls.size() <= 106
0 <= stalls[i] <= 108
2 <= k <= stalls.size()

Brute Force Approach

To approach the problem, we are given an integer array stalls and an integer k, and we need to determine the maximum possible minimum distance between any two of the k cows placed in the stalls. Each cow must be placed in a unique stall, and the goal is to maximize the smallest distance between any two cows.

What can be the minimum distance between any two cows?

The minimum distance required should be 1 because all stall positions are unique, and the closest two cows can be placed is in adjacent stalls with a difference of 1. This means that in the worst case when we have enough stalls, we can always place cows at a minimum distance of 1 between them.

Now that we know the minimum distance, what would be the maximum distance between any two cows?

The maximum possible distance should be max(stalls) - min(stalls). This is because, in the best case, if k is small enough, the cows can be placed at the farthest possible stalls, achieving the largest possible minimum distance.

Thus, our search space for the answer ranges from 1 to max(stalls) - min(stalls). Now, the problem reduces to finding the largest possible minimum distance that allows us to place k cows in the stalls.

A basic approach is to iterate through all possible values from 1 to max(stalls) - min(stalls) and check whether it is possible to place the cows such that the minimum distance between any two cows is at least a given value.

  • If it is possible, then it is a valid solution.
  • We continue this process until we find the maximum minimum distance that allows us to place all k cows.

We can either start from 1 and go up to max(stalls) - min(stalls) or start from max(stalls) - min(stalls) and go down to 1. The idea is to start from 1 to max(stalls) - min(stalls) and stop whenever we find the point where it's not possible to place the cows, and return the point before it, as it was the maximum valid minimum distance.

Consider stalls = [1, 2, 4, 8, 9] and k = 3.

We start by setting the smallest possible distance as 1 and the largest possible distance as max(stalls) - min(stalls) = 9 - 1 = 8.

We then check how many cows can be placed for different values of the minimum distance:

  • If the minimum distance is 1, cows can still be placed, so it works.
  • If the minimum distance is 2, cows can still be placed, so it works.
  • If the minimum distance is 3, cows can still be placed at stalls [1, 4, 8], so it works.
  • If the minimum distance is 4, it becomes difficult to place 3 cows while maintaining this distance, so it does not work.
  • If the minimum distance is 5, it becomes difficult to place 3 cows while maintaining this distance, so it does not work.

Since 4 is the first point where it's not possible to place k cows, we return 3, the point before it.

Thus, the answer is 3.

We can see that every number from 1 to 3 allows us to place k cows while maintaining the required distance. But as soon as we try 4 or more, it’s no longer possible because we don’t have enough stalls at that distance.

Let's call the maximum possible minimum distance as maxDistance. Any number from maxDistance + 1 to max(stalls) - min(stalls) won’t work because it will always result in fewer than k cows being placed.

However, any number from 1 to maxDistance will allow us to place at least k cows.

Therefore, maxDistance is the largest possible minimum distance between any two cows while ensuring k cows are placed in the stalls. Any number from 1 to maxDistance will work, but as soon as we try maxDistance + 1 or more, it won’t be possible anymore.

aggressive-cows

Explaining the Stall Allocation Process in Real-World Terms

Imagine you have a set of stalls in a barn and k aggressive cows that need to be placed inside the stalls. Your task is to figure out how far apart the cows can be while ensuring that each cow gets a stall. The challenge is to maximize the smallest distance between any two cows while still ensuring all k cows are placed.

Firstly, we should arrange the stalls in ascending order based on their positions by sorting them. Since the cows must be placed in the stalls while maintaining the required minimum distance, sorting the stalls in ascending order helps in systematic placement. Without sorting, placement would be random, making it impossible to determine the correct distances efficiently.

Why is Sorting Required?

Sorting the stall positions is necessary because:

  • Ensures a logical placement order: Without sorting, the stalls might be scattered randomly, making it impossible to systematically place cows at increasing distances.
  • Guarantees correctness: By iterating through stalls in sorted order, we can efficiently check whether the minimum distance x is feasible.
  • Avoids incorrect placements: If stalls were unsorted, we might end up skipping over closer stalls or incorrectly placing cows too far apart.
  • Simplifies implementation: Sorting allows us to traverse the array in one pass while ensuring cows are placed in the optimal order.

Thus, sorting stalls[] before placement ensures that we can correctly determine the maximum minimum distance possible for placing the cows.

Step 1: Setting Up the Process

To start, you need to determine if it’s possible to place the cows fairly for a given x, where x is the minimum distance we are trying to achieve between any two cows.

  • If x is too large, we might not have enough stalls to place all k cows.
  • If x is too small, we might not be maximizing the placement.

Step 2: Placing the Cows in Stalls

To check if placing cows at a given minimum distance x is possible, we iterate through the sorted stalls:

  • We start by placing the first cow in the first stall.
  • For each subsequent stall, we check if it is at least x distance away from the last placed cow.
  • If it is, we place the next cow there.
  • We repeat this until we have placed all k cows.

Step 3: Keeping Track of Placement

To keep track of how many cows are placed, we use a counter cowsPlaced.

  • Every time we successfully place a cow at a stall, we increment cowsPlaced.
  • If at the end, cowsPlaced >= k, then x is a valid minimum distance.

Step 4: Checking if the Goal is Met

Once all cows are placed:

  • If we managed to place at least k cows, then x is valid.
  • If we can’t, then x is too large.

Why This Works in the Real World

Sorting the stalls and placing cows using the largest possible minimum distance is a greedy approach that ensures, we maximize the space between aggressive cows.

  • Checking for a given distance x helps us determine the largest minimum distance possible.
  • Keeping track of cowsPlaced ensures we don’t exceed or miss placing any cow.
  • This method guarantees that we are fairly maximizing the placement while ensuring k cows fit in the stalls.

Ultimately, this process helps us strike a balance between placing the cows as far apart as possible while ensuring all k cows are placed.

💡
Try it Yourself!

Let's understand with an example:

Input: stalls[] = [10, 1, 2, 7, 5], k = 3

Step 1: Sort the Stall Positions

Sorted stalls[] = [1, 2, 5, 7, 10]

Step 2: Define Search Space

  • Minimum Distance (i = 1) (smallest possible distance between two cows).
  • Maximum Distance (i = 9) (10 - 1 = 9, largest possible minimum distance).

Step 3: Check for Each i from 1 to 9

i = 1:

  • Place first cow at stalls[0] = 1
  • Next placement at stalls[1] = 2 (2 - 1 ≥ 1)
  • Next placement at stalls[2] = 5 (5 - 2 ≥ 1)
  • More than 3 cows can be placed → Valid.

i = 2:

  • Place first cow at stalls[0] = 1
  • Next placement at stalls[1] = 2 (2 - 1 < 2 , no, move forward)
  • Next placement at stalls[2] = 5 (5 - 1 ≥ 2 )
  • Next placement at stalls[3] = 7 (7 - 5 ≥ 2 )
  • 3 cows placed → Valid.

i = 3:

  • Place first cow at stalls[0] = 1
  • Next placement at stalls[2] = 5 (5 - 1 ≥ 3)
  • Next placement at stalls[4] = 10 (10 - 5 ≥ 3 )
  • 3 cows placed → Valid.

i = 4:

  • Place first cow at stalls[0] = 1
  • Next placement at stalls[2] = 5 (5 - 1 ≥ 4 )
  • Next placement at stalls[4] = 10 (10 - 5 ≥ 4 )
  • 3 cows placed → Valid.

i = 5:

  • Place first cow at stalls[0] = 1
  • Next placement at stalls[2] = 5 (5 - 1 ≥ 5, no, move forward )
  • Next placement at stalls[3] = 7 (7 - 1 ≥ 5 )
  • Next placement at stalls[4] = 10 (10 - 7 ≥ 5, no, move forward )
  • 2 cows placed → Invalid.

Since i = 4 was the last valid case before an invalid one, the maximum minimum distance is 4.

Output: 4

Steps to Implement the Solution:

Sort the stalls

  • Sorting ensures that we check placements in an ordered manner.

Define the search space

  • The minimum possible distance is 1.
  • The maximum possible distance is stalls[n-1] - stalls[0].

Implement a function to check if a given minimum distance is possible (isPossible)

  • Initialize cowsPlaced = 0 and last = -1.
  • Iterate through the stalls:
    • If it's the first cow or the distance from the last placed cow is at least x, place a cow.
  • Return true if at least k cows are placed.

Perform a linear search for the maximum minimum distance

  • Iterate from low = 1 to high = max possible distance.
  • Use isPossible(stalls, k, i) to check feasibility.
  • If possible, update minDistance.

Return the maximum minimum distance found.

Aggressive Cows / Code Implementation
1. Aggressive Cows solution in c++ Try on Compiler 
class Solution {
    // Function to check if it is possible to place k cows with at least x distance apart
    bool isPossible(vector<int> &stalls, int k, int x)
    {
        // Counter for cows placed
        int cowsPlaced = 0;
        // Variable to store the last placed cow's stall position
        int last = -1;
        
        // Iterate through the stall positions
        for(int i = 0; i < stalls.size(); i++)
        {
            // Place cow if it is the first one or distance condition is met
            if(last == -1 || abs(stalls[i] - last) >= x)
            {
                cowsPlaced++;
                last = stalls[i];
            }
        }
        
        // Return true if we are able to place at least k cows
        return cowsPlaced >= k;
    }

  public:
    // Function to find the largest minimum distance for aggressive cows
    int aggressiveCows(vector<int> &stalls, int k) {
        // Get the number of stalls
        int n = stalls.size();
        
        // Sort the stall positions to ensure correct placement
        sort(stalls.begin(), stalls.end());
        
        // Define the search space for minimum possible and maximum possible distances
        int low = 1;
        int high = stalls[n-1] - stalls[0];
        
        // Variable to store the maximum minimum distance found
        int minDistance = 1;
        
        // Perform linear search from low to high
        for(int i = low; i <= high; i++)
        {
            // If placing cows with distance i is possible, update minDistance
            if(isPossible(stalls, k, i))
                minDistance = i;
        }
        
        // Return the maximum minimum distance possible
        return minDistance;
    }
};

2. Aggressive Cows solution in Java Try on Compiler 
class Solution {
    // Function to check if it is possible to place k cows with at least x distance apart
    private boolean isPossible(int[] stalls, int k, int x) {
        
        // Counter for cows placed
        int cowsPlaced = 0;
        // Variable to store the last placed cow's stall position
        int last = -1;

        // Iterate through the stall positions
        for (int i = 0; i < stalls.length; i++) {
            // Place cow if it is the first one or distance condition is met
            if (last == -1 || Math.abs(stalls[i] - last) >= x) {
                cowsPlaced++;
                last = stalls[i];
            }
        }

        // Return true if we are able to place at least k cows
        return cowsPlaced >= k;
    }

    // Function to find the largest minimum distance for aggressive cows
    public int aggressiveCows(int[] stalls, int k) {
        
        // Get the number of stalls
        int n = stalls.length;
        
        // Sort the stall positions to ensure correct placement
        Arrays.sort(stalls);
        
        // Define the search space for minimum possible and maximum possible distances
        int low = 1;
        int high = stalls[n - 1] - stalls[0];
        
        // Variable to store the maximum minimum distance found
        int minDistance = 1;
        
        // Perform linear search from low to high
        for (int i = low; i <= high; i++) {
            // If placing cows with distance i is possible, update minDistance
            if (isPossible(stalls, k, i))
                minDistance = i;
        }
        
        // Return the maximum minimum distance possible
        return minDistance;
    }
}

3. Aggressive Cows solution in Python Try on Compiler 
class Solution:
    # Function to check if it is possible to place k cows with at least x distance apart
    def isPossible(self, stalls, k, x):
        # Counter for cows placed
        cowsPlaced = 0
        # Variable to store the last placed cow's stall position
        last = -1
        
        # Iterate through the stall positions
        for i in range(len(stalls)):
            # Place cow if it is the first one or distance condition is met
            if last == -1 or abs(stalls[i] - last) >= x:
                cowsPlaced += 1
                last = stalls[i]
        
        # Return true if we are able to place at least k cows
        return cowsPlaced >= k

    # Function to find the largest minimum distance for aggressive cows
    def aggressiveCows(self, stalls, k):
        # Get the number of stalls
        n = len(stalls)
        
        # Sort the stall positions to ensure correct placement
        stalls.sort()
        
        # Define the search space for minimum possible and maximum possible distances
        low = 1
        high = stalls[-1] - stalls[0]
        
        # Variable to store the maximum minimum distance found
        minDistance = 1
        
        # Perform linear search from low to high
        for i in range(low, high + 1):
            # If placing cows with distance i is possible, update minDistance
            if self.isPossible(stalls, k, i):
                minDistance = i
        
        # Return the maximum minimum distance possible
        return minDistance

4. Aggressive Cows solution in Javascript Try on Compiler 
class Solution {
    // Function to check if it is possible to place k cows with at least x distance apart
    isPossible(stalls, k, x) {
        // Counter for cows placed
        let cowsPlaced = 0;
        // Variable to store the last placed cow's stall position
        let last = -1;

        // Iterate through the stall positions
        for (let i = 0; i < stalls.length; i++) {
            // Place cow if it is the first one or distance condition is met
            if (last === -1 || Math.abs(stalls[i] - last) >= x) {
                cowsPlaced++;
                last = stalls[i];
            }
        }

        // Return true if we are able to place at least k cows
        return cowsPlaced >= k;
    }

    // Function to find the largest minimum distance for aggressive cows
    aggressiveCows(stalls, k) {
        // Get the number of stalls
        let n = stalls.length;
        
        // Sort the stall positions to ensure correct placement
        stalls.sort((a, b) => a - b);
        
        // Define the search space for minimum possible and maximum possible distances
        let low = 1;
        let high = stalls[n - 1] - stalls[0];
        
        // Variable to store the maximum minimum distance found
        let minDistance = 1;
        
        // Perform linear search from low to high
        for (let i = low; i <= high; i++) {
            // If placing cows with distance i is possible, update minDistance
            if (this.isPossible(stalls, k, i)) {
                minDistance = i;
            }
        }
        
        // Return the maximum minimum distance possible
        return minDistance;
    }
}

Complexity Analysis of Aggressive Cows (brute force):

Time Complexity: O((max(stalls) - min(stalls)) * n)

The time complexity of the given solution can be broken down into two main parts:

1. Iterating Over Possible Values for Minimum Distance (i):

  • The outer loop iterates from low = 1 (minimum possible distance) to high = max(stalls) - min(stalls) (maximum possible distance).
  • This results in O(high - low + 1) = O(max(stalls) - min(stalls)) iterations in the worst case.

2. Calling the Helper Function (isPossible) for Each i:

  • For each value of i, we call the isPossible function.
  • Inside isPossible, we loop through the stalls array to check if we can place at least k cows with a minimum distance of i. This takes O(n) time, where n is the number of stalls.

3. Combined Time Complexity:

  • Outer Loop: Iterates from 1 to (max(stalls) - min(stalls)), i.e., O(max(stalls) - min(stalls)).
  • Inner Loop (isPossible): Runs O(n) for each iteration of the outer loop.

Thus, the overall time complexity is: O((max(stalls) - min(stalls)) * n)

Where:

  • max(stalls) - min(stalls) is the difference between the largest and smallest stall position (maximum possible distance).
  • n is the number of stalls.

Space Complexity: O(n)

  1. Auxiliary Space Complexity: O(1)
    The solution uses only a few integer variables (minDistance, low, high, last, cowsPlaced), which take O(1) space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    The stalls[] array takes O(n) space.
    Therefore, the total space complexity is O(n).

Will Brute Force Work Against the Given Constraints? 

For the current solution, the time complexity is O((max(stalls) - min(stalls)) × n), where n is the number of stalls (with an upper limit of 10⁶), and max(stalls) - min(stalls) is the maximum possible distance between any two stalls (with an upper limit of 10⁸). In the worst-case scenario, max(stalls) - min(stalls) could be as large as 10⁸, which leads to a time complexity of O((max(stalls) - min(stalls)) * n).

This time complexity can become inefficient when the maximum stall distance is large, particularly when max(stalls) - min(stalls) is close to its upper bound (10⁸) and n is large (up to 10⁶). In such cases, the algorithm may perform a large number of operations (nearly 10¹⁴) and become impractical for large inputs.

This solution may not execute efficiently for all test cases, particularly when max(stalls) - min(stalls) is near its upper limit. While it may work for inputs with smaller values of max(stalls) - min(stalls), it could exceed the time limits for large inputs where max(stalls) - min(stalls) is close to its maximum constraint.

In competitive programming environments, the typical time complexity limit is around 10⁶ operations per test case. Therefore, for inputs with large stall distances, this time complexity could lead to inefficient execution.

How to optimize Aggressive Cows solution?

In the previous approach, we checked every possible value of x (from 1 to max(stalls) - min(stalls)) and verified if it was possible to place k cows with at least x distance apart. This resulted in O(n * (max(stalls) - min(stalls))) time complexity, which was too slow and caused TLE (Time Limit Exceeded).

Now, let’s think about improving this.
The main issue was that we checked every possible value of x, which took too much time.

Can we make this part faster?

Yes! Here’s the hint:

We are searching for the maximum minimum distance between the cows. We know this maximum lies between 1 (minimum possible distance) and max(stalls) - min(stalls) (maximum possible distance).

Now that we know the two endpoints, 1 and max(stalls) - min(stalls), let's make a few observations:

  1. The data structure is sorted:
    The range of possible values for x is naturally sorted from 1 to max(stalls) - min(stalls).
  2. The search space is monotonic:
    • If a certain distance x allows us to place k cows, then any smaller distance will also work.
    • If a certain distance does not allow us to place k cows, then any larger distance will also fail.
    • For the example with the stalls [1, 2, 4, 8, 9] and k = 3, the algorithm will successfully place 3 cows with a minimum distance of 1, 2, and 3. However, when attempting to place the cows with a minimum distance of 4 or more, it will fail, as the stalls are not spaced far enough apart to accommodate all 3 cows while maintaining the required distance.This demonstrates the monotonic property of the problem.
  3. The middle element helps minimize or maximize the search space:
    • If we take the middle value of the current range and check if it works (i.e., can we place all k cows with at least mid distance), we can narrow the search space:
      • If it works, we move to the right half to find a larger valid distance.
      • If it doesn’t work, we move to the left half to find a smaller valid distance.

If we plot a graph with the range of possible minimum distances between cows on the x-axis and the number of cows that can be placed at that distance (f(x)) on the y-axis, we observe the following:

  • For a given minimum distance, we can either successfully place k cows or fail to do so.
  • Before reaching the maximum valid distance (denoted as maxdist), we can place k cows. This is because, for any minimum distance less than maxdist, the conditions allow us to place all k cows, and this trend continues as the distance decreases.
  • Once we go beyond maxdist, we can no longer place k cows. This is because, for any minimum distance greater than maxdist, the conditions for placing k cows are not met.

This showcases the monotonic nature of the problem.

aggressive-cows-graph

Thus, maxdist represents the largest possible minimum distance between any two cows while still being able to place all k cows. Once this number is found, placing k cows remains feasible for any number less than or equal to maxdist.

With these points in mind, it's clear that instead of linearly checking all possible distances from 1 to max(stalls) - min(stalls), we can take the middle value and continually reduce the search space.

Does this approach remind you of something you've seen before?

Yes, we are applying binary search here. By leveraging the sorted and monotonic properties of the range of possible distances between cows, we efficiently narrow down the search space to find the maximum minimum distance that works, instead of checking each value linearly.

💡
How binary search works?

Binary search can help us quickly find the maximum minimum distance between the cows while still allowing us to place k cows.

  • We can simply use binary search to determine the maximum minimum distance possible.
  • Start by taking the middle value between low (1) and high (max(stalls) - min(stalls) ).
  • If this mid value satisfies the condition that we can place k cows with at least mid distance apart, we store it as a potential answer and narrow the search space to the right half, looking for a larger valid value.
  • Otherwise, we move the search to the left half to find a smaller valid value.
  • We continue this process as long as low <= high.
  • Once the condition breaks, the stored answer is returned as the maximum possible minimum distance.

By using binary search, we can cut the search space in half at each step, making the solution much faster and avoiding TLE issues.

Let us understand this approach with a video,

0:00
/1:48

aggressive-cows-Animation Explaination

💡
Try it Yourself!

Let's understand with an example:

Let's walk through a concise dry run of the binary search approach with the example: stalls = [10, 1, 2, 7, 5], k = 3

Step 1: Initial Setup

  1. Sort the stalls:
    stalls = [1, 2, 5, 7, 10]
  2. Define the search space:
    • l = 1 (minimum possible distance)
    • r = 10 - 1 = 9 (maximum possible distance)

First Iteration

  • mid = (1 + 9) / 2 = 5
  • Call isPossible(stalls, k, 5):
    • Place first cow at stalls[0] = 1
    • Next valid placement: stalls[3] = 7 (distance = 6, valid)
    • Only 2 cows placed
  • Since it is not possible, move search range: l = 1, r = 4

Second Iteration

  • mid = (1 + 4) / 2 = 2
  • Call isPossible(stalls, k, 2):
    • Place first cow at stalls[0] = 1
    • Next valid placement: stalls[1] = 2 (distance = 1, too small)
    • Next valid placement: stalls[2] = 5 (distance = 4, valid)
    • Next valid placement: stalls[3] = 7 (distance = 2, valid)
    • Total cows placed = 3 (meets k)
  • Since it is possible, move search range: l = 3, r = 4

Third Iteration

  • mid = (3 + 4) / 2 = 3
  • Call isPossible(stalls, k, 3):
    • Place first cow at stalls[0] = 1
    • Next valid placement: stalls[2] = 5 (distance = 4, valid)
    • Next valid placement: stalls[4] = 10 (distance = 5, valid)
    • Total cows placed = 3 (meets k)
  • Since it is possible, move search range: l = 4, r = 4

Fourth Iteration

  • mid = (4 + 4) / 2 = 4
  • Call isPossible(stalls, k, 4):
    • Place first cow at stalls[0] = 1
    • Next valid placement: stalls[2] = 5 (distance = 4, valid)
    • Next valid placement: stalls[4] = 10 (distance = 5, valid)
    • Total cows placed = 3 (meets k)
  • Since it is possible, move search range: l = 5, r = 4

End of Search: Since l > r, exit the loop. The maximum minimum distance that allows us to place 3 cows is 4.

Final Answer: 4

How to code it up:

Step 1: Define the Helper Function (isPossible)

  • Initialize cowsPlaced = 0 to count the number of cows placed.
  • Initialize last = -1 to track the last stall where a cow was placed.
  • Loop through each stall position:
    • If last is -1 (i.e., placing the first cow) or the current stall is at least x distance apart from last, place a cow:
      • Increment cowsPlaced.
      • Update last to the current stall position.
  • Return true if at least k cows are placed; otherwise, return false.

Step 2: Define the Main Function (aggressiveCows)

  • Get the number of stalls (n = stalls.size()).
  • Sort the stall positions to ensure correct placement.
  • Define the search space:
    • low = 1 → The smallest possible distance.
    • high = stalls[n-1] - stalls[0] → The largest possible distance.
    • minDistance = 1 → Variable to store the maximum minimum distance found.
  • Apply Binary Search:
    • While low ≤ high:
      1. Compute mid = (low + high) / 2 as the candidate distance.
      2. Call isPossible(stalls, k, mid):
        • If true, update minDistance = mid and search for a larger distance (low = mid + 1).
        • If false, search for a smaller distance (high = mid - 1).
  • Return minDistance, which represents the largest minimum distance.
Aggressive Cows solution / Code Implementation
1. Aggressive Cows solution in c++ Try on Compiler 
class Solution {
    // Function to check if it is possible to place k cows with at least x distance apart
    bool isPossible(vector<int> &stalls, int k, int x)
    {
        // Counter for cows placed
        int cowsPlaced = 0;
        // Variable to store the last placed cow's stall position
        int last = -1;
        
        // Iterate through the stall positions
        for(int i = 0; i < stalls.size(); i++)
        {
            // Place cow if it is the first one or distance condition is met
            if(last == -1 || abs(stalls[i] - last) >= x)
            {
                cowsPlaced++;
                last = stalls[i];
            }
        }
        
        // Return true if we are able to place at least k cows
        return cowsPlaced >= k;
    }

  public:
    // Function to find the largest minimum distance for aggressive cows
    int aggressiveCows(vector<int> &stalls, int k) {
        // Get the number of stalls
        int n = stalls.size();
        
        // Sort the stall positions to ensure correct placement
        sort(stalls.begin(), stalls.end());
        
        // Define the search space for minimum possible and maximum possible distances
        int low = 1;
        int high = stalls[n-1] - stalls[0];
        
        // Variable to store the maximum minimum distance found
        int minDistance = 1;
        
        // Perform binary search from low to high
        while(low <= high)
        {
            // If placing cows with distance mid is possible, update minDistance
            int mid = (low+high)/2;
            if(isPossible(stalls, k, mid))
            {
                minDistance = mid;
                low = mid+1;
            }else
                high = mid-1;
        }
        
        // Return the maximum minimum distance possible
        return minDistance;
    }
};

2. Aggressive Cows solution in Java Try on Compiler 
import java.util.Arrays;

class Solution {
    // Function to check if it is possible to place k cows with at least x distance apart
    private boolean isPossible(int[] stalls, int k, int x) {
        // Counter for cows placed
        int cowsPlaced = 0;
        // Variable to store the last placed cow's stall position
        int last = -1;

        // Iterate through the stall positions
        for (int i = 0; i < stalls.length; i++) {
            // Place cow if it is the first one or distance condition is met
            if (last == -1 || Math.abs(stalls[i] - last) >= x) {
                cowsPlaced++;
                last = stalls[i];
            }
        }

        // Return true if we are able to place at least k cows
        return cowsPlaced >= k;
    }

    // Function to find the largest minimum distance for aggressive cows
    public int aggressiveCows(int[] stalls, int k) {
        // Get the number of stalls
        int n = stalls.length;

        // Sort the stall positions to ensure correct placement
        Arrays.sort(stalls);

        // Define the search space for minimum possible and maximum possible distances
        int low = 1;
        int high = stalls[n - 1] - stalls[0];

        // Variable to store the maximum minimum distance found
        int minDistance = 1;

        // Perform binary search from low to high
        while (low <= high) {
            // If placing cows with distance mid is possible, update minDistance
            int mid = (low + high) / 2;
            if (isPossible(stalls, k, mid)) {
                minDistance = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // Return the maximum minimum distance possible
        return minDistance;
    }
}

3. Aggressive Cows solution in Python Try on Compiler 
class Solution:
    # Function to check if it is possible to place k cows with at least x distance apart
    def isPossible(self, stalls, k, x):
        # Counter for cows placed
        cowsPlaced = 0
        # Variable to store the last placed cow's stall position
        last = -1

        # Iterate through the stall positions
        for i in range(len(stalls)):
            # Place cow if it is the first one or distance condition is met
            if last == -1 or abs(stalls[i] - last) >= x:
                cowsPlaced += 1
                last = stalls[i]

        # Return true if we are able to place at least k cows
        return cowsPlaced >= k

    # Function to find the largest minimum distance for aggressive cows
    def aggressiveCows(self, stalls, k):
        # Get the number of stalls
        n = len(stalls)

        # Sort the stall positions to ensure correct placement
        stalls.sort()

        # Define the search space for minimum possible and maximum possible distances
        low = 1
        high = stalls[-1] - stalls[0]

        # Variable to store the maximum minimum distance found
        minDistance = 1

        # Perform binary search from low to high
        while low <= high:
            # If placing cows with distance mid is possible, update minDistance
            mid = (low + high) // 2
            if self.isPossible(stalls, k, mid):
                minDistance = mid
                low = mid + 1
            else:
                high = mid - 1

        # Return the maximum minimum distance possible
        return minDistance

4. Aggressive Cows solution in Javascript Try on Compiler 
class Solution {
    // Function to check if it is possible to place k cows with at least x distance apart
    isPossible(stalls, k, x) {
        // Counter for cows placed
        let cowsPlaced = 0;
        // Variable to store the last placed cow's stall position
        let last = -1;

        // Iterate through the stall positions
        for (let i = 0; i < stalls.length; i++) {
            // Place cow if it is the first one or distance condition is met
            if (last === -1 || Math.abs(stalls[i] - last) >= x) {
                cowsPlaced++;
                last = stalls[i];
            }
        }

        // Return true if we are able to place at least k cows
        return cowsPlaced >= k;
    }

    // Function to find the largest minimum distance for aggressive cows
    aggressiveCows(stalls, k) {
        // Get the number of stalls
        let n = stalls.length;

        // Sort the stall positions to ensure correct placement
        stalls.sort((a, b) => a - b);

        // Define the search space for minimum possible and maximum possible distances
        let low = 1;
        let high = stalls[n - 1] - stalls[0];

        // Variable to store the maximum minimum distance found
        let minDistance = 1;

        // Perform binary search from low to high
        while (low <= high) {
            // If placing cows with distance mid is possible, update minDistance
            let mid = Math.floor((low + high) / 2);
            if (this.isPossible(stalls, k, mid)) {
                minDistance = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        // Return the maximum minimum distance possible
        return minDistance;
    }
}

Time Complexity : O(n * log d)

The algorithm primarily consists of two key operations:

1: Sorting the Stalls

The stalls are sorted in O(n log n) time using a sorting algorithm (e.g., quicksort or mergesort).
Let n be the number of stalls.

2: Binary Search Over Distance

  • The search space for binary search is the range [1, max(stalls) - min(stalls)].
  • The maximum difference between any two stalls is O(10⁹) in the worst case (as per problem constraints), but the effective range of distances is at most O(n) because the stalls are distinct.
  • Binary search runs in O(log d), where d is the difference between the largest and smallest stall position.

3: isPossible() Function

  • The isPossible function iterates through the n stalls to check if the cows can be placed with at least mid distance.
  • This takes O(n) time per call.
  • In the worst case, isPossible is called O(log d) times.

Final Complexity Calculation

  • Sorting: O(n log n)
  • Binary Search: O(log d)
  • Each isPossible() Call: O(n)
  • Total isPossible Calls: O(log d)
  • Total Complexity: O(n log ⁡n)+O(n log⁡ d)
  • Since d ≈ 10⁸ and n = 10⁶ in the worst case, the time complexity of the algorithm is O(n * log d).
  • Final Complexity: O(n * log d)

Space Complexity : O(n)

  1. Auxiliary Space Complexity: O(1)
    The algorithm only uses a few integer variables. These are just primitive variables that occupy O(1) space.
    Therefore, the auxiliary space complexity is O(1).
  2. Total Space Complexity: O(n)
    The input stalls array takes O(n) space.
    Therefore, the total space complexity is O(n).

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems.

1. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours.Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.Return the minimum integer k such that she can eat all the bananas within h hours.

2. Capacity To Ship Packages Within D Days

A conveyor belt has packages that must be shipped from one port to another within D days.The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within D days.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8