Watch 10 video solutions for Maximum Tastiness of Candy Basket, a medium level problem involving Array, Binary Search, Greedy. This walkthrough by CodeWithSunny has 5,103 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 109Problem Overview: You receive an array price where each value represents the price of a candy. You must choose k candies so the minimum absolute difference between any two selected prices is as large as possible. The goal is to maximize this minimum difference, often called the basket's tastiness.
Approach 1: Sort and Binary Search (O(n log n + n log M) time, O(1) space)
Start by sorting the array so price differences become predictable. The key insight: instead of directly choosing candies, search for the largest minimum difference that can still place k candies. Use binary search over the answer range [0, max(price)-min(price)]. For a candidate difference d, greedily place candies from left to right—always pick the next price whose difference from the last chosen candy is at least d. If you can place k candies, the difference is feasible. Increase the search range; otherwise decrease it. Sorting costs O(n log n), each feasibility check costs O(n), giving O(n log M) binary search iterations where M is the price range. This approach combines sorting, binary search, and a greedy placement strategy.
Approach 2: Sliding Window Technique (O(n^2) worst-case time, O(1) space)
After sorting the prices, use a two-pointer or sliding window idea to explore candidate groups. Fix a starting candy and expand the window while greedily selecting the next candy that keeps the gap as large as possible. Track the smallest pairwise difference within the chosen candies and update the best answer. This avoids binary search but may re-scan large parts of the array for different starting points, leading to quadratic behavior in the worst case. The approach still relies on sorted order and greedy selection, but without the monotonic property exploited by binary search.
Recommended for interviews: The sort + binary search approach is what interviewers expect. It shows you recognize a classic "binary search on answer" pattern and can combine it with a greedy feasibility check. Mentioning a simpler exploratory method first shows understanding, but implementing the binary search solution demonstrates stronger algorithmic skill and awareness of optimal complexity.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort + Binary Search with Greedy Check | O(n log n + n log M) | O(1) | Best general solution; large inputs where maximizing minimum distance is required |
| Sliding Window Exploration | O(n^2) worst case | O(1) | Conceptual approach for small arrays or when exploring greedy selections without binary search |