You are given an array of positive integers price where price[i] denotes the price of the ith candy and a positive integer k.
The store sells baskets of k distinct candies. The tastiness of a candy basket is the smallest absolute difference of the prices of any two candies in the basket.
Return the maximum tastiness of a candy basket.
Example 1:
Input: price = [13,5,1,8,21,2], k = 3 Output: 8 Explanation: Choose the candies with the prices [13,5,21]. The tastiness of the candy basket is: min(|13 - 5|, |13 - 21|, |5 - 21|) = min(8, 8, 16) = 8. It can be proven that 8 is the maximum tastiness that can be achieved.
Example 2:
Input: price = [1,3,1], k = 2 Output: 2 Explanation: Choose the candies with the prices [1,3]. The tastiness of the candy basket is: min(|1 - 3|) = min(2) = 2. It can be proven that 2 is the maximum tastiness that can be achieved.
Example 3:
Input: price = [7,7,7,7], k = 2 Output: 0 Explanation: Choosing any two distinct candies from the candies we have will result in a tastiness of 0.
Constraints:
2 <= k <= price.length <= 1051 <= price[i] <= 109The key idea in #2517 Maximum Tastiness of Candy Basket is to maximize the minimum difference ("tastiness") between the prices of candies selected for a basket of size k. A common strategy is to first sort the array of candy prices so that differences can be evaluated easily.
After sorting, apply binary search on the answer. Instead of directly picking candies, guess a minimum tastiness value and check if it is possible to select k candies such that the difference between consecutive chosen prices is at least that value. This feasibility check can be implemented using a greedy scan that always picks the next candy meeting the required gap.
If selecting k candies is possible, increase the search range to try a larger tastiness; otherwise decrease it. This approach efficiently narrows down the optimal answer. Sorting dominates preprocessing, while each binary search step performs a linear check. The method is efficient and widely used in problems involving maximizing minimum distances.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Binary Search with Greedy Check | O(n log n + n log R) | O(1) |
CodeWithSunny
Use these hints if you're stuck. Try solving on your own first.
The answer is binary searchable.
For some x, we can use a greedy strategy to check if it is possible to pick k distinct candies with tastiness being at least x.
Sort prices and iterate from left to right. For some price[i] check if the price difference between the last taken candy and price[i] is at least x. If so, add the candy i to the basket.
So, a candy basket with tastiness x can be achieved if the basket size is bigger than or equal to k.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Binary search is used because the problem asks to maximize the minimum difference between selected values. The feasibility of a given difference is monotonic, meaning if a certain tastiness is possible, smaller values will also work.
Yes, this type of problem is common in coding interviews because it combines binary search on the answer with greedy validation. Variants of maximizing minimum distance frequently appear in interviews at top tech companies.
The optimal approach uses sorting combined with binary search on the minimum tastiness value. After sorting the candy prices, we binary search the answer and use a greedy check to verify whether k candies can be chosen with at least that difference.
The solution mainly relies on arrays and sorting. After sorting the array, a simple greedy traversal is used to check feasibility, so no advanced data structures are required.