Skip to main content
Talentd

Number of Unique Flavors After Sharing K Candies - Solution & Explanation

MediumPremiumFree on FleetCodeArrayHash TableSliding Window11 min readAsked at: Microsoft, Ciena
Practice this problem

Problem Statement

You are given a 0-indexed integer array candies, where candies[i] represents the flavor of the ith 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 <= 105
  • 1 <= candies[i] <= 105
  • 0 <= k <= candies.length

Approach Overview

Problem Overview: You are given an array where each value represents the flavor of a candy. You must give away k consecutive candies and keep the rest. The goal is to maximize the number of unique flavors left after the removal.

Approach 1: Brute Force Window Check (O(n * k) time, O(n) space)

Iterate over every possible subarray of size k representing the candies you give away. For each window, rebuild the remaining set of candies and count unique flavors using a hash set. This requires scanning most of the array repeatedly and reconstructing the set for every window. The approach is straightforward but inefficient for large inputs since each window evaluation can take up to O(n) operations, resulting in roughly O(n * k) or worse depending on implementation.

Approach 2: Sliding Window + Hash Table (O(n) time, O(n) space)

Start by counting frequencies of all flavors using a hash table. This represents candies you currently keep. Then slide a window of size k across the array representing the candies you give away. When a candy enters the window, decrement its frequency in the map because it is no longer kept. If its frequency becomes zero, one unique flavor disappears from your remaining set.

As the window moves forward, restore the candy leaving the window by incrementing its count back in the map. If its frequency changes from 0 → 1, that flavor becomes available again in the remaining candies. Track the number of flavors with positive frequency throughout the process. The maximum value observed after each window placement is the answer.

This pattern is a classic sliding window combined with a frequency map using a hash table. Each element enters and leaves the window exactly once, so the algorithm runs in linear time. The candy list itself is simply an array, and the hash map maintains counts efficiently.

Recommended for interviews: Interviewers expect the sliding window with a frequency map. The brute force approach demonstrates baseline reasoning but quickly becomes too slow. The optimal solution shows that you recognize window-based subarray problems and know how to maintain counts dynamically in O(1) per step.

Solution

We can maintain a sliding window of size k, where the candies outside the window are for ourselves, and the k candies inside the window are shared with our sister and mother. We can use a hash table cnt to record the flavors of the candies outside the window and their corresponding quantities.

Initially, the hash table cnt stores the flavors of the candies from candies[k] to candies[n-1] and their corresponding quantities. At this time, the number of candy flavors is the size of the hash table cnt, that is, ans = cnt.size().

Next, we traverse the candies in the range [k,..n-1], add the current candy candies[i] to the window, and move the candy candies[i-k] on the left side of the window out of the window. Then we update the hash table cnt, and update the number of candy flavors ans to max(ans, cnt.size()).

After traversing all the candies, we can get the maximum number of unique flavors of candies that can be retained.

The time complexity is O(n), and the space complexity is O(n). Here, n is the number of candies.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Window CheckO(n * k)O(n)Useful for understanding the problem or when constraints are very small
Sliding Window + Hash TableO(n)O(n)Optimal approach for large arrays; maintains flavor frequencies while sliding the window

Video Solution

2107. Number of Unique Flavors After Sharing K Candies (Leetcode Medium) • Programming Live with Larry • 260 views views

Watch 1 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Number of Unique Flavors After Sharing K Candies with our built-in code editor and test cases.

Practice on FleetCode
Previous

Remove Boxes

Next

Subarrays with K Different Integers