Is Number of Unique Flavors After Sharing K Candies easy or hard?

The problem is typically classified as Medium. The challenge is recognizing that removing k consecutive candies can be modeled as a sliding window and maintaining flavor counts efficiently with a hash table.

Number of Unique Flavors After Sharing K Candies Python/Java solution

Most implementations follow the same structure: build a frequency map of all candies, slide a window of size k, update counts when elements enter or leave the window, and track the number of flavors with positive frequency. The logic is identical across Python, Java, C++, Go, TypeScript, and Rust.

How to solve Number of Unique Flavors After Sharing K Candies in O(n)?

First count the frequency of all flavors in a hash map. Use a sliding window of size k to represent the candies given away. When a candy enters the window, decrement its frequency and reduce the unique count if it reaches zero. When a candy leaves the window, increment its frequency and restore the unique count if it becomes positive again.

What is the best approach for Number of Unique Flavors After Sharing K Candies?

The most efficient approach uses a sliding window with a hash table to track flavor frequencies. Maintain counts of candies that remain after removing a window of size k. As the window slides, update frequencies and track how many flavors still have a positive count. This runs in O(n) time with O(n) space.

Is Number of Unique Flavors After Sharing K Candies asked at Google/Amazon/Meta?

Sliding window and frequency counting problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The exact problem may vary, but the pattern of maintaining counts while sliding a fixed-size window is a common interview topic.

What data structure is used in Number of Unique Flavors After Sharing K Candies?

The core data structure is a hash table (hash map) that stores flavor frequencies. Combined with a sliding window over the array, it allows constant-time updates when candies enter or leave the window.

What is the time complexity of Number of Unique Flavors After Sharing K Candies?

The optimal sliding window solution runs in O(n) time because each candy enters and leaves the window exactly once. Hash table updates and lookups take O(1) on average. Space complexity is O(n) in the worst case if every candy has a unique flavor.

Description Hints 3 Solution Video 11:38

2107. Number of Unique Flavors After Sharing K Candies

Medium62.4% acceptance2 companiesPremium elsewhere, free here

You are given a 0-indexed integer array candies, where candies[i] represents the flavor of the i^th candy. Your mom wants you to share these candies with your little sister by giving her k consecutive candies, but you want to keep as many flavors of candies as possible.

Return the maximum number of unique flavors of candy you can keep after sharing with your sister.

Example 1:

Input: candies = [1,2,2,3,4,3], k = 3
Output: 3
Explanation: 
Give the candies in the range [1, 3] (inclusive) with flavors [2,2,3].
You can eat candies with flavors [1,4,3].
There are 3 unique flavors, so return 3.

Example 2:

Input: candies = [2,2,2,2,3,3], k = 2
Output: 2
Explanation: 
Give the candies in the range [3, 4] (inclusive) with flavors [2,3].
You can eat candies with flavors [2,2,2,3].
There are 2 unique flavors, so return 2.
Note that you can also share the candies with flavors [2,2] and eat the candies with flavors [2,2,3,3].

Example 3:

Input: candies = [2,4,5], k = 0
Output: 3
Explanation: 
You do not have to give any candies.
You can eat the candies with flavors [2,4,5].
There are 3 unique flavors, so return 3.

Constraints:

0 <= candies.length <= 10⁵
1 <= candies[i] <= 10⁵
0 <= k <= candies.length

Asked at 2 companies

Ciena Microsoft

Topics

Hints open one at a time

Hint 1

For every group of k consecutive candies, count the number of unique flavors not inside that group. Return the largest number of unique flavors.

Hint 2

When calculating an adjacent group of k consecutive candies, can you use some of your previous calculations?

Hint 3

Use a sliding window where the window is the group of k consecutive candies you are sharing. Use a hash map to store the number of candies of each type you can keep.

11:38

Still stuck?Read the written solution, or watch a walkthrough.

Open solution