Array Sorting Binary Search Two Pointers
Proficient Level

Implement the aggressiveCowsDistance method that maximizes the minimum distance between placed cows.

The input contains stall positions stalls, its length size, and the number of cows. Your task is to place all cows in the stalls so that the minimum distance between any two cows is as large as possible.

Only one cow can be placed in a stall. The answer is the largest distance value that can still allow all cows to be placed.

For example, with stalls [1,2,4,8,9] and 3 cows, the best minimum distance is 3.

Example 1
Input:
stalls (int[]) = [1,2,4,8,9]
size (int) = 5
cows (int) = 3
Return:
(int) 3
Example 2
Input:
stalls (int[]) = [1,2,8,4,9]
size (int) = 5
cows (int) = 3
Return:
(int) 3
Example 3
Input:
stalls (int[]) = [1,2,3,4,5]
size (int) = 5
cows (int) = 2
Return:
(int) 4

Sort the stall positions first because placement depends on distance order.

Then use binary search on the possible minimum distance. For a guessed distance, greedily place the first cow in the first stall, then place each next cow in the earliest stall that is at least that distance away from the last placed cow.

If all cows can be placed, the distance is possible, so try a larger distance. Otherwise, try a smaller distance.

Pseudocode:

function canPlaceCows(stalls, size, cows, distance):
    count = 1
    lastPosition = stalls[0]
    for i from 1 to size - 1:
        if stalls[i] - lastPosition >= distance:
            count++
            lastPosition = stalls[i]
    return count >= cows
function aggressiveCowsDistance(stalls, size, cows):
    sort stalls
    left = 1
    right = stalls[size - 1] - stalls[0]
    answer = 0
    while left <= right:
        mid = left + (right - left) / 2
        if canPlaceCows(stalls, size, cows, mid):
            answer = mid
            left = mid + 1
        else:
            right = mid - 1
    return answer
Run your code to see the result.