Watch 2 video solutions for Number of Unique Flavors After Sharing K Candies, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Programming Live with Larry has 255 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |