time O(N log(max_val - min_val))
space O(1)
State Variables
low1
high8
mid (dist)-
cowsPlaced-/3
Target
1
[0]
2
[1]
4
[2]
8
[3]
9
[4]
Sort stalls. Range of possible distances: low = 1, high = 8.
Pseudocode
Pseudocode
1function aggressiveCows(stalls, k):
2 stalls.sort()
3 low = 1, high = stalls[n-1] - stalls[0]
4 ans = 1
5 while low <= high:
6 mid = (low + high) / 2
7 if canPlaceCows(stalls, k, mid):
8 ans = mid
9 low = mid + 1
10 else:
11 high = mid - 1
12 return ans
13
14function canPlaceCows(stalls, k, dist):
15 count = 1, lastPos = stalls[0]
16 for i from 1 to n-1:
17 if stalls[i] - lastPos >= dist:
18 count++
19 lastPos = stalls[i]
20 if count == k: return true
21 return false