
### Problem Statement

###### Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,...,xN (0 <= xi <= 1,000,000,000).

###### His C (2 <= C <= N) cows don't like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ wants to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?

![Aggressive Cows](https://cdn.mos.cms.futurecdn.net/g88wUaSeSxL4yiUBeRo5c6.jpg)

**INPUT**

- **5** _stall_ , **3** _cows_
- **[1,2,8,4,9]** --- _location of each stall_

**OUTPUT**

FJ can put his **3** cows in the stalls at positions **1**, **4** and **8**,
resulting in a minimum distance of **3**.

**Steps To Solve**

- Write out some test cases
  - [1,2,4,8,9] // Stalls Locations
- Think of solution without code
  - So we have 5 stalls and 3 aggressive cows to place in those stalls.
  - Lets see how we can apply binary search here.
  - So the min possible distance between two cows is 0 and the max possible distance is 9 - 1 = 8.
  - The basic idea is to play in this number line from 0 to 8.
  - So what does this number line denotes?
  - It denotes the max min distance between two consecutive cows.
  - Now we have to decrease and increase the length of number line to get the best possible minimum distance .
  - Lets take mid of number line (0 + 8) / 2 = 4. Can we place cows in the distance of 4 and successfully place all our cows ?
  - Lets check , we placed a cow at stall 1 and the next cow at stall 8, as placing the 2nd cow at stall 2 or stall 4 is not possible because distance between stalls is **2 - 1 = 1** and **4 - 1 = 3** respectively and they are less than our minimum distance 4.
  - Did we place all our cows ?
  - No we placed only 2 cows at 1 and 8 and cannot place our 3rd cow following the constraints of minimum distance of 4 and all our stalls are checked for possible placement.
  - So what we do now ?
  - We decrease our minimum distance.
  - One thing to notice here is that if we cannot place our cows at minimum distance of 4 , then we cannot place all of our cows at min distance above 4 and hence our search space is reduced to half,now we only have to check for minimum distance less than 4.
  - So our new mid point is (0 + 4) / 2 = 2 .
  - Can we place our cows at a minimum distance of 2?
  - Yes we can place our cows at stall 1 , stall 4 and stall 8 as **4 - 1 = 3** and **8 - 4 = 4** , greater than min distance 2 and all our cows are covered.
  - Now we want to maximize our min distance , so we cannot stop here.Also we need to discard the left search space as if min distance 2 is possible then min distance 0 , 1 is also possible.
  - Our search space is now reduced to 2 to 4.
  - Again lets take mid (2 + 4) / 2 = 3.
  - Can we place our cows at a minimum distance 3 ?
  - Indeed we can.Lets place our cows at stall 1, stall 4 and stall 8 , **4 - 1 = 3** and **8 - 4 = 5** .
  - So 3 is the maximum minimum distance possible.

```js
var maxDistance = function (stalls, cows) {
  stalls.sort((a, b) => a - b);

  let n = stalls.length;

  let start = 0;
  let end = stalls[n - 1] - stalls[0];
  let ans = -1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    let canplace = canPlace(stalls, mid, cows);
    if (canplace) {
      ans = mid;
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }

  return ans;
};

function canPlace(stalls, mid, cows) {
  let placedCow = 1;
  let prev = stalls[0];
  for (let i = 1; i < stalls.length; i++) {
    if (stalls[i] - prev >= mid) {
      placedCow++;
      prev = stalls[i];

      if (placedCow === cows) return true;
    }
  }

  return false;
}
```

<iframe src="https://codesandbox.io/embed/tic-tac-toe-with-step-4vvv5i?fontsize=14&hidenavigation=1&theme=dark" 
class="w-full"
style="height:500px;"
allow="accelerometer; ambient-light-sensor; camera; encrypted-media; geolocation; gyroscope; hid; microphone; midi; payment; usb; vr; xr-spatial-tracking"
sandbox="allow-forms allow-modals allow-popups allow-presentation allow-same-origin allow-scripts"
/>

###### Time and Space Complexity

The canPlace function will take **O(N)** time , while the while loop will take **O(Largest difference between coordinates after sorting)** i.e **O(Nlog(X&#8345; - X&#x2080;))**.Sorting will take **O(NlogN)**.So Time Complexity is **O(NlogN)**.
Space complexity in this case is **O(1)**.
