Maximum Tastiness of Candy Basket
Maximum Tastiness of Candy Basket is a medium binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on the answer), runs in O(n log n + n log M) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (try every pairwise difference) up.
Problem
A shop sells candies, and price[i] is the price of the i-th candy. You want to put together a basket of exactly k different candies (different indices; their prices may be equal).
The tastiness of a basket is the smallest absolute difference between the prices of any two candies in it. Return the largest tastiness any basket of k candies can have.
Examples
Example 1
- Input
price = [20, 3, 11, 7, 15, 1], k = 3- Output
9- Why
- Pick the prices 1, 11 and 20. The closest pair is 11 and 20, which differ by 9, and no choice of three does better.
Example 2
- Input
price = [4, 9, 4], k = 2- Output
5- Why
- Taking 4 and 9 gives a difference of 5; taking the two 4s would give 0.
Example 3
- Input
price = [6, 6, 6, 6], k = 3- Output
0- Why
- All prices are equal, so any two chosen candies differ by 0.
Constraints
2 <= k <= price.length <= 10^51 <= price[i] <= 10^9
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every pairwise difference) | O(n³) | O(1) |
| Optimal (binary search on the answer) | O(n log n + n log M) | O(1) |
1Brute force (try every pairwise difference)
O(n³)There are O(n²) candidate differences and each greedy check is O(n).O(1)Only counters besides the sort.The best tastiness is always the difference of some pair of prices, so collect every pairwise difference and test each one as a candidate gap. A candidate d is feasible when a greedy scan over the sorted prices (take the first price, then the next price at least d above the last taken one) collects k candies. Return the largest feasible candidate.
- Sort price.
- For every pair i < j, let d = price[j] - price[i].
- Greedy check: take price[0], then every price that is at least d above the last taken one; count them.
- If the count reaches k, update the answer with d.
- Return the best d found.
class Solution {
public int maximumTastiness(int[] price, int k) {
Arrays.sort(price);
int n = price.length, best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int d = price[j] - price[i];
if (d > best && canPick(price, k, d)) best = d;
}
return best;
}
private boolean canPick(int[] price, int k, int d) {
int count = 1, last = price[0];
for (int i = 1; i < price.length && count < k; i++)
if (price[i] - last >= d) {
count++;
last = price[i];
}
return count >= k;
}
}class Solution:
def maximumTastiness(self, price: List[int], k: int) -> int:
price.sort()
n = len(price)
best = 0
for i in range(n):
for j in range(i + 1, n):
d = price[j] - price[i]
if d > best and self.canPick(price, k, d):
best = d
return best
def canPick(self, price: List[int], k: int, d: int) -> bool:
count, last = 1, price[0]
for p in price[1:]:
if count >= k:
break
if p - last >= d:
count += 1
last = p
return count >= kclass Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
sort(price.begin(), price.end());
int n = price.size(), best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
int d = price[j] - price[i];
if (d > best && canPick(price, k, d)) best = d;
}
return best;
}
private:
bool canPick(vector<int>& price, int k, int d) {
int count = 1, last = price[0];
for (int i = 1; i < (int)price.size() && count < k; i++)
if (price[i] - last >= d) {
count++;
last = price[i];
}
return count >= k;
}
};function maximumTastiness(price, k) {
price.sort((a, b) => a - b);
const n = price.length;
let best = 0;
const canPick = (d) => {
let count = 1, last = price[0];
for (let i = 1; i < n && count < k; i++)
if (price[i] - last >= d) {
count++;
last = price[i];
}
return count >= k;
};
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) {
const d = price[j] - price[i];
if (d > best && canPick(d)) best = d;
}
return best;
}2Optimal (binary search on the answer)
O(n log n + n log M)Sorting costs n log n, and each of the log M binary-search steps (M = max - min) runs an O(n) greedy check.O(1)Only a few variables besides the in-place sort.Feasibility is monotonic in d: if you can pick k candies with all gaps at least d, you can also do it for any smaller gap. So binary search d over [0, max - min], using the same greedy scan to test each middle value. Taking the cheapest remaining candy that is far enough from the last one is always safe, because it leaves the most room for the rest.
- Sort price.
- lo = 0, hi = price[n-1] - price[0].
- While lo < hi: mid = lo + (hi - lo + 1) / 2.
- If the greedy scan picks at least k candies with gap mid, set lo = mid; otherwise hi = mid - 1.
- Return lo.
class Solution {
public int maximumTastiness(int[] price, int k) {
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, k, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private boolean canPick(int[] price, int k, int d) {
int count = 1, last = price[0];
for (int i = 1; i < price.length && count < k; i++)
if (price[i] - last >= d) {
count++;
last = price[i];
}
return count >= k;
}
}class Solution:
def maximumTastiness(self, price: List[int], k: int) -> int:
price.sort()
lo, hi = 0, price[-1] - price[0]
while lo < hi:
mid = lo + (hi - lo + 1) // 2
if self.canPick(price, k, mid):
lo = mid
else:
hi = mid - 1
return lo
def canPick(self, price: List[int], k: int, d: int) -> bool:
count, last = 1, price[0]
for i in range(1, len(price)):
if count >= k:
break
if price[i] - last >= d:
count += 1
last = price[i]
return count >= kclass Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
sort(price.begin(), price.end());
int lo = 0, hi = price.back() - price[0];
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
if (canPick(price, k, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
private:
bool canPick(vector<int>& price, int k, int d) {
int count = 1, last = price[0];
for (int i = 1; i < (int)price.size() && count < k; i++)
if (price[i] - last >= d) {
count++;
last = price[i];
}
return count >= k;
}
};function maximumTastiness(price, k) {
price.sort((a, b) => a - b);
const n = price.length;
const canPick = (d) => {
let count = 1, last = price[0];
for (let i = 1; i < n && count < k; i++)
if (price[i] - last >= d) {
count++;
last = price[i];
}
return count >= k;
};
let lo = 0, hi = price[n - 1] - price[0];
while (lo < hi) {
const mid = lo + Math.floor((hi - lo + 1) / 2);
if (canPick(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}Edge cases to test
k = 2: the answer is simply max - mink = price.length: every candy is taken, so the answer is the smallest gap between neighbours after sorting- Duplicate prices, which can force the answer down to 0
- Prices near 10^9, where differences must not overflow
Hints
Hint 1
Only the relative order of prices matters, so sort them first. The tastiness of a chosen set is then the smallest gap between consecutive chosen prices.
Hint 2
Turn the question around: for a fixed gap d, can you pick k candies whose consecutive gaps are all at least d? A greedy left-to-right pick answers that.
Hint 3
If gap d is achievable, every smaller gap is too. That monotonic yes/no answer is exactly what binary search on the answer needs.
FAQ
What is the best time complexity for Maximum Tastiness of Candy Basket?
Optimal (binary search on the answer) runs in O(n log n + n log M) time and O(1) extra space. Sorting costs n log n, and each of the log M binary-search steps (M = max - min) runs an O(n) greedy check.
Which pattern does Maximum Tastiness of Candy Basket use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Maximum Tastiness of Candy Basket?
Yes. Brute force (try every pairwise difference) takes O(n³) time and O(1) space. The best tastiness is always the difference of some pair of prices, so collect every pairwise difference and test each one as a candidate gap.
Which edge cases should I test for Maximum Tastiness of Candy Basket?
k = 2: the answer is simply max - min; k = price.length: every candy is taken, so the answer is the smallest gap between neighbours after sorting; Duplicate prices, which can force the answer down to 0; Prices near 10^9, where differences must not overflow.