Problem Link - Aggressive Cows in Binary Search
Problem Statement:
Farmer John has built a new long barn, with N stalls. The stalls are located along a straight line at positions x_1, ..., x_N.
His C 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, Farmer John wants to assign the cows to stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
Approach:
- Sorting the Stall Positions: The array (which contains the stall positions) is sorted in ascending order. This is important because the stalls need to be considered in order to calculate the distance between them.
- Binary Search Setup:
- Initialize two pointers:
low
andhigh
:low = 0
: This represents the smallest possible distance between two cows.high = 1e9 + 1
: This represents the largest possible distance (just beyond the maximum possible stall position of 10^9).
- Using Binary Search:
- The loop performs binary search to find the maximum possible minimum distance between cows:
mid
is calculated as the midpoint betweenfirst
andlast
.- The
check
function is called withmid
as the target distance, to check if it’s possible to place all cows with at least this distance between them. Refer for check function: Aggressive Cows in Binary Search - If placing cows with this distance is possible (
canplace == true
), the search continues to the right (increasing the minimum distance by settingfirst = mid
). - If not, the search continues to the left by updating
last = mid
. - Once the binary search completes the value of
first
is printed. This represents the largest minimum distance at which the cows can be placed.
Complexity:
- Time Complexity: Sorting takes
O(n log n)
, Binary search utilizesO(log n)
and the check function takesO(n)
for iterating through the stalls. Total time complexity:O(n log n) + O(log n) + O(n) = O(n log n)
. - Space Complexity:
O(1)
No extra space is used.