Number of Unique Flavors After Sharing K Candies

Number of Unique Flavors After Sharing K Candies - Problem

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 unique flavors of candies as possible.

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

Input & Output

Example 1 — Basic Case

$ Input: candies = [1,2,1,3,2], k = 2

› Output: 3

💡 Note: Give sister candies [1,2] (positions 0-1), [2,1] (positions 1-2), or [1,3] (positions 2-3), or [3,2] (positions 3-4). Best choice is any that keeps all 3 unique flavors {1,2,3}.

Example 2 — All Same Flavors

$ Input: candies = [1,1,1,1], k = 2

› Output: 1

💡 Note: No matter which 2 consecutive candies we give away, we always keep flavor 1, so answer is 1 unique flavor.

Example 3 — Must Lose Unique Flavor

$ Input: candies = [1,2,3], k = 2

› Output: 2

💡 Note: Must give away 2 consecutive candies from [1,2,3]. Giving [1,2] keeps {3}, giving [2,3] keeps {1}. Maximum is 1, but we can give [1,2] and keep [3], or give [2,3] and keep [1]. Wait, let me recalculate: give [1,2] keeps [3] = 1 unique, give [2,3] keeps [1] = 1 unique. Actually answer should be 1.

Constraints

1 ≤ candies.length ≤ 10⁵
1 ≤ k ≤ candies.length
1 ≤ candies[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array of candy flavors and k consecutive candies to share

Process

Find which k consecutive candies to remove to keep most unique flavors

Output

Maximum number of unique flavors you can keep

Key Takeaway

🎯 Key Insight: Find the k consecutive candies whose removal loses the fewest unique flavors

Asked in

G Google 15 a Amazon 12 Apple 8 f Meta 6

Find the maximum unique flavors you can keep after giving away k consecutive candies. The key insight is to find which consecutive window of k candies to remove that minimizes the loss of unique flavors. Best approach uses sliding window with frequency counting. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Sliding Window	O(n)	O(n)	Use frequency counting and sliding window to efficiently find the best k consecutive candies to remove
Brute Force - Try All Windows	O(n²)	O(n)	Try removing every possible consecutive subarray of length k and count remaining unique flavors

Optimized Sliding Window — Algorithm Steps

Step 1: Count frequency of all flavors and total unique count
Step 2: Use sliding window of size k to track flavors to remove
Step 3: For each window, calculate how many unique flavors would be lost
Step 4: Choose window that loses minimum unique flavors

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Total

Count frequency of all flavors in array

Slide Window

Move k-sized window and track which flavors would be lost

Find Minimum

Choose window that loses fewest unique flavors

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* candies, int n, int k) {
    // Simple implementation using arrays for frequency counting
    // Assuming flavor values are in reasonable range
    int totalFreq[10001] = {0};
    int minVal = 5000, maxVal = 5000; // Track range for efficiency
    
    // Count frequency of each flavor
    for (int i = 0; i < n; i++) {
        int idx = candies[i] + 5000; // Offset for negative numbers
        totalFreq[idx]++;
        if (candies[i] < minVal) minVal = candies[i];
        if (candies[i] > maxVal) maxVal = candies[i];
    }
    
    // Count total unique flavors
    int totalUnique = 0;
    for (int i = minVal + 5000; i <= maxVal + 5000; i++) {
        if (totalFreq[i] > 0) totalUnique++;
    }
    
    int minLost = totalUnique; // Initialize with worst case
    
    // Try each window of size k
    for (int start = 0; start <= n - k; start++) {
        int windowFreq[10001] = {0};
        
        // Count frequency in current window
        for (int i = start; i < start + k; i++) {
            windowFreq[candies[i] + 5000]++;
        }
        
        // Count how many unique flavors would be lost
        int lost = 0;
        for (int i = minVal + 5000; i <= maxVal + 5000; i++) {
            if (windowFreq[i] > 0 && windowFreq[i] == totalFreq[i]) {
                lost++;
            }
        }
        
        if (lost < minLost) {
            minLost = lost;
        }
    }
    
    return totalUnique - minLost;
}

int main() {
    char line[100000];
    fgets(line, sizeof(line), stdin);
    
    // Simple array parsing
    int candies[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '\n') {
            candies[n++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    int k;
    scanf("%d", &k);
    
    int result = solution(candies, n, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through array: one to count frequencies, one sliding window pass

✓ Linear Growth

Space Complexity

O(n)

Hash maps to store frequency counts of all flavors and current window

⚡ Linearithmic Space

8.4K Views

Medium Frequency

~15 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Sliding Window — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler