Number of Unique Flavors After Sharing K Candies

Number of Unique Flavors After Sharing K Candies

What is this problem about?

The Number of Unique Flavors After Sharing K Candies problem gives you an array of candy flavors. You give away exactly k consecutive candies (a contiguous subarray of length k) to a friend. Find the maximum number of unique flavors you can keep for yourself. This coding problem uses a sliding window of size k to identify which flavors are removed and maximize remaining unique flavors.

Why is this asked in interviews?

Microsoft asks this because it requires maintaining the frequency of elements both inside and outside a fixed-size window — a classic two-hashmap sliding window problem. The array, hash table, and sliding window interview pattern is directly demonstrated.

Algorithmic pattern used

Fixed-size sliding window with two frequency maps. Maintain inside (frequency of candies in the current k-window) and outside (frequency of all other candies). Start with the first k candies in inside and the rest in outside. Count unique flavors in outside (keys with count > 0). Slide the window: remove the leftmost element from inside (if count drops to 0, remove key), add its neighbor to outside. Add the next element to inside (remove from outside). Track max unique outside count.

Example explanation

candies=[1,2,1,3,1,4,1,2,3], k=3. Window [1,2,1]: outside=[3,1,4,1,2,3]. outside freq: {3:2,1:2,4:1,2:1}. Unique=4. Window [2,1,3]: outside=[1,1,4,1,2,3]. outside freq: {1:3,4:1,2:1,3:1}. Unique=4. Continue sliding. Max unique = 4 (varies with window).

Common mistakes candidates make

• Using a set for outside (doesn't track counts correctly when same flavor is in both window and outside).
• Not handling the case where a flavor exists in both inside and outside.
• Recomputing the outside frequency from scratch for each window position.
• Off-by-one in the initial window setup.

Interview preparation tip

Two-hashmap sliding window problems track what's "in the window" and what's "out of the window" simultaneously. When sliding, update both maps incrementally: slide out one element (remove from inside, add to outside), slide in a new element (add to inside, remove from outside). Track the outside unique count as a running variable — increment when a flavor's outside count goes from 0 to 1, decrement when it drops from 1 to 0. Practice maintaining running unique counts across sliding window variants.