aggressive cows

29 Jun 2026 · Stone Liu

The problem goes like this…

you are given which is an array of integers. represents the position of the stall. You are also given to represent the number of aggressive cows. The goal is to try and assign all the stalls to cows such that the minimum distance between any two cows is maximized.

Okay… so lets say we have cows and we have all the stalls consecutively: I guess I can assign them in any order maybe? Like if I placed cow on . Then the min distance would be for all of them so I would return .

But lets say we go through the provided example:

Say I picked the first three numbers in stalls. That would mean that all cows would be located at . Well pair wise I would compute the distances among all which would be . But . Clearly this is not the maximum of the sequence. However if I chose the locations then I can see that my pair wise distances would be which . So one brute force way to do this is to just to find all possible combinations of locations and then compute their pairwise conditions. That is pretty bad, its factorial in time so we can disregard the brute force solution.

Okay that was kinda easy to just brute force, for that one example, another thing that I have found is that

This one I don’t even have to check every single pairwise distance. There are stalls for cows, this means that I must choose or which the minimum distance has to be .

Let’s start with a smaller example. on the entire set.

Since this has only cows, I want to keep them maximally distanced. That would be the stalls located at and for a maximum distance of . Okay simple enough. Let’s try . In this case intuitively I want to be able to split this and find the middle distance between and . That would be . But since we don’t have we choose its nearest neighbor which is . Now the min distance would be . Hmmm this leads me to believe that there is potentially a binary search going on here. The task is essentially, for each pair of stalls, we want to perform binary search on each of them and then find the point that maximizes the distance between each of the points on a number line.

If we continue for the mid distance we have remaining would be which is indeed on our number line. The min distance would then devolve into .

If we flip the answer around such that we want to optimize and find some distance such that we can place all the cows under, then run binary search on that value we can reach the solution.

Essentially what is the maximum possible distance you can place cows given stalls? Well that would be the position of the smallest stall vs the largest stall. What is the smallest possible distance you can place two cows? Well that would be . If we do that, then the pseudo-code becomes a lot easier to hash out. Let’s first write the function possible that determines given some distance if its possible to place the cows such that all cows are spaced at-least distance apart.

def possible(self, stalls, k, d):
  remaining_cows = k
  idx = 0
  prev_cow_pos = None
  # Greedily place cows if the position is possible
  while remaining_cows > 0 and idx < len(stalls):
    curr_pos = stalls[idx]
    if prev_cow_pos is None or (curr_pos - prev_cow_pos) >= d:
      prev_cow_pos = curr_pos
      remaining_cows -= 1
    idx += 1
  return remaining_cows == 0

Usually its always good to test these helper functions so lets check…

assert True == possible([2,3,7,11,12,26], 2, 24) # Should be true
assert False == possible([2,3,7,11,12,26], 3, 24) # Should be false
assert False == possible([2,3,7,11,12,26], 3, 12) # Should be false
assert True == possible([2,3,7,11,12,26], 3, 10) # Should be true!
assert False == possible([2,3,7,11,12,26], 4, 7) # Should be false.
assert True == possible([2,3,7,11,12,26], 4, 5) # Should be true.
assert True == possible([2,3,7,11,12,26], 5, 1) # Should be true.

With those checks passing we can write the binary search on …

def aggressiveCows(self, stalls, k):
    stalls = sorted(stalls)
    l = 1
    r = stalls[len(stalls) - 1] - stalls[0]
    opt_d = 1
    while l <= r:
      d = (l + r) // 2
      if self.possible(stalls, k, d):
        # try to expand the distance using binary search.
        l = d + 1
        opt_d = d
      else:
        # If its not possible then we would have to make the distance smaller.
        r = d - 1
    return opt_d

Testing it out on the rudimentary example above…

val = aggressiveCows([2,3,7,11,12,26], 2)
assert val == 24
val = aggressiveCows([2,3,7,11,12,26], 3)
assert val == 10
val = aggressiveCows([2,3,7,11,12,26], 4)
assert val == 5

If we think about the overall time complexity, given stalls and cows, we would perform binary search a total of times. So the overall time complexity would have to be .