Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Maximize Minimum Distance

HARDProblemSolveExternal Links

Description

You are given an array of integers representing the positions of stalls along a number line, and an integer k representing the number of aggressive cows. Your task is to place all k cows into distinct stalls such that the minimum distance between any two cows is as large as possible.

In other words, among all possible ways to assign k cows to k different stalls, find the arrangement that maximizes the smallest gap between any pair of cows. Return this maximized minimum distance.

For example, if the stalls are at positions [1, 2, 4, 8, 9] and you have 3 cows, you want to spread them out as much as possible. Placing them at positions 1, 4, and 9 gives pairwise distances of 3, 5, and 8 — the minimum of which is 3. No other arrangement produces a larger minimum distance, so the answer is 3.

Examples

Example 1

Input: stalls = [1, 2, 4, 8, 9], k = 3

Output: 3

Explanation: Place cow 1 at stall 1, cow 2 at stall 4, cow 3 at stall 9. The distances between consecutive cows are 4-1=3 and 9-4=5. The minimum distance is 3. We cannot do better — for example, placing at 1, 8, 9 gives a minimum distance of only 1.

Example 2

Input: stalls = [10, 1, 2, 7, 5], k = 3

Output: 4

Explanation: After sorting the stalls become [1, 2, 5, 7, 10]. Place cow 1 at position 1, cow 2 at position 5, cow 3 at position 10. Distances: 5-1=4 and 10-5=5. The minimum distance is 4. Any other arrangement results in a smaller minimum gap.

Example 3

Input: stalls = [2, 12, 11, 3, 26, 7], k = 5

Output: 1

Explanation: After sorting: [2, 3, 7, 11, 12, 26]. With 5 cows and 6 stalls, the stalls are relatively close together. The best arrangement gives a minimum distance of 1. When the number of cows is close to the number of stalls, the achievable minimum distance shrinks because there is less room to spread out.

Constraints

  • 2 ≤ stalls.length ≤ 10^6
  • 0 ≤ stalls[i] ≤ 10^8
  • 2 ≤ k ≤ stalls.length
  • All stall positions are unique

Editorial

Brute Force

Intuition

The most straightforward idea is to try every possible minimum distance and check whether we can place all k cows such that every pair is at least that far apart.

Think of it like setting a thermostat. You want the room as cold as possible (maximum distance). You start at 1 degree and check: "Can I keep all cows at least 1 unit apart?" If yes, try 2. Then 3. Keep going until you find a distance where placement becomes impossible. The last distance that worked is your answer.

The smallest possible minimum distance is 1 (when stalls are adjacent). The largest possible minimum distance is max(stalls) - min(stalls) divided among k-1 gaps. We iterate through every integer distance from 1 upward, and for each one we greedily try to place cows: start at the first stall, then place the next cow at the first stall that is at least dist units away, and so on.

First, we sort the stalls so we can process them in order. Then for each candidate distance, we run the greedy placement check.

Step-by-Step Explanation

Let's trace with stalls = [1, 2, 4, 8, 9], k = 3:

After sorting: [1, 2, 4, 8, 9]. The range is 9 - 1 = 8.

Step 1: Try dist = 1. Place cow 1 at stall 1. Next stall ≥ 1+1=2 → stall 2. Place cow 2 at stall 2. Next stall ≥ 2+1=3 → stall 4. Place cow 3 at stall 4. All 3 cows placed. dist=1 works. Update answer = 1.

Step 2: Try dist = 2. Place cow 1 at stall 1. Next stall ≥ 1+2=3 → stall 4. Place cow 2 at stall 4. Next stall ≥ 4+2=6 → stall 8. Place cow 3 at stall 8. All 3 cows placed. dist=2 works. Update answer = 2.

Step 3: Try dist = 3. Place cow 1 at stall 1. Next stall ≥ 1+3=4 → stall 4. Place cow 2 at stall 4. Next stall ≥ 4+3=7 → stall 8. Place cow 3 at stall 8. All 3 cows placed. dist=3 works. Update answer = 3.

Step 4: Try dist = 4. Place cow 1 at stall 1. Next stall ≥ 1+4=5 → stall 8. Place cow 2 at stall 8. Next stall ≥ 8+4=12 → no stall found. Only 2 cows placed. dist=4 does NOT work.

Step 5: Since dist=4 fails, stop. The answer is the last successful distance: 3.

Result: Return 3.

Brute Force — Testing Each Distance — Watch as we try increasing minimum distances one by one, greedily placing cows at each attempt until placement fails.

