2517. Maximum Tastiness of Candy Basket LeetCode Solution
In this guide, you will get 2517. Maximum Tastiness of Candy Basket LeetCode Solution with the best time and space complexity. The solution to Maximum Tastiness of Candy Basket problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Maximum Tastiness of Candy Basket
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.
Time Complexity: O(\texttt{sort} + n \cdot (\max(\texttt{price}) – \min(\texttt{price})))
Space Complexity: O(\texttt{sort} + 1)
2517. Maximum Tastiness of Candy Basket LeetCode Solution in C++
class Solution {
public:
int maximumTastiness(vector<int>& price, int k) {
ranges::sort(price);
int l = 0;
int r = ranges::max(price) - ranges::min(price) + 1;
while (l < r) {
const int m = (l + r) / 2;
if (numBaskets(price, m) < k)
r = m;
else
l = m + 1;
}
return l - 1;
}
private:
// Returns the number of baskets we can pick for m tastiness.
int numBaskets(const vector<int>& price, int m) {
int baskets = 0;
int prevPrice = -m;
for (const int p : price)
if (p >= prevPrice + m) {
prevPrice = p;
++baskets;
}
return baskets;
}
}; /* code provided by PROGIEZ */
2517. Maximum Tastiness of Candy Basket LeetCode Solution in Java
class Solution {
public int maximumTastiness(int[] price, int k) {
Arrays.sort(price);
int l = 0;
int r = Arrays.stream(price).max().getAsInt() - Arrays.stream(price).min().getAsInt() + 1;
while (l < r) {
final int m = (l + r) / 2;
if (numBaskets(price, m) >= k)
l = m + 1;
else
r = m;
}
return l - 1;
}
// Returns the number of baskets we can pick for m tastiness.
private int numBaskets(int[] price, int m) {
int baskets = 0;
int prevPrice = -m;
for (final int p : price)
if (p >= prevPrice + m) {
prevPrice = p;
++baskets;
}
return baskets;
}
} // code provided by PROGIEZ
2517. Maximum Tastiness of Candy Basket LeetCode Solution in Python
class Solution:
def maximumTastiness(self, price: list[int], k: int) -> int:
price.sort()
def numBaskets(m: int) -> int:
"""Returns the number of baskets we can pick for m tastiness."""
baskets = 0
prevPrice = -m
for p in price:
if p >= prevPrice + m:
prevPrice = p
baskets += 1
return baskets
l = bisect.bisect_left(range(max(price) - min(price) + 1), True,
key=lambda m: numBaskets(m) < k)
return l - 1 # code by PROGIEZ
