Problem Description

You have a 0-indexed array candies where candies[i] represents the flavor of the i-th candy. You need to share some candies with your little sister by giving her exactly k consecutive candies from the array. After giving away these k consecutive candies, you want to keep as many unique flavors as possible for yourself.

The task is to find the maximum number of unique candy flavors you can keep after sharing k consecutive candies with your sister.

For example, if you have candies [1, 2, 2, 3, 4, 3] and k = 3, you could give away:

• Candies at indices 0-2 (flavors [1, 2, 2]), keeping [3, 4, 3] which has 2 unique flavors
• Candies at indices 1-3 (flavors [2, 2, 3]), keeping [1, 4, 3] which has 3 unique flavors
• Candies at indices 2-4 (flavors [2, 3, 4]), keeping [1, 2, 3] which has 3 unique flavors
• Candies at indices 3-5 (flavors [3, 4, 3]), keeping [1, 2, 2] which has 2 unique flavors

The maximum unique flavors you can keep is 3.

The goal is to determine which k consecutive candies to give away so that the remaining candies have the maximum number of unique flavors.

Intuition

The key insight is that we want to give away k consecutive candies that minimize the impact on the variety of flavors we keep. This means we should think about what candies we're keeping rather than what we're giving away.

If we give away candies from position i to i+k-1, then we keep all candies before position i and all candies after position i+k-1. The unique flavors we retain depend on the candies outside this window of size k.

This naturally leads to a sliding window approach. We can imagine a window of size k sliding across the array - the candies inside the window are given to our sister, while the candies outside are what we keep. For each possible position of this window, we count how many unique flavors exist outside of it.

To efficiently track the unique flavors outside the window, we can use a hash table (Counter) that maintains the frequency of each flavor. As the window slides:

1. When the window moves right by one position, a candy that was previously inside the window (at the left edge) now becomes ours - we add it to our counter
2. A candy that was previously ours (at the right edge of the window) now goes inside the window - we remove it from our counter

The number of unique flavors we have at any point is simply the number of distinct keys in our counter (flavors with non-zero count). By tracking this for all possible window positions, we can find the maximum number of unique flavors we can keep.

Starting with the window at position [0, k-1] means we initially keep candies from position k to n-1. Then we slide the window one position at a time, updating our counter and checking if we've found a better arrangement.

Learn more about Sliding Window patterns.

Solution Approach

We implement a sliding window approach with a hash table to track the candies we keep.

Initial Setup:

• Create a Counter cnt that stores the frequency of candies from index k to n-1 (these are the candies we keep when giving away the first k candies)
• Initialize ans with the size of cnt, which represents the number of unique flavors when we give away candies [0, k-1]

Sliding the Window: We iterate from index k to n-1, where each iteration represents sliding our window one position to the right:

1. Add the candy leaving the window: When we move the window right, the candy at position i-k (which was inside the window) now becomes ours. We increment its count in cnt:

   cnt[candies[i - k]] += 1

2. Remove the candy entering the window: The candy at position i (which was ours) now enters the window to be given away. We decrement its count in cnt:

   cnt[candies[i]] -= 1

3. Clean up zero counts: If the count of candies[i] becomes 0, we remove it from the counter entirely since we no longer have any candies of that flavor:

   if cnt[candies[i]] == 0:
       cnt.pop(candies[i])

4. Update the maximum: After adjusting the counter, the number of unique flavors we have is len(cnt). We update our answer:

   ans = max(ans, len(cnt))

Time and Space Complexity:

• Time: O(n) where n is the length of the candies array, as we visit each element once
• Space: O(n) in the worst case where all candies have different flavors

The algorithm efficiently finds the optimal window position by trying all possible positions and keeping track of the maximum unique flavors achievable.

Example Walkthrough

Let's walk through the solution with candies = [2, 1, 3, 3, 2] and k = 2.

We need to give away 2 consecutive candies and maximize the unique flavors we keep.

Initial Setup:

• We start by considering giving away candies at indices [0, 1] (values [2, 1])
• We keep candies from index 2 to 4: [3, 3, 2]
• Create counter cnt = {3: 2, 2: 1} (two 3's and one 2)
• Initial ans = 2 (we have 2 unique flavors: 3 and 2)

Sliding the Window:

Iteration 1 (i = 2):

• Window moves from [0,1] to [1,2]
• Candy at index 0 (value 2) leaves the window and becomes ours
  • cnt[2] += 1 → cnt = {3: 2, 2: 2}
• Candy at index 2 (value 3) enters the window
  • cnt[3] -= 1 → cnt = {3: 1, 2: 2}
• We still have 2 unique flavors
• ans = max(2, 2) = 2

Iteration 2 (i = 3):

• Window moves from [1,2] to [2,3]
• Candy at index 1 (value 1) leaves the window and becomes ours
  • cnt[1] += 1 → cnt = {3: 1, 2: 2, 1: 1}
• Candy at index 3 (value 3) enters the window
  • cnt[3] -= 1 → cnt = {3: 0, 2: 2, 1: 1}
  • Since cnt[3] = 0, remove it → cnt = {2: 2, 1: 1}
• We have 2 unique flavors
• ans = max(2, 2) = 2

Iteration 3 (i = 4):

• Window moves from [2,3] to [3,4]
• Candy at index 2 (value 3) leaves the window and becomes ours
  • cnt[3] += 1 → cnt = {2: 2, 1: 1, 3: 1}
• Candy at index 4 (value 2) enters the window
  • cnt[2] -= 1 → cnt = {2: 1, 1: 1, 3: 1}
• We have 3 unique flavors!
• ans = max(2, 3) = 3

Result: The maximum unique flavors we can keep is 3, achieved by giving away candies at indices [3,4] and keeping [2, 1, 3].

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the candies array. The algorithm performs the following operations:

• Initial creation of a Counter for candies[k:] takes O(n-k) time
• The for loop iterates from k to n-1, which is O(n-k) iterations
• Inside each iteration, we perform constant time operations: adding to counter, subtracting from counter, checking if count is zero, potentially removing from counter, and updating the maximum - all O(1) operations
• Therefore, the total time complexity is O(n-k) + O(n-k) × O(1) = O(n)

The space complexity is O(n). The Counter cnt stores the frequency of unique candy types. In the worst case, when all candies are of different types, the Counter could contain up to n-k elements initially, and through the sliding window process, it could potentially store information about all n unique candy types at different points in the execution. Therefore, the space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Off-by-One Error in Window Boundaries

A common mistake is incorrectly calculating which candy is leaving or entering the window when sliding. Developers often confuse:

• Which candy should be added back (the one leaving the give-away window)
• Which candy should be removed (the one entering the give-away window)

Incorrect Implementation:

for i in range(k, len(candies)):
    # Wrong: Adding the candy that's entering the window
    candy_counter[candies[i]] += 1
    # Wrong: Removing the candy that's leaving the window
    candy_counter[candies[i - k]] -= 1

Correct Implementation:

for i in range(k, len(candies)):
    # Correct: Add back the candy leaving the give-away window
    candy_counter[candies[i - k]] += 1
    # Correct: Remove the candy entering the give-away window
    candy_counter[candies[i]] -= 1

2. Forgetting to Handle the Edge Case k = n

When k equals the array length, all candies must be given away, leaving none for yourself. Without this check, the code might try to access candies[k:] which would be an empty slice, but the logic would still incorrectly return a non-zero value.

Solution:

if k == len(candies):
    return 0

3. Not Cleaning Up Zero-Count Entries

Failing to remove entries with zero count from the counter will lead to incorrect unique flavor counting. The len(candy_counter) would include flavors with zero count, inflating the result.

Incorrect:

candy_counter[candies[i]] -= 1
# Missing: removal of zero-count entries
max_unique_types = max(max_unique_types, len(candy_counter))

Correct:

candy_counter[candies[i]] -= 1
if candy_counter[candies[i]] == 0:
    candy_counter.pop(candies[i])
max_unique_types = max(max_unique_types, len(candy_counter))

4. Incorrect Initial Window Setup

Some might try to initialize by counting all candies first, then removing the first k candies. This approach is more error-prone and less efficient.

Less Optimal:

candy_counter = Counter(candies)
for i in range(k):
    candy_counter[candies[i]] -= 1
    if candy_counter[candies[i]] == 0:
        candy_counter.pop(candies[i])

Better:

candy_counter = Counter(candies[k:])  # Direct initialization with kept candies