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 <= 1051 <= candies[i] <= 1050 <= k <= candies.lengthProblem 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.
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.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Window Check | O(n * k) | O(n) | Useful for understanding the problem or when constraints are very small |
| Sliding Window + Hash Table | O(n) | O(n) | Optimal approach for large arrays; maintains flavor frequencies while sliding the window |
2107. Number of Unique Flavors After Sharing K Candies (Leetcode Medium) • Programming Live with Larry • 255 views views
Watch 1 more video solutions →Practice Number of Unique Flavors After Sharing K Candies with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor