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: 1

💡 Note: Must give away 2 consecutive candies from [1,2,3]. Giving [1,2] keeps [3] with 1 unique flavor, giving [2,3] keeps [1] with 1 unique flavor. Maximum is 1.

Constraints

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

Visualization

Tap to expand

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

✓ Brute Force - Try All Windows

⏱️ Time: O(n²) Space: O(n)

For each possible starting position, remove k consecutive candies and count how many unique flavors remain. Keep track of the maximum unique flavors across all possibilities.

Optimized Sliding Window

⏱️ Time: O(n) Space: O(n)

First count total unique flavors and frequency of each. Then use sliding window to find which k consecutive candies to remove that minimizes the loss of unique flavors.

Brute Force - Try All Windows — Algorithm Steps

Step 1: For each possible starting position i from 0 to n-k
Step 2: Create a copy without candies[i] to candies[i+k-1]
Step 3: Count unique flavors in remaining array
Step 4: Track maximum unique count

Visualization

Tap to expand

Step-by-Step Walkthrough

Try Window 1

Remove first k candies, count unique in remainder

Try Window 2

Remove next k candies, count unique in remainder

Continue

Try all positions, keep maximum unique count

Code -

solution.c — C

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

int solution(int* candies, int n, int k) {
    int maxUnique = 0;
    
    // Try removing each possible consecutive subarray of length k
    for (int start = 0; start <= n - k; start++) {
        // Use array to track unique flavors (assuming flavors are small integers)
        int seen[10001] = {0}; // Adjust size based on constraints
        int uniqueCount = 0;
        
        // Add flavors before the removed window
        for (int i = 0; i < start; i++) {
            if (seen[candies[i] + 5000] == 0) { // Offset for negative numbers
                seen[candies[i] + 5000] = 1;
                uniqueCount++;
            }
        }
        // Add flavors after the removed window
        for (int i = start + k; i < n; i++) {
            if (seen[candies[i] + 5000] == 0) {
                seen[candies[i] + 5000] = 1;
                uniqueCount++;
            }
        }
        
        if (uniqueCount > maxUnique) {
            maxUnique = uniqueCount;
        }
    }
    
    return maxUnique;
}

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²)

Outer loop runs n-k+1 times, inner counting takes O(n) time each iteration

⚠ Quadratic Growth

Space Complexity

O(n)

Need to store temporary arrays and hash sets for counting unique elements

⚡ Linearithmic Space

8.5K 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

Number of Unique Flavors After Sharing K Candies - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Windows — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler