LeetCode 2517 - Maximum Tastiness of Candy Basket
The problem gives us an array price where each element represents the price of a candy. We must choose exactly k distinct candies and maximize the basket's "tastiness".
Difficulty: 🟡 Medium
Topics: Array, Binary Search, Greedy, Sorting
Solution
LeetCode 2517 - Maximum Tastiness of Candy Basket
Problem Understanding
The problem gives us an array price where each element represents the price of a candy. We must choose exactly k distinct candies and maximize the basket's "tastiness".
The tastiness of a basket is defined as the minimum absolute difference between the prices of any two candies inside that basket.
In other words, if we select k candy prices, we examine every pair of chosen candies and compute their absolute price differences. The smallest of those differences becomes the tastiness of the basket. Our goal is to make this minimum difference as large as possible.
For example, if we choose candies with prices [5, 13, 21], the pairwise differences are:
|13 - 5| = 8|21 - 13| = 8|21 - 5| = 16
The smallest difference is 8, so the basket tastiness is 8.
The constraints are very important:
price.lengthcan be as large as10^5- Each price can be as large as
10^9
These limits immediately rule out exponential or quadratic subset generation approaches. Any solution that tries all possible combinations of candies will be far too slow.
The problem guarantees:
- We always have at least two candies
kis always valid- Prices are positive integers
- Candies themselves are distinct items, even if some prices are equal
Several edge cases are important:
- Multiple candies may have identical prices
- The maximum answer can be
0 kmay equalprice.length- The optimal basket may not involve the smallest or largest values
- Large input sizes require an efficient algorithm
The key challenge is finding the largest possible minimum difference efficiently.
Approaches
Brute Force Approach
The most direct solution is to generate every possible subset of size k. For each subset, we compute the minimum pairwise absolute difference and keep track of the maximum value across all subsets.
This works because it explicitly checks every valid basket and therefore cannot miss the optimal answer.
However, the number of subsets is enormous. The number of ways to choose k elements from n candies is:
$$\binom{n}{k}$$
This becomes computationally impossible when n reaches 10^5.
Additionally, each subset requires pairwise comparisons, which adds even more cost.
Therefore, brute force is completely infeasible for the given constraints.
Optimal Approach
The important observation is that the problem asks us to maximize a minimum value. Problems with this structure often suggest binary search on the answer.
Suppose we guess a candidate tastiness value d.
The question becomes:
"Can we choose at least k candies such that every chosen pair differs by at least d?"
This feasibility check is much easier.
After sorting the prices, we can greedily pick candies:
- Always take the smallest available candy first
- Then keep selecting the next candy whose price differs from the previously chosen candy by at least
d
If we can select at least k candies this way, then d is feasible.
This works because sorting transforms the problem into checking gaps between consecutive selected elements. A greedy strategy becomes optimal in sorted order.
Since feasibility changes monotonically:
- If distance
dis possible, then every smaller distance is also possible - If distance
dis impossible, then every larger distance is impossible
This monotonic property allows binary search over the answer space.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | Exponential | O(k) | Tries all subsets of size k |
| Optimal | O(n log n + n log M) | O(1) extra, excluding sort | Binary search on answer with greedy feasibility check |
Here, M is the range of prices, approximately 10^9.
Algorithm Walkthrough
- Sort the
pricearray.
Sorting is essential because it allows us to reason about differences in order. Once sorted, if consecutive selected candies satisfy the minimum distance requirement, then all other pairwise distances will also satisfy it. 2. Define the binary search range.
The smallest possible tastiness is 0.
The largest possible tastiness is:
max(price) - min(price)
because no pairwise difference can exceed the full range of values. 3. Perform binary search on the answer.
For each candidate minimum difference mid, determine whether it is possible to build a basket of size k.
4. Implement the feasibility check greedily.
Start by selecting the first candy in sorted order.
Then iterate through the array:
-
If the current candy differs from the last selected candy by at least
mid, select it. -
Continue until either:
-
kcandies are selected, or -
the array ends
- Update the binary search bounds.
- If
midis feasible, try larger values because we want to maximize tastiness. - Otherwise, try smaller values.
- Return the largest feasible value found.
Why it works
The correctness depends on two properties.
First, the feasibility function is monotonic. If we can select k candies with minimum distance d, then we can also do so for any smaller distance.
Second, the greedy selection strategy is optimal after sorting. Choosing the earliest valid candy always leaves maximum room for future selections. If the greedy method cannot build a valid basket, then no other selection strategy can.
Together, these properties guarantee that binary search finds the maximum feasible tastiness.
Python Solution
from typing import List
class Solution:
def maximumTastiness(self, price: List[int], k: int) -> int:
price.sort()
def can_form_basket(min_diff: int) -> bool:
count = 1
last_selected = price[0]
for current_price in price[1:]:
if current_price - last_selected >= min_diff:
count += 1
last_selected = current_price
if count >= k:
return True
return False
left = 0
right = price[-1] - price[0]
answer = 0
while left <= right:
mid = (left + right) // 2
if can_form_basket(mid):
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
The implementation begins by sorting the array. This transforms the problem into one where differences between consecutive selected candies are sufficient to verify the minimum distance condition.
The helper function can_form_basket checks whether a candidate minimum difference is feasible. It greedily selects candies while maintaining at least min_diff separation between consecutive chosen candies.
The variable count tracks how many candies have been selected so far. The variable last_selected stores the most recently chosen candy price.
The binary search explores the answer space between 0 and the maximum possible difference. Whenever a candidate value is feasible, we store it as the current best answer and search for a larger value.
Eventually, binary search converges to the maximum feasible tastiness.
Go Solution
package main
import (
"sort"
)
func maximumTastiness(price []int, k int) int {
sort.Ints(price)
canFormBasket := func(minDiff int) bool {
count := 1
lastSelected := price[0]
for i := 1; i < len(price); i++ {
if price[i]-lastSelected >= minDiff {
count++
lastSelected = price[i]
if count >= k {
return true
}
}
}
return false
}
left := 0
right := price[len(price)-1] - price[0]
answer := 0
for left <= right {
mid := left + (right-left)/2
if canFormBasket(mid) {
answer = mid
left = mid + 1
} else {
right = mid - 1
}
}
return answer
}
The Go implementation closely mirrors the Python version.
Go uses sort.Ints to sort the slice in place. The feasibility check is implemented as an anonymous function assigned to canFormBasket.
The binary search midpoint calculation uses:
mid := left + (right-left)/2
This form avoids integer overflow, although overflow is not a practical concern for the current constraints.
Slices in Go behave similarly to dynamic arrays, so no special handling is needed for empty input because the constraints guarantee at least two elements.
Worked Examples
Example 1
Input:
price = [13,5,1,8,21,2]
k = 3
Step 1: Sort the array
[1, 2, 5, 8, 13, 21]
Step 2: Binary search
Initial range:
left = 0
right = 21 - 1 = 20
| mid | Feasible? | Selected Candies | Result |
|---|---|---|---|
| 10 | No | 1, 13 | Only 2 candies |
| 4 | Yes | 1, 5, 13 | 3 candies formed |
| 7 | Yes | 1, 8, 21 | 3 candies formed |
| 8 | Yes | 1, 13, 21 | 3 candies formed |
| 9 | No | 1, 13 | Only 2 candies |
Final answer:
8
Example 2
Input:
price = [1,3,1]
k = 2
Step 1: Sort
[1, 1, 3]
Step 2: Binary search
| mid | Feasible? | Selected Candies |
|---|---|---|
| 1 | Yes | 1, 3 |
| 2 | Yes | 1, 3 |
| 3 | No | Only 1 candy |
Final answer:
2
Example 3
Input:
price = [7,7,7,7]
k = 2
Step 1: Sort
[7,7,7,7]
Maximum possible difference:
7 - 7 = 0
Binary search immediately concludes:
answer = 0
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n + n log M) | Sorting plus binary search with linear feasibility checks |
| Space | O(1) extra | Only a few variables are used beyond sorting |
The sorting step costs O(n log n).
The binary search performs O(log M) iterations, where M is the difference between the maximum and minimum prices.
Each feasibility check scans the array once, costing O(n).
Therefore, the total complexity becomes:
$$O(n \log n + n \log M)$$
Since log M is at most about 31 for 10^9, the solution easily handles the constraints.
Test Cases
from typing import List
class Solution:
def maximumTastiness(self, price: List[int], k: int) -> int:
price.sort()
def can_form_basket(min_diff: int) -> bool:
count = 1
last_selected = price[0]
for current_price in price[1:]:
if current_price - last_selected >= min_diff:
count += 1
last_selected = current_price
if count >= k:
return True
return False
left = 0
right = price[-1] - price[0]
answer = 0
while left <= right:
mid = (left + right) // 2
if can_form_basket(mid):
answer = mid
left = mid + 1
else:
right = mid - 1
return answer
solution = Solution()
assert solution.maximumTastiness([13,5,1,8,21,2], 3) == 8 # Provided example
assert solution.maximumTastiness([1,3,1], 2) == 2 # Duplicate values
assert solution.maximumTastiness([7,7,7,7], 2) == 0 # All equal prices
assert solution.maximumTastiness([1,2], 2) == 1 # Smallest valid input
assert solution.maximumTastiness([1,1000000000], 2) == 999999999 # Large range
assert solution.maximumTastiness([1,2,3,4,5], 5) == 1 # Must take all candies
assert solution.maximumTastiness([1,2,4,8,16], 3) == 7 # Nontrivial optimal selection
assert solution.maximumTastiness([5,5,5,10], 2) == 5 # Repeated values with one larger
assert solution.maximumTastiness([1,6,11,16,21], 3) == 10 # Evenly spaced values
assert solution.maximumTastiness([1,2,2,2,10], 3) == 1 # Duplicates force small gap
Test Summary
| Test | Why |
|---|---|
[13,5,1,8,21,2], k=3 |
Validates the main example |
[1,3,1], k=2 |
Tests duplicate prices |
[7,7,7,7], k=2 |
Ensures answer can be zero |
[1,2], k=2 |
Smallest allowed input |
[1,1000000000], k=2 |
Tests very large values |
[1,2,3,4,5], k=5 |
Must select every candy |
[1,2,4,8,16], k=3 |
Tests non-obvious optimal selection |
[5,5,5,10], k=2 |
Duplicate-heavy array |
[1,6,11,16,21], k=3 |
Uniform spacing case |
[1,2,2,2,10], k=3 |
Duplicates constrain minimum difference |
Edge Cases
One important edge case occurs when all candy prices are identical. In this situation, every pairwise difference is zero, so the maximum tastiness must also be zero. A buggy implementation might incorrectly assume positive spacing always exists. The binary search correctly handles this because the search range becomes [0, 0].
Another important case is when k equals the length of the array. In this situation, every candy must be selected. The answer is therefore determined by the smallest adjacent difference after sorting. The greedy feasibility check naturally handles this because it attempts to include as many candies as possible while respecting the minimum distance.
Large price values are also important. Since prices may be as large as 10^9, arithmetic overflow could become an issue in some languages. The Go implementation avoids midpoint overflow by using:
mid := left + (right-left)/2
Finally, arrays with many duplicate values can be tricky. For example, [1,2,2,2,10] with k=3 forces the algorithm to include at least two very close values. A naive greedy strategy that ignores duplicates could incorrectly overestimate the answer. The sorted greedy feasibility check correctly rejects impossible minimum distances.