Algorithm

  1. Sort the stalls array in ascending order
  2. Define a helper function canPlace(stalls, k, dist) that greedily checks if k cows can be placed with at least dist between consecutive cows:
    • Place the first cow at stalls[0]
    • For each subsequent stall, if the distance from the last placed cow is ≥ dist, place a cow there
    • Return true if at least k cows were placed
  3. Iterate dist from 1 to stalls[n-1] - stalls[0]:
    • If canPlace(stalls, k, dist) is true, update answer = dist
    • If false, stop and return answer
  4. Return answer

Code

#include <vector>
#include <algorithm>
using namespace std;

bool canPlace(vector<int>& stalls, int k, int dist) {
    int count = 1;
    int lastPos = stalls[0];
    for (int i = 1; i < stalls.size(); i++) {
        if (stalls[i] - lastPos >= dist) {
            count++;
            lastPos = stalls[i];
        }
    }
    return count >= k;
}

int aggressiveCows(vector<int>& stalls, int k) {
    sort(stalls.begin(), stalls.end());
    int n = stalls.size();
    int answer = 0;

    for (int dist = 1; dist <= stalls[n - 1] - stalls[0]; dist++) {
        if (canPlace(stalls, k, dist)) {
            answer = dist;
        } else {
            break;
        }
    }

    return answer;
}
def can_place(stalls, k, dist):
    count = 1
    last_pos = stalls[0]
    for i in range(1, len(stalls)):
        if stalls[i] - last_pos >= dist:
            count += 1
            last_pos = stalls[i]
    return count >= k

def aggressive_cows(stalls, k):
    stalls.sort()
    n = len(stalls)
    answer = 0

    for dist in range(1, stalls[n - 1] - stalls[0] + 1):
        if can_place(stalls, k, dist):
            answer = dist
        else:
            break

    return answer
import java.util.*;

