Aggressive Cows

Q: What is the time complexity of Aggressive Cows?

Sorting takes O(n log n) and the binary search O(n log D) , where D is the span of the stalls divided by k-1 . Besides a sorted copy, the memory is O(1) .

Q: Why does the first cow always go in the leftmost stall?

Take any placement that works and move its leftmost cow to the leftmost stall. That cow only moves away from the others, so no distance shrinks, and some best placement uses the leftmost stall.

Q: How do you spot a binary search on the answer?

The question asks for the largest or smallest value for which something is possible, checking one value is much easier than finding the best one, and the answers flip only once as the value grows. Here the value is the gap and the check is the greedy placement.

MediumBinary search Sorting Greedy

+10

A barn has stalls along one straight line, and stalls[i] is the position of stall i. The positions are all different and come in no particular order. You must put k cows into k different stalls, and the cows fight when they stand close, so you want the two closest cows as far apart as you can get them.

Return the largest possible value of the smallest distance between any two cows.

Function

aggressiveCows(stalls: integer-array, k: integer) → integer

stallsinteger-array: the distinct stall positions, in any order
kinteger: the number of cows to place
Returnsinteger: the largest possible smallest distance between two cows

Constraints

2 ≤ stalls.length ≤ 5000
0 ≤ stalls[i] ≤ 10⁹
All positions in stalls are distinct.
2 ≤ k ≤ stalls.length

Examples

Input: stalls = [10, 1, 7, 4, 15]k = 3
Output: 6
Explanation: Cows at 1, 7 and 15 stand 6 and 8 apart. A gap of 7 fails: after 1 the next cow goes to 10, and no stall is at 17 or beyond.

Follow-up

What changes if the stalls stand on a circle, so the last stall in order is also a neighbour of the first?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

Fix a gap and ask: can k cows stand with every two at least that far apart? One greedy pass over the sorted stalls answers it. The answer flips from yes to no once as the gap grows, so binary search finds the last yes.

Sort, then try every gap in turn

Correct, but does not finish on the largest tests

Intuition

Sort the positions. The two closest cows are then always neighbours, so a gap g works when every pair of neighbouring cows is at least g apart.

To test a gap, put a cow in the leftmost stall, then one in every stall at least g past the last cow. This greedy placement fits the most cows any placement can. Line up any working placement from the left: greedy's cow i is never to the right of that placement's cow i, so greedy finds a stall for its next cow no later.

A gap of 1 always works, so try g = 2, 3, ... and stop at the first gap that places fewer than k cows. In the first example gap 6 places 3 cows and gap 7 only 2, so the answer is 6.

With two cows and stalls at 0 and 10^9, that is about 10^9 passes over 5000 stalls, 5 × 10^12 steps.

Algorithm

Sort the positions.
Write the check for a gap g: one cow at pos[0], then a cow at every stall where pos[i] - last ≥ g, counting the cows.
Start with gap = 1.
While the check for gap + 1 places at least k cows, add 1 to gap.
Return gap.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    gap = 1  # positions are distinct, so a gap of 1 always fits every cow
    while cowsPlaced(pos, gap + 1) >= k:
        gap += 1
    return gap

Binary search on the gap

Intuition

A placement with every gap at least g+1 also has every gap at least g, so the checks read yes, ..., yes, no, ..., no. Binary search finds the last yes.

Search from lo = 1, which always works, to hi = the span divided by k-1, rounded down: k cows leave k-1 gaps inside the span, so the smallest cannot be larger. A passing check sets lo = mid, so mid must round up; rounded down, lo = 5 and hi = 6 repeat forever.

On the first example the span is 14 and k = 3, so hi = 7. Gap 4 passes, gap 6 passes, gap 7 fails, and the range closes on 6.

A range up to 10^9 wide closes in about 30 checks of 5000 stalls, roughly 150,000 steps.

Algorithm

Sort the positions.
Set lo = 1 and hi = (pos[n-1] - pos[0]) / (k-1), rounded down.
While lo < hi, take mid = lo + (hi - lo + 1) / 2.
If the greedy check at mid places at least k cows, set lo = mid; otherwise set hi = mid - 1.
Return lo.

def cowsPlaced(pos, gap):
    count, last = 1, pos[0]  # the first cow takes the leftmost stall
    for p in pos[1:]:
        if p - last >= gap:
            count += 1
            last = p
    return count


def aggressiveCows(stalls, k):
    pos = sorted(stalls)
    lo = 1  # positions are distinct, so a gap of 1 always works
    hi = (pos[-1] - pos[0]) // (k - 1)  # k-1 gaps share the whole span
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # round up so lo = mid always moves
        if cowsPlaced(pos, mid) >= k:
            lo = mid  # mid fits, so the answer is mid or larger
        else:
            hi = mid - 1  # mid does not fit, so the answer is smaller
    return lo

Pitfalls and edge cases

Skipping the sort. On the unsorted [10, 1, 7, 4, 15] with gap 6, the check starts at 10, finds no later stall 6 past it, and reports one cow.
Rounding mid down while a pass sets lo = mid. Once hi = lo + 1 the range stops shrinking and the loop never ends.
Testing for exactly k cows. At gap 1 the first example places 5 cows, more than 3, yet the gap works; test count ≥ k.
Starting the cow count at 0. The cow in the leftmost stall counts, so the count starts at 1.

Frequently asked questions3

What is the time complexity of Aggressive Cows?

Sorting takes O(n log n) and the binary search O(n log D), where D is the span of the stalls divided by k-1. Besides a sorted copy, the memory is O(1).

Why does the first cow always go in the leftmost stall?

Take any placement that works and move its leftmost cow to the leftmost stall. That cow only moves away from the others, so no distance shrinks, and some best placement uses the leftmost stall.

How do you spot a binary search on the answer?

The question asks for the largest or smallest value for which something is possible, checking one value is much easier than finding the best one, and the answers flip only once as the value grows. Here the value is the gap and the check is the greedy placement.

def aggressiveCows(stalls, k):
    # Write code here

Test #1

Test #2

Test #3

Arguments

stalls = [10, 1, 7, 4, 15]
k = 3

Expected Output