We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Tastiness of Candy Basket

Difficulty: Medium

Problem Description

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.

Key Insights

  • The goal is to maximize the minimum absolute difference between any two candy prices in a selected basket of k candies.
  • Sorting the array of prices helps in efficiently determining the absolute differences between selected candies.
  • A binary search can be utilized to find the maximum possible value of tastiness by checking the feasibility of selecting k candies with a given minimum difference.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the prices and binary searching through potential tastiness values. Space Complexity: O(1) - no additional space is used that scales with input size.

Solution

To solve this problem, we can follow these steps:

  1. Sort the price array.
  2. Use binary search to find the maximum tastiness. The search space for tastiness will be between 0 and the difference between the maximum and minimum prices in the sorted array.
  3. For each midpoint in the binary search, check if it is possible to select k candies such that the minimum difference between any two selected candies is at least that midpoint value. This is done by iterating through the sorted prices and counting how many candies can be selected based on the current minimum difference.
  4. Adjust the binary search bounds based on whether the selection was successful or not.

Code Solutions

def maxTastiness(price, k):
    price.sort()
    
    def canSelectCandies(min_diff):
        count = 1
        last_selected = price[0]
        
        for i in range(1, len(price)):
            if price[i] - last_selected >= min_diff:
                count += 1
                last_selected = price[i]
                if count == k:
                    return True
        return False

    left, right = 0, price[-1] - price[0]
    while left < right:
        mid = (left + right + 1) // 2
        if canSelectCandies(mid):
            left = mid
        else:
            right = mid - 1
    
    return left
← Back to All Questions