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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Tastiness of Candy Basket

Number: 2600

Difficulty: Medium

Paid? No

Companies: Amazon, PhonePe

Problem Description

Given an array of positive integers representing candy prices and an integer k, select k distinct candies such that the tastiness of the candy basket, defined as the smallest absolute difference between the prices of any two chosen candies, is maximized. Return the maximum possible tastiness.

Key Insights

  • Sorting the array simplifies finding pairs with a desired minimum difference.
  • Use binary search on the answer (the possible minimum difference) to efficiently determine the maximum tastiness.
  • A greedy method can be used to check if a candidate tastiness is achievable by selecting candies that are at least the candidate difference apart.

Space and Time Complexity

Time Complexity: O(n log n + n log m) where n is the number of candies and m is the range of possible tastiness values.
Space Complexity: O(n) for sorting the array.

Solution

The solution begins by sorting the given prices array. The problem is then transformed into a decision problem where we seek to determine if k candies can be selected such that each adjacent chosen candy has a difference of at least mid, a candidate tastiness value. This check is done using a greedy algorithm that iterates over the sorted array and counts the number of candies selected given the difference constraint. Binary search is employed over the range of possible tastiness values starting from 0 to the maximum difference between the smallest and largest candy prices. The largest mid value for which the greedy test passes is the answer.

Code Solutions

# Python solution for Maximum Tastiness of Candy Basket

def maximumTastiness(price, k):
    # Sort the prices to allow greedy selection based on minimum differences
    price.sort()
    
    # Function to check if a tastiness of `min_diff` can be achieved using greedy selection
    def canAchieve(min_diff):
        count = 1  # Always pick the first candy
        last_price = price[0]
        # Iterate through the sorted prices
        for cur_price in price[1:]:
            # Select the current candy if the difference meets the min_diff requirement
            if cur_price - last_price >= min_diff:
                count += 1
                last_price = cur_price
                if count == k:
                    return True
        return False

    # Initialize binary search boundaries
    low, high = 0, price[-1] - price[0]
    best_tastiness = 0
    
    # Binary search to find the maximum minimum difference
    while low <= high:
        mid = (low + high) // 2
        # Check feasibility of achieving at least mid tastiness
        if canAchieve(mid):
            best_tastiness = mid
            low = mid + 1  # try for a greater tastiness
        else:
            high = mid - 1  # reduce the tastiness candidate
            
    return best_tastiness

# Example usage:
print(maximumTastiness([13,5,1,8,21,2], 3))  # Output: 8
← Back to All Questions