DAY 79 - Aggressive Cows Problem
Tags: leetcode, coding, codenewbie, algorithms
Published: 2023-08-21 17:35:36

Hey Guys! It's day 79 and we are going to do another binary Search question.

---


## Problem: [Aggressive Cows Placement](https://www.codingninjas.com/studio/problems/aggressive-cows_1082559)

In this article, we'll explore an approach to solving the problem of placing cows in stalls in an aggressive manner, ensuring a minimum distance between them. This problem can be approached using binary search to find the maximum possible minimum distance between the cows.

### Problem Description:

You are given an array ‘arr’ of size ‘n’ which denotes the position of stalls.
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.
Find the maximum possible minimum distance.

---

### Example 1:


![ex](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uyqslqkrn08r505kza46.png)

---

### Approach Overview

The problem can be solved using a binary search approach to find the maximum possible minimum distance between the cows. The idea is to start with a range of possible distances (from 0 to the maximum possible distance) and use binary search to narrow down the range until the desired distance is found.

The key components of the approach are as follows:

- The `canPlace` function determines whether it is possible to place the given number of cows (`k`) in the stalls while maintaining a minimum distance of `dist` between them. It iterates through the sorted `stalls` array, keeping track of the number of cows placed and the last position of the placed cow. If the condition is satisfied for the required number of cows, the function returns `true`, indicating that placement is possible.

- The `aggressiveCows` function sorts the `stalls` array and initializes the lower (`s`) and upper (`e`) bounds for the binary search. It then performs a binary search between the bounds, calling the `canPlace` function to check if placing `k` cows is possible with the current minimum distance `mid`. If possible, the `result` variable is updated, and the search continues on the right side of the search range; otherwise, the search narrows down on the left side.

**Code:**

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

bool canPlace(vector<int>& stalls, int k, int dist){
    int cows = 1;
    int lastPos = stalls[0];
    for(int i = 1; i < stalls.size(); i++){ // Start from index 1
        if(stalls[i] - lastPos >= dist){
            cows++;
            lastPos = stalls[i];
        }
    }
    return cows >= k; // Check if the required number of cows can be placed
}

int aggressiveCows(vector<int> &stalls, int k)
{
    sort(stalls.begin(), stalls.end());
    int s = 0; // Lower bound for binary search
    int e = stalls[stalls.size()-1] - stalls[0]; // Upper bound for binary search

    int result = 0; // Initialize the result variable

    while(s <= e){
        int mid = s + (e - s) / 2;
        if(canPlace(stalls, k, mid)){
            result = mid; // Update result if placing cows is possible
            s = mid + 1;
        }
        else{
            e = mid - 1;
        }
    }

    return result;
}

```

### Complexity Analysis

The time complexity of the solution is O(N * log M), where N is the number of stalls and M is the difference between the maximum and minimum stall positions. The binary search performs a logarithmic number of iterations (log M), and for each iteration, the `canPlace` function is called, which takes linear time in the size of the stalls array.

The space complexity of the solution is O(1), as it uses a constant amount of extra space regardless of the input size.

| Complexity | Notation | Explanation |
|------------|----------|-------------|
| Time       | O(N * log M) | The binary search performs log M iterations, and for each iteration, the canPlace function takes linear time. |
| Space      | O(1)     | The algorithm uses a constant amount of extra space. |