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

Number of Unique Flavors After Sharing K Candies

Number: 2247

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given an array of candies (each represented by its flavor as an integer), you must share k consecutive candies with your sister and keep the rest. Your goal is to maximize the number of unique candy flavors you keep. In other words, choose a contiguous block of k candies to remove so that the remaining candies preserve as many distinct flavors as possible.

Key Insights

  • Pre-calculate the total frequency of each flavor in the entire array.
  • The overall count of unique flavors is fixed.
  • For any contiguous block (window) of k candies, determine the number of flavors that are completely removed from the remaining candy collection (i.e., flavors for which the window count equals the total count).
  • Slide the window over the array to find the block that minimizes the removal (loss) of unique flavors.
  • The maximum unique flavors you can eat equals total unique flavors minus the minimal number of flavors lost by sharing.

Space and Time Complexity

Time Complexity: O(n), where n is the number of candies, because we pre-calculate frequencies and then slide a window across the array. Space Complexity: O(n) in the worst case due to storing frequency counts in hash maps/dictionaries.

Solution

We first compute a frequency dictionary (totalCounts) for all candies to know how many times each flavor appears. The total number of unique flavors is the count of keys in this dictionary.

Next, we use a sliding window of size k to simulate sharing k consecutive candies. For each window, we keep another frequency dictionary (windowCounts) that tracks the flavors in that window. For a given window, if for a flavor the count in windowCounts equals the count in totalCounts, it means that flavor is completely removed from the remaining candies. We want to choose the window with the least number of such completely removed flavors.

We update the window frequency counts as we slide the window and keep track of the loss (i.e. the number of flavors that are completely removed). Finally, the maximum unique flavors you can keep is calculated as: unique kept = total unique flavors - minimal loss

Key data structures and techniques:

  • Two hash maps/dictionaries to store total and window frequencies.
  • A sliding window to efficiently update the window frequency counts rather than recalculating from scratch.

Code Solutions

# Python solution
def maxUniqueFlavors(candies, k):
    # Calculate overall frequency of each flavor in candies
    total_counts = {}
    for flavor in candies:
        total_counts[flavor] = total_counts.get(flavor, 0) + 1
    total_unique = len(total_counts)
    
    # If no candies are shared, all unique flavors are kept.
    if k == 0:
        return total_unique
    # If k equals length, all candies are given away.
    if k >= len(candies):
        return 0
    
    # Initialize the sliding window and count loss (fully removed flavors)
    window_counts = {}
    loss = 0  # number of flavors completely removed from remainder
    # Build initial window for first k candies
    for i in range(k):
        flavor = candies[i]
        window_counts[flavor] = window_counts.get(flavor, 0) + 1
    # Calculate loss for the initial window
    for flavor, count in window_counts.items():
        if count == total_counts[flavor]:
            loss += 1
    
    # Set minimal loss as loss from initial window.
    min_loss = loss
    
    # Slide the window over remaining candies
    for i in range(k, len(candies)):
        # outgoing candy from the left
        outgoing = candies[i - k]
        # incoming candy from the right
        incoming = candies[i]
        
        # Process outgoing flavor: decrease its count in the window
        # If it was completely removed (fully removed in previous state),
        # update loss accordingly.
        if window_counts[outgoing] == total_counts[outgoing]:
            loss -= 1
        window_counts[outgoing] -= 1
        
        # Process incoming flavor: add to window counts
        window_counts[incoming] = window_counts.get(incoming, 0) + 1
        # Check if this addition causes the flavor to be fully removed 
        # from what you get to keep.
        if window_counts[incoming] == total_counts[incoming]:
            loss += 1
        
        # Update minimal loss seen so far.
        min_loss = min(min_loss, loss)
    
    # Maximum unique flavors kept
    return total_unique - min_loss

# Example usage:
candies1 = [1,2,2,3,4,3]
k1 = 3
print(maxUniqueFlavors(candies1, k1))  # Expected output: 3
← Back to All Questions