Workspace

Problem workspace

3 day streakD

Aggressive Cows / Maximum Minimum Distance

MediumBinary SearchSearch on the answer

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
left0candidate—right8Search candidate values, not input indices
1021428394
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 = 8

Recorded 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

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap