Maximum Tastiness of Candy Basket — Problem & Solution
Maximum Tastiness of Candy Basket solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Tastiness of Candy Basket is a medium coding problem on arrays, sorting and greedy, asked in Amazon, Google and PhonePe interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Greedy, Binary Search
- Asked at: Amazon, Google, PhonePe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A candy shop lists price[i] for candy i. A basket holds exactly k different candies (different indices; two candies may share a price).
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.
Example 1
Input: price = [13,5,1,8,21,2], k = 3
Output: 8
Explanation: Take the candies priced 13, 5 and 21: the closest pair is 13 and 5, eight apart.
Example 2
Input: price = [1,3,1], k = 2
Output: 2
Example 3
Input: price = [7,7,7,7], k = 2
Output: 0
Explanation: Every pair costs the same.
Constraints
2 <= k <= price.length <= 10^51 <= price[i] <= 10^9
Hints for Maximum Tastiness of Candy Basket
Hint 1
Sorting the prices loses nothing — tastiness only depends on the multiset of chosen prices.
Hint 2
Ask instead: can you pick
kcandies whose sorted neighbours are all at leastdapart? Largerdonly makes it harder.Hint 3
For a fixed
d, pick greedily from the cheapest candy, taking the next price that is at leastdabove the last pick; binary-search the largestdthat still yieldskpicks.
How to solve Maximum Tastiness of Candy Basket
Binary search on the answer d. Whether k candies can be spaced at least d apart is decided by a greedy sweep over the sorted prices, and that test is monotone in d.
Approach
- Sort
price. canSpace(d): take the first price, then walk right and take every price that is at leastdabove the last one taken; succeed if at leastkare taken.- Binary-search the largest
din[0, price[n-1] - price[0]]withcanSpace(d)true (using the upper middle so the loop advances). - Return that
d.
Why it works
For a fixed d, taking the smallest price first is never worse: any valid selection can swap its first pick for the global minimum and stay valid, and the same exchange argument applies to every subsequent pick (the earliest admissible price leaves the most room to the right). So the greedy count is the maximum number of candies spaced by d. If d works, every smaller d works, so the largest feasible d is a clean threshold.
Complexity
- Time —
O(n log n + n log R) with R the price range - Space —
O(n) for the sorted copy
Pitfalls
- Compare with
price[i] - last >= d; writinglast + dcan overflow 32-bit when both are near 10^9. - Duplicate prices are allowed, so the answer can be 0.
- Use
lo + (hi - lo + 1) / 2when the feasible branch setslo = mid.
Reference solution
Python
from typing import List
def maximumTastiness(price: List[int], k: int) -> int:
p = sorted(price)
def can_space(d):
taken, last = 1, p[0]
for x in p:
if x - last >= d:
taken += 1
last = x
if taken >= k:
return True
return taken >= k
lo, hi = 0, p[-1] - p[0]
while lo < hi:
mid = (lo + hi + 1) // 2
if can_space(mid):
lo = mid
else:
hi = mid - 1
return loJava
public static int maximumTastiness(int[] price, int k) {
int[] p = price.clone();
Arrays.sort(p);
int lo = 0, hi = p[p.length - 1] - p[0];
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
int taken = 1, last = p[0];
for (int i = 1; i < p.length && taken < k; i++) {
if (p[i] - last >= mid) { taken++; last = p[i]; }
}
if (taken >= k) lo = mid; else hi = mid - 1;
}
return lo;
}C++
int maximumTastiness(vector<int>& price, int k) {
vector<int> p(price);
sort(p.begin(), p.end());
int lo = 0, hi = p.back() - p[0];
while (lo < hi) {
int mid = lo + (hi - lo + 1) / 2;
int taken = 1, last = p[0];
for (int i = 1; i < (int)p.size() && taken < k; i++) {
if (p[i] - last >= mid) { taken++; last = p[i]; }
}
if (taken >= k) lo = mid; else hi = mid - 1;
}
return lo;
}JavaScript
var maximumTastiness = function(price, k) {
var p = price.slice().sort(function(a, b) { return a - b; });
var canSpace = function(d) {
var taken = 1, last = p[0];
for (var i = 1; i < p.length; i++) {
if (p[i] - last >= d) {
taken++;
last = p[i];
if (taken >= k) return true;
}
}
return taken >= k;
};
var lo = 0, hi = p[p.length - 1] - p[0];
while (lo < hi) {
var mid = lo + Math.floor((hi - lo + 1) / 2);
if (canSpace(mid)) lo = mid; else hi = mid - 1;
}
return lo;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms