Understanding the Problem
We are given an array representing the positions of stalls along a straight line, such as [1, 2, 4, 8, 9]
. Our goal is to place K
cows in these stalls such that the **minimum distance between any two cows is as large as possible**.
In simpler words, the cows don't like being too close to each other. So, we have to spread them out in such a way that the closest pair of cows is still as far apart as we can manage — while still placing all cows.
This is a classic case of Binary Search on the Answer, where we don’t search through stall positions directly, but instead we ask: “What’s the largest minimum distance we can guarantee between any two cows?”
Step-by-Step Solution with Example
Step 1: Sort the Stall Positions
We begin by sorting the given array. This ensures that we consider stalls in proper order when placing cows.
Input: stalls = [1, 2, 8, 4, 9], cows = 3
Sorted: [1, 2, 4, 8, 9]
Step 2: Apply Binary Search on Distance
We want to find the largest minimum distance possible. Let’s define our search space:
low = 1
: The minimum possible distance (at least 1 unit apart)
high = max(stalls) - min(stalls) = 9 - 1 = 8
: The maximum gap we could try
Step 3: Define the Feasibility Check
We write a helper function to check: "Is it possible to place all cows such that the minimum distance between them is at least mid
?"
We try placing the first cow in the first stall, and then greedily place each next cow in the next stall that is at least mid
away from the last one. If we can place all cows, return true
, else false
.
Step 4: Run Binary Search
We run a binary search loop:
- Find the middle distance
mid = Math.floor((low + high) / 2)
- If placing cows with distance
mid
is possible → move to the right half to try a larger distance
- If not possible → move to the left half to reduce distance
Keep track of the largest mid
value for which placement worked — that will be our answer.
Step 5: Example Walkthrough
For stalls = [1, 2, 4, 8, 9]
and K = 3
, here's what the binary search would do:
Try mid = 4: Place cows at 1, 4, 8 → YES → try bigger
Try mid = 6: Place cows at 1, 9 → only 2 cows → NO → try smaller
Try mid = 5: Place cows at 1, 8 → only 2 cows → NO → try smaller
Try mid = 3: Place cows at 1, 4, 8 → YES → try bigger
Try mid = 4 (again): already checked
Eventually, we find that the largest minimum distance that allows all cows to be placed is 3
.
Edge Cases
- Only One Cow: If
K = 1
, we can place it anywhere. The answer is 0
since no second cow exists to compare distance.
- Stalls Less Than Cows: If
K > N
, it's impossible to place all cows. We return -1
or throw an error.
- All Stalls at Same Position: Example:
[5, 5, 5]
. No positive distance can be maintained → answer is 0
.
- Empty Stall List: No stall to place even a single cow → return
-1
.
Finally
This problem is a perfect example of how binary search can be used in non-obvious ways — not just on arrays, but also on possible “answers”.
It teaches us to focus on feasibility and gradually narrow down the range of possible solutions, ensuring both correctness and efficiency.
Time Complexity: O(N log(MaxDistance))
, where N
is the number of stalls.
It’s a powerful template for solving optimization problems involving placement, distance, and constraints.
Comments
Loading comments...