Maximum Tastiness of Candy Basket - Solution & Explanation
Problem Statement
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] <= 109
Approach Overview
Problem 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 1: Approach 1: Sort and Binary Search
In this approach, we first sort the given price array. After sorting, we perform a binary search on the possible values of the maximum tastiness. For each candidate tastiness value, we check if it's feasible to select k candies such that the minimum absolute difference between the selected prices is at least the candidate value by using a greedy approach. We incrementally count distinct candies such that the difference condition is maintained.
This C solution uses a combination of sorting and binary search. After sorting the prices array, we perform a binary search on the possible range of the maximum tastiness. The function is_feasible checks if it's possible to choose k distinct candies with a given minimum difference. The main function computes the highest possible tastiness value.
Complexity
Time Complexity: O(n log n) due to sorting and binary searching over n elements.
Space Complexity: O(1) for the in-place modification.
Approach 2: Approach 2: Sliding Window Technique
This approach uses a sliding window technique to find the maximum tastiness for the basket of candies. After sorting the array, the idea is to maintain a window of size k and find the minimum difference of prices within this window. Expand the window by increasing the left and right pointers maintaining a difference constraint. It leverages the sorted nature to prioritize the minimum differences.
In this version, we sort the prices array and utilize a sliding window approach to consider segments of size k. For each segment, we calculate the minimum difference and update the maximum tastiness found.
Complexity
Time Complexity: O(n log n + nk) due to sorting and going through windows.
Space Complexity: O(1).
Approach 3: Default Approach
Try this approach in the editor →Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Binary Search | Time Complexity: |
| Approach 2: Sliding Window Technique | Time Complexity: |
| Default Approach | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Maximum Tastiness of Candy Basket | 2517 LeetCode | Binary Search | Leetcode Weekly Contest 325 • CodeWithSunny • 5,319 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Maximum Tastiness of Candy Basket easy or hard?
Maximum Tastiness of Candy Basket Python/Java solution
How to solve Maximum Tastiness of Candy Basket in O(n)?
What is the best approach for Maximum Tastiness of Candy Basket?
Is Maximum Tastiness of Candy Basket asked at Google/Amazon/Meta?
What data structure is used in Maximum Tastiness of Candy Basket?
What is the time complexity of Maximum Tastiness of Candy Basket?
Ready to solve this problem?
Practice Maximum Tastiness of Candy Basket with our built-in code editor and test cases.
Practice on FleetCode