Scale Engineer

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 SearchSorting
Data structures
Array
Companies
eBayPhonePe

Prompt

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 <= 105
  • 1 <= price[i] <= 109

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.

// Note: This code is for demonstration and will be too slow for the problem constraints.class Solution {    int maxTastiness = 0;    int k;    int[] price;     public int maximumTastiness(int[] price, int k) {        this.k = k;        this.price = price;        // Using a list of prices for the current basket        findCombinations(0, new java.util.ArrayList<>());        return maxTastiness;    }     private void findCombinations(int start, java.util.List<Integer> currentBasketPrices) {        if (currentBasketPrices.size() == k) {            // A full basket is formed, calculate its tastiness            java.util.Collections.sort(currentBasketPrices);            int minDiff = Integer.MAX_VALUE;            for (int i = 0; i < currentBasketPrices.size() - 1; i++) {                minDiff = Math.min(minDiff, currentBasketPrices.get(i + 1) - currentBasketPrices.get(i));            }            maxTastiness = Math.max(maxTastiness, minDiff);            return;        }         // Explore further combinations        for (int i = start; i < price.length; i++) {            currentBasketPrices.add(price[i]);            findCombinations(i + 1, currentBasketPrices);            currentBasketPrices.remove(currentBasketPrices.size() - 1); // Backtrack        }    }}

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.

Solutions

public 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 ; } }

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 →

Next problem