Maximum Tastiness of Candy Basket
Problem
Given an array price where price[i] is the cost of the i-th candy and an integer k, choose exactly k candies. The tastiness of a basket is the smallest absolute difference between any two chosen prices. Return the largest tastiness you can achieve.
price = [13, 5, 1, 8, 21, 2], k = 38def maximum_tastiness(price, k):
price.sort()
def can(gap):
count, last = 1, price[0]
for x in price[1:]:
if x - last >= gap:
count += 1
last = x
return count >= k
lo, hi = 0, price[-1] - price[0]
while lo < hi:
mid = (lo + hi + 1) // 2
if can(mid): lo = mid
else: hi = mid - 1
return lofunction maximumTastiness(price, k) {
price.sort((a, b) => a - b);
const can = (gap) => {
let count = 1, last = price[0];
for (let i = 1; i < price.length; i++) {
if (price[i] - last >= gap) { count++; last = price[i]; }
}
return count >= k;
};
let lo = 0, hi = price[price.length - 1] - price[0];
while (lo < hi) {
const mid = (lo + hi + 1) >> 1;
if (can(mid)) lo = mid; else hi = mid - 1;
}
return lo;
}class Solution {
public int maximumTastiness(int[] price, int k) {
java.util.Arrays.sort(price);
int lo = 0, hi = price[price.length - 1] - price[0];
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPick(price, mid, k)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private boolean canPick(int[] price, int gap, int k) {
int count = 1, last = price[0];
for (int i = 1; i < price.length; i++) {
if (price[i] - last >= gap) { count++; last = price[i]; }
}
return count >= k;
}
}int maximumTastiness(vector<int>& price, int k) {
sort(price.begin(), price.end());
auto can = [&](int gap) {
int count = 1, last = price[0];
for (int i = 1; i < (int)price.size(); i++) {
if (price[i] - last >= gap) { count++; last = price[i]; }
}
return count >= k;
};
int lo = 0, hi = price.back() - price.front();
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (can(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}Explanation
The tastiness is the minimum gap between any two chosen prices, and we want that minimum to be as large as possible. This "maximize the minimum" shape is a classic signal for binary search on the answer.
First sort the prices. After sorting, the smallest difference in any chosen set is always between two adjacent picks, so checking a candidate gap becomes a simple left-to-right scan.
The feasibility test can(gap) asks: can we pick at least k candies so that consecutive picks differ by at least gap? Greedily keep the first price, then walk right and grab the next price whenever it is at least gap away from the last one we kept. Taking the earliest valid price is safe because it leaves the most room for future picks.
Feasibility is monotonic: if a gap works, every smaller gap also works. So we binary-search the largest feasible gap. When can(mid) succeeds we move lo = mid (try bigger); otherwise hi = mid - 1. The search range is [0, max - min]. Note the mid = (lo + hi + 1) / 2 rounding-up so the loop terminates when hunting an upper bound.
Example: price = [13,5,1,8,21,2], k = 3. Sorted is [1,2,5,8,13,21]. With gap = 8 we keep 1, skip to 13 (diff 12), then 21 (diff 8): that is 3 picks, so 8 is feasible. With gap = 9 we keep 1, then 13, but 21 - 13 = 8 < 9, so only 2 picks — not feasible. The answer is 8.