Maximum Tastiness of Candy Basket

Med

#2297Time: O(C(N, k) * k log k) Where `N` is the length of the `price` array and `C(N, k)` is the number of combinations (`N! / (k! * (N-k)!)`). Generating all combinations is exponential. For each combination, we sort it in `O(k log k)` time. This complexity is far too high for the given constraints.Space: O(k) This space is used to store the current combination being built and for the recursion stack. The depth of the recursion is at most `k`.2 companies

Patterns

Greedy

Algorithms

Binary Search Sorting

Data structures

Array

Companies

eBay PhonePe

Prompt

You are given an array of positive integers price where price[i] denotes the price of the i^th 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 <= 10⁵
1 <= price[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the problem statement into a search algorithm. It involves systematically generating every possible basket of k candies, calculating the tastiness for each one, and keeping track of the highest tastiness found. While straightforward, its computational cost is prohibitive.

Algorithm

Initialize max_tastiness to 0.
Generate all unique combinations of k candies from the price array. A recursive backtracking approach is suitable for this.
For each combination (a basket of k candies):
1. Sort the prices within the current basket.
2. Calculate the tastiness by finding the minimum difference between any two adjacent prices in the sorted basket.
3. Update max_tastiness = max(max_tastiness, current_tastiness).
After iterating through all possible combinations, return max_tastiness.

Walkthrough

The core idea is to perform an exhaustive search over all possible subsets of size k from the price array. We can implement this using a recursive function that builds a combination step by step.

For every complete combination of k candies, we determine its tastiness. The tastiness is defined as the smallest absolute difference between the prices of any two candies in the basket. An easy way to compute this is to first sort the k prices in the basket and then iterate through the sorted prices to find the minimum difference between adjacent elements. This minimum difference is the tastiness for that specific basket.

We maintain a global variable, max_tastiness, which is updated whenever we find a basket with a tastiness greater than the current maximum. After exploring all C(N, k) combinations, this variable will hold the final answer.

1// Note: This code is for demonstration and will be too slow for the problem constraints.2class Solution {3    int maxTastiness = 0;4    int k;5    int[] price;6 7    public int maximumTastiness(int[] price, int k) {8        this.k = k;9        this.price = price;10        // Using a list of prices for the current basket11        findCombinations(0, new java.util.ArrayList<>());12        return maxTastiness;13    }14 15    private void findCombinations(int start, java.util.List<Integer> currentBasketPrices) {16        if (currentBasketPrices.size() == k) {17            // A full basket is formed, calculate its tastiness18            java.util.Collections.sort(currentBasketPrices);19            int minDiff = Integer.MAX_VALUE;20            for (int i = 0; i < currentBasketPrices.size() - 1; i++) {21                minDiff = Math.min(minDiff, currentBasketPrices.get(i + 1) - currentBasketPrices.get(i));22            }23            maxTastiness = Math.max(maxTastiness, minDiff);24            return;25        }26 27        // Explore further combinations28        for (int i = start; i < price.length; i++) {29            currentBasketPrices.add(price[i]);30            findCombinations(i + 1, currentBasketPrices);31            currentBasketPrices.remove(currentBasketPrices.size() - 1); // Backtrack32        }33    }34}

Complexity

Time

O(C(N, k) * k log k) Where `N` is the length of the `price` array and `C(N, k)` is the number of combinations (`N! / (k! * (N-k)!)`). Generating all combinations is exponential. For each combination, we sort it in `O(k log k)` time. This complexity is far too high for the given constraints.

Space

O(k) This space is used to store the current combination being built and for the recursion stack. The depth of the recursion is at most `k`.

Trade-offs

Pros

Simple to conceptualize and follows the problem definition directly.

Cons

Extremely slow and inefficient.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints due to the exponential number of combinations.

A much more efficient approach leverages binary search on the answer. The problem asks to maximize a minimum value (the tastiness). This structure suggests that if we can achieve a tastiness of t, we can also achieve any tastiness less than t. This monotonic property allows us to binary search for the optimal tastiness value.

The core of this approach is a helper function that can efficiently determine if it's possible to form a basket with a given minimum tastiness. By combining this check with binary search, we can quickly narrow down the search space and find the maximum possible tastiness.

Algorithm

First, sort the price array in non-decreasing order. This is crucial for the greedy checking strategy.
Define a search space for the answer (the tastiness). The minimum possible tastiness is 0, and the maximum is price[n-1] - price[0].
Perform a binary search on this range [low, high].
For each mid value (a potential tastiness) in the binary search:
- Check if it's possible to select k candies with at least a mid price difference. This is done with a greedy helper function, canAchieve(tastiness).
- The canAchieve function works by iterating through the sorted price array. It greedily picks candies, always choosing the next candy that is at least tastiness away from the previously picked one.
- If canAchieve(mid) returns true, it means a tastiness of mid is possible. We store mid as a potential answer and try for an even higher tastiness by setting low = mid + 1.
- If canAchieve(mid) returns false, the tastiness mid is too high. We must search for a smaller one by setting high = mid - 1.
The last successfully validated mid value is the maximum possible tastiness.

Walkthrough

The key insight is to reframe the problem from "find the maximum tastiness" to "is it possible to achieve a tastiness of x?". If we can answer this decision problem efficiently, we can use binary search to find the maximum x for which the answer is yes.

1. Sorting: First, we sort the price array. This allows us to check for differences greedily and efficiently. Let the sorted array be p'. The tastiness of any basket of k candies {c_1, c_2, ..., c_k} with c_1 < c_2 < ... < c_k is determined by the minimum of c_{i+1} - c_i.

2. The canAchieve(tastiness) check: To check if a given tastiness is achievable, we use a greedy strategy on the sorted price array:

Pick the first candy (price[0]).
Iterate through the rest of the array. To maintain the minimum difference, the next candy we pick must have a price of at least (price of last picked candy) + tastiness.
We greedily select the very next candy that satisfies this condition.
We count how many candies we can pick this way. If the count is at least k, then the given tastiness is achievable.

3. Binary Search: We binary search over the possible range of answers. The lowest possible tastiness is 0, and the highest is the difference between the maximum and minimum prices in the array.

We repeatedly take the middle value mid of our current search range and use canAchieve(mid) to test it.
If it's achievable, we know mid is a potential answer, and we try for a better (larger) one by searching in the upper half: low = mid + 1.
If it's not achievable, mid is too high, so we must search in the lower half: high = mid - 1.

This process efficiently converges to the maximum possible tastiness.

1import java.util.Arrays;2 3class Solution {4    public int maximumTastiness(int[] price, int k) {5        Arrays.sort(price);6        int n = price.length;7        int low = 0;8        int high = price[n - 1] - price[0];9        int ans = 0;10 11        while (low <= high) {12            int mid = low + (high - low) / 2;13            if (canAchieve(mid, price, k)) {14                // This tastiness is achievable, so it's a potential answer.15                // We try for an even larger tastiness.16                ans = mid;17                low = mid + 1;18            } else {19                // This tastiness is too high, we need to try a smaller one.20                high = mid - 1;21            }22        }23        return ans;24    }25 26    // Helper function to check if we can pick k candies with at least `tastiness` difference.27    private boolean canAchieve(int tastiness, int[] price, int k) {28        int count = 1; // We always pick the first candy29        int lastPrice = price[0];30        for (int i = 1; i < price.length; i++) {31            if (price[i] >= lastPrice + tastiness) {32                count++;33                lastPrice = price[i];34            }35        }36        return count >= k;37    }38}

Complexity

Time

O(N log N + N log R) Where `N` is `price.length` and `R` is the range of prices (`max_price - min_price`). Sorting takes `O(N log N)`. The binary search performs `O(log R)` iterations, and each iteration involves a call to `canAchieve`, which takes `O(N)` time. The total time is therefore `O(N log N + N log R)`.

Space

O(log N) or O(N) The space complexity is dominated by the sorting algorithm. In-place quicksort uses `O(log N)` space for its recursion stack, while merge sort would use `O(N)`. The binary search itself uses `O(1)` extra space.

Trade-offs

Pros

Highly efficient and optimal.
Scales well for large inputs, easily passing the given constraints.

Cons

The logic is less direct than brute force and requires understanding the concept of binary searching on an answer space.

Solutions

Solution

1public class Solution { public int MaximumTastiness ( int [] price , int k ) { Array . Sort ( price ); int l = 0 , r = price [ price . Length - 1 ] - price [ 0 ]; while ( l < r ) { int mid = ( l + r + 1 ) >> 1 ; if ( check ( price , mid , k )) { l = mid ; } else { r = mid - 1 ; } } return l ; } private bool check ( int [] price , int x , int k ) { int cnt = 0 , pre = - x ; foreach ( int cur in price ) { if ( cur - pre >= x ) { ++ cnt ; pre = cur ; } } return cnt >= k ; } }

1class Solution {2public3  int maximumTastiness(int[] price, int k) {4    Arrays.sort(price);5    int l = 0, r = price[price.length - 1] - price[0];6    while (l < r) {7      int mid = (l + r + 1) >> 1;8      if (check(price, k, mid)) {9        l = mid;10      } else {11        r = mid - 1;12      }13    }14    return l;15  }16private17  boolean check(int[] price, int k, int x) {18    int cnt = 0, pre = -x;19    for (int cur : price) {20      if (cur - pre >= x) {21        pre = cur;22        ++cnt;23      }24    }25    return cnt >= k;26  }27}

1class Solution {2public:3  int maximumTastiness(vector<int> &price, int k) {4    sort(price.begin(), price.end());5    int l = 0, r = price.back() - price[0];6    auto check = [&](int x) -> bool {7      int cnt = 0, pre = -x;8      for (int &cur : price) {9        if (cur - pre >= x) {10          pre = cur;11          ++cnt;12        }13      }14      return cnt >= k;15    };16    while (l < r) {17      int mid = (l + r + 1) >> 1;18      if (check(mid)) {19        l = mid;20      } else {21        r = mid - 1;22      }23    }24    return l;25  }26};

1class Solution:2    def maximumTastiness(self, price: List[int], k: int) -> int: def check(x: int) -> bool: cnt, pre = 0, - x for cur in price: if cur - pre >= x: pre = cur cnt += 1 return cnt >= k price . sort() l, r = 0, price[- 1] - price[0] while l < r: mid = (l + r + 1) >> 1 if check(mid): l = mid else: r = mid - 1 return l

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem