LeetCode Problem 2107

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window

Solution

LeetCode 2107 - Number of Unique Flavors After Sharing K Candies

Problem Understanding

The problem gives us an integer array candies, where each value represents the flavor of a candy. We must give exactly k consecutive candies to our sister. After removing those k candies, we keep the remaining candies for ourselves.

Our goal is to maximize the number of distinct candy flavors that remain in our possession.

In other words, we are choosing a contiguous subarray of length k to remove, and we want the remaining elements outside that window to contain as many unique values as possible.

For example, if:

candies = [1,2,2,3,4,3]
k = 3

and we remove the subarray [2,2,3], then the remaining candies are:

[1,4,3]

The remaining distinct flavors are {1,3,4}, so the answer is 3.

The constraints are important:

• candies.length can be as large as 10^5
• Candy flavors can also be as large as 10^5

This immediately tells us that an O(n^2) solution will likely time out. We need an algorithm that runs in linear time or close to it.

There are several important edge cases:

• k = 0, meaning we give away nothing
• k = n, meaning we give away all candies
• Arrays with all identical flavors
• Arrays where every flavor is unique
• Empty arrays

The problem guarantees that 0 <= k <= candies.length, so we never need to handle invalid window sizes.

Approaches

Brute Force Approach

A straightforward solution is to try every possible consecutive block of size k.

For each possible window:

1. Remove that window conceptually
2. Build a set of the remaining candies
3. Count the unique flavors
4. Track the maximum result

This works because we explicitly evaluate every valid choice of candies to share.

However, this approach is too slow.

If the array has length n, there are O(n) possible windows. For each window, rebuilding the remaining set may take O(n) time. That leads to an overall complexity of O(n^2).

With n = 100000, this is not practical.

Optimal Sliding Window Approach

The key observation is that instead of repeatedly rebuilding the remaining candies, we can maintain frequency counts dynamically.

Think about the problem differently:

• Initially, we own all candies
• Then we slide a window of size k
• The candies inside the window are given away
• The candies outside the window remain ours

We can maintain a frequency map representing the candies we currently keep.

Initially:

• The frequency map contains counts for all candies
• The number of keys in the map equals the number of unique flavors we currently own

As the sharing window slides:

• A candy entering the window is removed from our collection
• A candy leaving the window is added back to our collection

This allows us to update the answer in constant time per step.

Because each candy is processed only a few times, the entire algorithm becomes linear.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Rebuilds remaining flavors for every window
Optimal	O(n)	O(n)	Uses sliding window with frequency counting

Algorithm Walkthrough

1. Create a frequency map containing the count of every candy flavor in the entire array.

This represents all candies we initially keep before sharing anything. 2. Compute the initial number of unique flavors.

This is simply the number of keys in the frequency map. 3. Handle the special case where k == 0.

If we do not give away any candies, the answer is just the total number of distinct flavors. 4. Start sliding a window of size k across the array.

The window represents candies being shared with the sister. 5. For each candy entering the window:

• Decrease its count in the frequency map
• If its count becomes zero, remove it from the map entirely

This reflects that we no longer own that flavor outside the shared window. 6. Once the window reaches size k, compute the number of unique flavors remaining.

Since the map only contains candies we still keep, the answer at this point is simply:

len(frequency_map)

7. Update the maximum answer.
8. Before moving the window forward:

• Add back the leftmost candy of the current window
• Increase its frequency in the map

This reflects reclaiming ownership of that candy after it leaves the shared segment. 9. Continue until all windows have been processed.

Why it works

The sliding window always represents the exact candies being shared. The frequency map always represents the candies we still own outside the window.

Because the map is updated consistently when candies enter or leave the window, the number of keys in the map is always equal to the number of unique flavors we currently keep.

By checking every valid window exactly once, we guarantee that the maximum recorded value is the optimal answer.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def shareCandies(self, candies: List[int], k: int) -> int:
        frequency = Counter(candies)

        if k == 0:
            return len(frequency)

        max_unique = 0
        left = 0

        for right in range(len(candies)):
            flavor = candies[right]

            frequency[flavor] -= 1

            if frequency[flavor] == 0:
                del frequency[flavor]

            if right - left + 1 == k:
                max_unique = max(max_unique, len(frequency))

                left_flavor = candies[left]
                frequency[left_flavor] = frequency.get(left_flavor, 0) + 1

                left += 1

        return max_unique

The implementation begins by building a Counter containing frequencies for every candy flavor. This represents all candies currently owned.

If k == 0, no candies are shared, so we immediately return the number of distinct flavors.

The sliding window is controlled using two pointers:

• left
• right

As the right pointer expands the window, the corresponding candy is removed from the frequency map because it is now shared.

Whenever a frequency becomes zero, the flavor is deleted from the map entirely. This keeps len(frequency) equal to the number of distinct flavors we still own.

Once the window size becomes exactly k, we update the answer using the current number of unique flavors remaining.

Before moving forward, we restore the candy at the left side of the window back into the map, because it will no longer be shared in the next iteration.

This guarantees correct state maintenance throughout the sliding process.

Go Solution

func shareCandies(candies []int, k int) int {
	frequency := make(map[int]int)

	for _, candy := range candies {
		frequency[candy]++
	}

	if k == 0 {
		return len(frequency)
	}

	maxUnique := 0
	left := 0

	for right := 0; right < len(candies); right++ {
		flavor := candies[right]

		frequency[flavor]--

		if frequency[flavor] == 0 {
			delete(frequency, flavor)
		}

		if right-left+1 == k {
			if len(frequency) > maxUnique {
				maxUnique = len(frequency)
			}

			leftFlavor := candies[left]
			frequency[leftFlavor]++

			left++
		}
	}

	return maxUnique
}

The Go implementation follows the same logic as the Python solution.

A map[int]int is used instead of Python's Counter. Since Go maps return zero values automatically for missing keys, incrementing restored frequencies is straightforward.

The delete function removes flavors whose counts reach zero, ensuring that len(frequency) accurately tracks the number of unique remaining flavors.

No special handling for integer overflow is necessary because all values remain well within Go's integer range.

Worked Examples

Example 1

candies = [1,2,2,3,4,3]
k = 3

Initial frequency map:

Flavor	Count
1	1
2	2
3	2
4	1

Initial unique flavors = 4

Sliding Window Trace

Step	Window	Removed Candy	Frequency Map Keys	Unique Remaining
right=0	[1]	1	{2,3,4}	not ready
right=1	[1,2]	2	{2,3,4}	not ready
right=2	[1,2,2]	2	{3,4}	2
right=3	[2,2,3]	3	{1,3,4}	3
right=4	[2,3,4]	4	{1,2,3}	3
right=5	[3,4,3]	3	{1,2}	2

Maximum = 3

Example 2

candies = [2,2,2,2,3,3]
k = 2

Initial frequencies:

Flavor	Count
2	4
3	2

Sliding Window Trace

Window	Remaining Candies	Unique Flavors
[2,2]	[2,2,3,3]	2
[2,2]	[2,2,3,3]	2
[2,2]	[2,2,3,3]	2
[2,3]	[2,2,3]	2
[3,3]	[2,2,2,2]	1

Maximum = 2

Example 3

candies = [2,4,5]
k = 0

No candies are shared.

Distinct flavors are:

{2,4,5}

Answer = 3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each candy enters and leaves the sliding window at most once
Space	O(n)	Frequency map may store all distinct candy flavors

The algorithm is linear because every array element is processed a constant number of times. Frequency updates, insertions, and deletions in the hash map are all average O(1) operations.

The space complexity depends on the number of distinct candy flavors. In the worst case, every candy has a different flavor, so the map stores n entries.

Test Cases

from typing import List

class Solution:
    def shareCandies(self, candies: List[int], k: int) -> int:
        from collections import Counter

        frequency = Counter(candies)

        if k == 0:
            return len(frequency)

        max_unique = 0
        left = 0

        for right in range(len(candies)):
            flavor = candies[right]

            frequency[flavor] -= 1

            if frequency[flavor] == 0:
                del frequency[flavor]

            if right - left + 1 == k:
                max_unique = max(max_unique, len(frequency))

                left_flavor = candies[left]
                frequency[left_flavor] = frequency.get(left_flavor, 0) + 1

                left += 1

        return max_unique

sol = Solution()

assert sol.shareCandies([1,2,2,3,4,3], 3) == 3  # provided example
assert sol.shareCandies([2,2,2,2,3,3], 2) == 2  # provided example
assert sol.shareCandies([2,4,5], 0) == 3  # no candies shared

assert sol.shareCandies([], 0) == 0  # empty array
assert sol.shareCandies([1], 0) == 1  # single candy, keep all
assert sol.shareCandies([1], 1) == 0  # single candy, share all

assert sol.shareCandies([1,1,1,1], 2) == 1  # all identical flavors
assert sol.shareCandies([1,2,3,4], 2) == 2  # all distinct flavors

assert sol.shareCandies([1,2,1,2,3], 3) == 2  # overlapping repeated flavors
assert sol.shareCandies([5,5,5,6,7], 1) == 3  # removing duplicate flavor
assert sol.shareCandies([1,2,3,4,5], 5) == 0  # share entire array

assert sol.shareCandies([1,2,2,1,3,3,4], 4) == 3  # mixed repeated patterns

Test	Why
[1,2,2,3,4,3], k=3	Validates standard sliding window behavior
[2,2,2,2,3,3], k=2	Tests repeated flavors
[2,4,5], k=0	Tests no sharing case
[], k=0	Tests empty input
[1], k=0	Tests single element without removal
[1], k=1	Tests removing entire array
[1,1,1,1], k=2	Tests all identical flavors
[1,2,3,4], k=2	Tests all distinct flavors
[1,2,1,2,3], k=3	Tests repeated overlapping patterns
[5,5,5,6,7], k=1	Tests removal of duplicates
[1,2,3,4,5], k=5	Tests full removal
[1,2,2,1,3,3,4], k=4	Tests complex mixed frequencies

Edge Cases

One important edge case occurs when k = 0. In this situation, no candies are shared, so the answer should simply be the total number of distinct flavors in the original array. A buggy implementation might still attempt sliding window logic and accidentally remove elements. The implementation avoids this by returning early before window processing begins.

Another critical edge case is when k = len(candies). Here, every candy is shared with the sister, leaving us with no candies at all. The correct answer is therefore 0. The sliding window naturally handles this because the frequency map becomes empty once the entire array enters the window.

Arrays with all identical flavors are another common source of mistakes. For example:

[1,1,1,1]

Even after removing some candies, the remaining candies still contain only one distinct flavor. Incorrect implementations may confuse total count with distinct count. Using a frequency map and counting only map keys ensures correctness.

An empty input array also deserves attention. Since there are no candies, the answer must be 0. The implementation handles this naturally because the frequency map starts empty and no sliding occurs.

Finally, arrays with completely distinct flavors require careful handling. Removing any window reduces the number of remaining unique flavors exactly by the number of removed elements. The sliding window correctly captures this because frequencies drop to zero immediately for removed flavors.