class Solution {
    static boolean canPlace(int[] stalls, int k, int dist) {
        int count = 1;
        int lastPos = stalls[0];
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPos >= dist) {
                count++;
                lastPos = stalls[i];
            }
        }
        return count >= k;
    }

    public static int aggressiveCows(int[] stalls, int k) {
        Arrays.sort(stalls);
        int n = stalls.length;
        int answer = 0;

        for (int dist = 1; dist <= stalls[n - 1] - stalls[0]; dist++) {
            if (canPlace(stalls, k, dist)) {
                answer = dist;
            } else {
                break;
            }
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n × (max - min) + n log n)

Sorting takes O(n log n). Then we try every integer distance from 1 to (max - min), and for each distance we run the greedy placement check which takes O(n). So the main loop costs O(n × (max(stalls) - min(stalls))). With stall values up to 10^8, this can mean up to 10^8 × 10^6 = 10^14 operations — far too slow.

Space Complexity: O(1)

We only use a constant number of variables besides the input array. The sort may use O(log n) stack space internally.

Why This Approach Is Not Efficient

The brute force tries every integer distance from 1 to max(stalls) - min(stalls). When stall positions can be up to 10^8 apart, this means potentially 10^8 candidate distances, each requiring an O(n) check — resulting in O(n × 10^8) total work, which is computationally infeasible.

The key observation that makes this problem solvable faster is the monotonic property of the feasibility check:

  • If we can place k cows with minimum distance d, then we can certainly place them with any distance smaller than d (more flexibility).
  • If we cannot place k cows with minimum distance d, then any distance larger than d will also fail (even less flexibility).

This means the feasible distances form a contiguous range: [1, 2, ..., answer] are all feasible, and [answer+1, answer+2, ...] are all infeasible. Whenever we have a sorted search space with a clear boundary between "yes" and "no", we can use binary search to find that boundary in O(log(range)) instead of O(range).

Optimal Approach - Binary Search on Answer

Intuition

Instead of trying every distance from 1 to max-min, we use binary search to zero in on the largest feasible distance directly.

Imagine you are a sound engineer setting the volume on a speaker. You know that below some threshold everything sounds fine, and above it the speaker distorts. Instead of testing volume 1, 2, 3, 4, ... you would jump to the middle (say 50), check if it distorts. If no, jump to 75. If yes, drop to 62. Each test cuts your search space in half. In 7 tests you cover a range of 100.

Here, "distortion" corresponds to "cannot place all k cows." The volume is the minimum distance. We binary search on the minimum distance:

  • lo = 1 (smallest meaningful distance)
  • hi = (max(stalls) - min(stalls)) / (k - 1) (theoretical maximum possible for k cows)
  • At each midpoint, run the same greedy check: place cows left to right, each at least mid apart.
  • If placement works, the answer might be mid or higher → move lo = mid + 1
  • If placement fails, mid is too large → move hi = mid - 1

The greedy placement strategy is straightforward: always place the first cow at the leftmost stall, then place each subsequent cow at the earliest stall that is at least dist away from the last placed cow. This greedy approach is optimal because placing a cow as early as possible gives maximum room for remaining cows.

Step-by-Step Explanation

Let's trace with stalls = [1, 2, 4, 8, 9], k = 3:

After sorting: [1, 2, 4, 8, 9].

Step 1: Set lo = 1, hi = (9 - 1) / (3 - 1) = 4. answer = 0.

Step 2: Iteration 1: mid = (1 + 4) / 2 = 2.

  • Greedy check with dist=2: Place cow1 at 1. Next stall ≥ 3 → stall 4 (cow2). Next stall ≥ 6 → stall 8 (cow3). Placed 3 cows. Feasible!
  • Update answer = 2, lo = mid + 1 = 3.

Step 3: Iteration 2: mid = (3 + 4) / 2 = 3.

  • Greedy check with dist=3: Place cow1 at 1. Next stall ≥ 4 → stall 4 (cow2). Next stall ≥ 7 → stall 8 (cow3). Placed 3 cows. Feasible!
  • Update answer = 3, lo = mid + 1 = 4.

Step 4: Iteration 3: mid = (4 + 4) / 2 = 4.

  • Greedy check with dist=4: Place cow1 at 1. Next stall ≥ 5 → stall 8 (cow2). Next stall ≥ 12 → no stall found. Only 2 cows placed. Not feasible.
  • hi = mid - 1 = 3.

Step 5: lo = 4 > hi = 3. Binary search ends.

Result: Return answer = 3.

Binary Search on Answer — Maximize Minimum Distance — Watch how binary search narrows down the optimal minimum distance by halving the search space at each step, using greedy cow placement to validate each candidate.

Algorithm

  1. Sort the stalls array in ascending order
  2. Define a helper function canPlace(stalls, k, dist):
    • Place the first cow at stalls[0], set count = 1, lastPos = stalls[0]
    • For each subsequent stall stalls[i]:
      • If stalls[i] - lastPos >= dist, place a cow: increment count, update lastPos = stalls[i]
    • Return count >= k
  3. Binary search:
    • lo = 1, hi = (stalls[n-1] - stalls[0]) / (k - 1), answer = 0
    • While lo <= hi:
      • mid = (lo + hi) / 2
      • If canPlace(stalls, k, mid) → answer = mid, lo = mid + 1
      • Else → hi = mid - 1
  4. Return answer

Code

#include <vector>
#include <algorithm>
using namespace std;

bool canPlace(vector<int>& stalls, int k, int dist) {
    int count = 1;
    int lastPos = stalls[0];
    for (int i = 1; i < stalls.size(); i++) {
        if (stalls[i] - lastPos >= dist) {
            count++;
            lastPos = stalls[i];
        }
    }
    return count >= k;
}

int aggressiveCows(vector<int>& stalls, int k) {
    sort(stalls.begin(), stalls.end());
    int n = stalls.size();

    int lo = 1;
    int hi = (stalls[n - 1] - stalls[0]) / (k - 1);
    int answer = 0;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (canPlace(stalls, k, mid)) {
            answer = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return answer;
}
def can_place(stalls, k, dist):
    count = 1
    last_pos = stalls[0]
    for i in range(1, len(stalls)):
        if stalls[i] - last_pos >= dist:
            count += 1
            last_pos = stalls[i]
    return count >= k

def aggressive_cows(stalls, k):
    stalls.sort()
    n = len(stalls)

    lo = 1
    hi = (stalls[n - 1] - stalls[0]) // (k - 1)
    answer = 0

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if can_place(stalls, k, mid):
            answer = mid
            lo = mid + 1
        else:
            hi = mid - 1

    return answer
import java.util.*;

class Solution {
    static boolean canPlace(int[] stalls, int k, int dist) {
        int count = 1;
        int lastPos = stalls[0];
        for (int i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPos >= dist) {
                count++;
                lastPos = stalls[i];
            }
        }
        return count >= k;
    }

    public static int aggressiveCows(int[] stalls, int k) {
        Arrays.sort(stalls);
        int n = stalls.length;

        int lo = 1;
        int hi = (stalls[n - 1] - stalls[0]) / (k - 1);
        int answer = 0;

        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (canPlace(stalls, k, mid)) {
                answer = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return answer;
    }
}

Complexity Analysis

Time Complexity: O(n log n + n log d), where d = max(stalls) - min(stalls)

Sorting the stalls takes O(n log n). The binary search runs for at most O(log d) iterations, where d is the range of stall positions. Each iteration calls canPlace which scans the stalls array in O(n). So the binary search phase costs O(n log d). Overall: O(n log n + n log d). Since d can be at most 10^8, log d ≈ 27, making this extremely efficient.

Space Complexity: O(1)

We use only a constant number of extra variables (lo, hi, mid, answer, count, lastPos). The sort may use O(log n) stack space internally, but no additional data structures are created.