The challenge
Place k cows in distinct stalls to maximize the minimum distance between any two cows.
Distinct signed 32-bit stall coordinates; 2 ≤ k ≤ n. Invalid k returns −1. Input order is arbitrary.
Example
[1, 2, 8, 4, 9], k = 3 → gap 3, placing at 1, 4, 8.
Use the walkthrough below to inspect the input and each state change.
See Maximize minimum distance, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space search · sorted stallsk = 3
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 0
- Middle
- —
- Right
- 8
Step 01 / 6
Search the answer range
The candidate is a minimum gap, rather than an input index. Keep the largest feasible value.
left = 0; right = 8Recorded result so far
Not resolved
View exact input
Input: [1,2,8,4,9] · k = 3
Put it into code
Sort a copy of the coordinates. For a proposed gap, always place the next cow in the earliest stall far enough from the last.
Indices are zero-based. C++ uses C++17 or later.
def maximum_distance(stalls, k):
# Distinct stall coordinates; 2 <= k <= len(stalls).
if k < 2 or k > len(stalls):
return -1
stalls = sorted(stalls) # Preserve the caller's input.
left, right, answer = 0, stalls[-1] - stalls[0], 0
while left <= right:
mid = left + (right - left) // 2
placed, last = 1, stalls[0]
for position in stalls[1:]:
if position - last >= mid:
placed += 1
last = position
if placed >= k:
answer = mid
left = mid + 1
else:
right = mid - 1
return answer#include <algorithm>
#include <vector>
long long maximum_distance(const std::vector<int>& input, int k) {
if (k < 2 || k > static_cast<int>(input.size())) return -1;
auto stalls = input; // Copy before sorting.
std::sort(stalls.begin(), stalls.end());
long long left = 0, right = static_cast<long long>(stalls.back()) - stalls.front(), answer = 0;
while (left <= right) {
long long mid = left + (right - left) / 2, last = stalls[0];
int placed = 1;
for (int i = 1; i < static_cast<int>(stalls.size()); ++i) {
if (stalls[i] - last >= mid) { ++placed; last = stalls[i]; }
}
if (placed >= k) { answer = mid; left = mid + 1; }
else right = mid - 1;
}
return answer;
}