2107. Number of Unique Flavors After Sharing K Candies

MediumArrayHash TableSliding Window
Leetcode Link

Problem Description

You have an array of integers named candies where each element represents the flavor of a candy. The position of the flavored candy in the list is its index, starting from 0. You are tasked with sharing a certain number k of consecutive candies with your sister. The goal is to retain the highest number of unique candy flavors for yourself after you share k consecutive candies with her. You must figure out the maximum number of unique flavors you can keep after giving away k candies.

Intuition

The key to solving this problem lies in understanding that when you give away a range of consecutive candies, the unique flavors you have left are the ones not included in the range you gave away. To maximize the unique flavors, you want to give away the segment which has the least number of unique flavors. To find the solution, you can use a sliding window approach that moves across the candies array. This sliding window will represent the candies you will give to your sister.

  • Starting after the first k candies, count the unique flavors you have (all the candies except the first k ones).
  • Then, for each subsequent candy, adjust the count by removing the flavor going out of the window and adding the flavor coming into the window at the end.
  • Note that if after removing a candy from the count its frequency drops to zero, remove it from the count to maintain an accurate representation of unique flavors.
  • Update and keep track of the maximum count of unique flavors after each step.

By iterating through the array and adjusting the window of candies given to your sister, we can determine the maximum number of unique flavors that can be kept.

Learn more about Sliding Window patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The solution uses a sliding window approach alongside Python's Counter class (from collections) to keep track of the frequency of each flavor of candy that we can keep (i.e., candies not included in the k consecutive candies given to the sister).

Here's a step-by-step explanation of the implementation:

  1. Begin by counting the unique flavors of the candies that are initially outside the range of the first k candies using Counter(candies[k:]). This gives us the starting set of flavors we have excluding the first k to be given away.

  2. Initialize the count of unique flavors (ans) to the length of the initial count, representing the number of unique flavors after giving away the first segment of k candies.

  3. Iterate over the candies starting from index k up to the end:

    • For each candy at index i, decrement the count of the flavor encountered since it now becomes part of the segment to give away.
    • Increment the count of the flavor i-k, which is now coming into the window of candies we can keep, as the sliding window moves forward.
    • After adjusting the counts, check if the flavor we just decremented has a count of zero, indicating there are no more of that flavor to keep, and if so, remove it from the count.
    • Update the maximum count of unique flavors (ans) with the larger of the current ans or the current number of unique flavors after the adjustments.

The use of Counter makes it efficient to keep track of the frequency of each flavor and its updates, and the max() function assists in retaining the highest number of unique flavors after each iteration. By the end of the loop, ans holds the maximum number of unique flavors that can be kept.

1class Solution:
2    def shareCandies(self, candies: List[int], k: int) -> int:
3        cnt = Counter(candies[k:])
4        ans = len(cnt)
5        for i in range(k, len(candies)):
6            cnt[candies[i]] -= 1
7            cnt[candies[i - k]] += 1
8            if cnt[candies[i]] == 0:
9                cnt.pop(candies[i])
10            ans = max(ans, len(cnt))
11        return ans

This code snippet effectively finds the optimal number of unique flavors that can be retained, utilizing the efficiency of Counter for frequency tracking within the sliding window operated by the loop.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

How many ways can you arrange the three letters A, B and C?

Example Walkthrough

Let's consider the candies array as [1, 2, 3, 2, 2, 1, 3, 3] and k equals 3. Now, let's apply the solution step by step:

  1. We start with the initial Counter(candies[k:]) which excludes the first k candies: Counter([2, 2, 1, 3, 3]), resulting in a count of {2: 2, 1: 1, 3: 2}. Here, you have two unique flavors of #2, one of #1, and two of #3. Therefore, the initial ans (maximum number of unique flavors) is 3, as there are three unique flavors in this count.

  2. We now iterate over candies starting from the k-th element, which is the 3rd index (using zero-based indexing) in the original candies array.

  3. At index 3 (candies[3] is 2), we would give away the second flavor candy, which was in the initial segment to be kept. So, we decrement the count of flavor 2 from {2: 2, 1: 1, 3: 2} to {2: 1, 1: 1, 3: 2}.

  4. We also include the flavor at index 0 (because the window is sliding forward), so flavor 1 is to be added back into our count. The count remains the same because flavor 1 is already in our count {2: 1, 1: 1, 3: 2}.

  5. The current count of unique flavors is still 3, and thus ans remains 3.

  6. Continue the iteration:

    • Move to index 4: Remove one occurrence of flavor 2 and add back flavor 1. Count is now {2: 0, 1: 2, 3: 2}. After removing the flavor 2 count which is zero, the count becomes {1: 2, 3: 2}. ans remains 3.

    • Move to index 5: Remove flavor 1 and add back flavor 2. New count is {1: 1, 3: 2} (since 2 was not in the count, it doesn't get added). ans remains 3.

    • Move to index 6: Remove flavor 3 and there's no flavor at i-k (since we're now at the end of the array). Current count is {1: 1, 3: 1}. ans does not change and remains 3.

By the end of the process, we have iterated through the array and adjusted the window properly. The final ans remains 3, which signifies the maximum number of unique flavors we can retain after sharing k consecutive candies with the sister. The sliding window approach made it efficient to find this out.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def shareCandies(self, candies, k):
5        # Initialize the counter with the candies excluding the first 'k' candies
6        candy_counter = Counter(candies[k:])
7        # Calculate initial number of unique candies
8        max_unique = len(candy_counter)
9      
10        # Iterate over the list starting from the 'k-th' candy to the end
11        for i in range(k, len(candies)):
12            # Decrease the count of the outgoing candy (as the window slides)
13            candy_counter[candies[i - k]] += 1
14            # Increase the count of the incoming candy
15            candy_counter[candies[i]] -= 1
16          
17            # Remove the outgoing candy from counter if its count falls to zero
18            if candy_counter[candies[i]] == 0:
19                del candy_counter[candies[i]]
20
21            # Update the result with the maximum number of unique candies seen so far
22            max_unique = max(max_unique, len(candy_counter))
23      
24        # Return the maximum number of unique candies that can be given to a sibling
25        return max_unique
26
1class Solution {
2
3    public int shareCandies(int[] candies, int k) {
4        // This map will hold the count of each type of candy
5        Map<Integer, Integer> candyCountMap = new HashMap<>();
6        int totalCandies = candies.length;
7      
8        // Initialize the map with the candy count for the first window of size (totalCandies - k)
9        for (int i = k; i < totalCandies; ++i) {
10            candyCountMap.merge(candies[i], 1, Integer::sum);
11        }
12      
13        // The initial answer is the number of distinct candies in the first window
14        int maxDistinctCandies = candyCountMap.size();
15      
16        // Slide the window one candy at a time, updating the map accordingly
17        for (int i = k; i < totalCandies; ++i) {
18            // Decrement the count of the leftmost candy of the previous window
19            // If its count drops to 0, remove it from the map
20            if (candyCountMap.merge(candies[i - k], -1, Integer::sum) == 0) {
21                candyCountMap.remove(candies[i - k]);
22            }
23          
24            // Increment the count of the new candy entering the current window
25            candyCountMap.merge(candies[i], 1, Integer::sum);
26          
27            // Update the max distinct candies seen so far
28            maxDistinctCandies = Math.max(maxDistinctCandies, candyCountMap.size());
29        }
30      
31        // Return the maximum number of distinct candies
32        return maxDistinctCandies;
33    }
34}
35
1#include <vector>
2#include <unordered_map>
3#include <algorithm>
4
5class Solution {
6public:
7    int shareCandies(vector<int>& candies, int k) {
8        // Create a hash map to store the frequency count of each type of candy.
9        unordered_map<int, int> candy_count;
10        int total_candies = candies.size();
11      
12        // Populate the map with the frequencies of the candies starting from index 'k'.
13        for (int i = k; i < total_candies; ++i) {
14            ++candy_count[candies[i]];
15        }
16      
17        // Initialize the maximum number of unique candies as the current size of the map.
18        int max_unique_candies = candy_count.size();
19      
20        // Use a sliding window of size 'k' to find the maximum number of unique candies
21        // that can be shared.
22        for (int i = k; i < total_candies; ++i) {
23            // Decrease the count of the current candy as it is leaving the window.
24            if (--candy_count[candies[i]] == 0) {
25                // If the count becomes zero, remove it from the map.
26                candy_count.erase(candies[i]);
27            }
28          
29            // Increase the count for the new candy entering the window.
30            ++candy_count[candies[i - k]];
31          
32            // Update the max_unique_candies with the current number of unique candies.
33            max_unique_candies = std::max(max_unique_candies, static_cast<int>(candy_count.size()));
34        }
35      
36        // Return the maximum number of unique candies that can be shared.
37        return max_unique_candies;
38    }
39};
40
1// import the necessary modules. In TypeScript, you typically import modules instead of including headers.
2import { max } from "lodash";
3
4// Define the variables and methods globally as required.
5
6// Function to find the share of candies.
7// candies: The array of candy types.
8// k: The number of candies to share.
9function shareCandies(candies: number[], k: number): number {
10    // Create a map to store the frequency count of each type of candy.
11    const candyCount: Map<number, number> = new Map<number, number>();
12    const totalCandies = candies.length;
13  
14    // Populate the map with the frequencies of the candies starting from index 'k'.
15    for (let i = k; i < totalCandies; i++) {
16        candyCount.set(candies[i], (candyCount.get(candies[i]) || 0) + 1);
17    }
18  
19    // Initialize the maximum number of unique candies as the current size of the map.
20    let maxUniqueCandies = candyCount.size;
21  
22    // Use a sliding window of size 'k' to find the maximum number of unique candies
23    // that can be shared.
24    for (let i = k; i < totalCandies; i++) {
25        // Decrease the count of the current candy as it is leaving the window.
26        const currentCandyCount = candyCount.get(candies[i])! - 1;
27        if (currentCandyCount === 0) {
28            // If the count becomes zero, remove it from the map.
29            candyCount.delete(candies[i]);
30        } else {
31            // If count is not zero, then update the count in the map.
32            candyCount.set(candies[i], currentCandyCount);
33        }
34      
35        // Increase the count for the new candy entering the window.
36        const newCandyCount = (candyCount.get(candies[i - k]) || 0) + 1;
37        candyCount.set(candies[i - k], newCandyCount);
38      
39        // Update the maxUniqueCandies with the current number of unique candies.
40        maxUniqueCandies = max([maxUniqueCandies, candyCount.size])!;
41    }
42  
43    // Return the maximum number of unique candies that can be shared.
44    return maxUniqueCandies;
45}
46
47// Note that TypeScript does not have a direct equivalent to `unordered_map` in C++.
48// We use the `Map` object in TypeScript for the key-value mapping.
49// Additionally, TypeScript requires explicit null-checks or 'non-null assertion operators' (!) when dealing with potentially null values.
50
51// Usage of lodash's max function requires it to be installed and imported, or you could write a utility function for that purpose.
52
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity

The initial setup of the Counter cnt with the slice candies[k:] is O(n-k) where n is the length of candies.

The loop runs for n-k iterations (since it starts from k and goes up to n). Within each iteration, the operations on the Counter object (cnt[candies[i]] -= 1, cnt[candies[i - k]] += 1, and cnt.pop(candies[i])) can be considered O(1) on average, as they involve updating the hash table.

Therefore, the total time complexity of the loop is O(n-k). Since the setup time is also O(n-k) and these are done sequentially, the overall time complexity of the function is O(n-k + n-k), which simplifies to O(n), assuming k is much smaller than n.

Space Complexity

The space complexity is dominated by the space needed to store the Counter object cnt. In the worst case, if all candies elements are unique, the Counter will have up to n-k entries, leading to a space complexity of O(n-k). In the best-case scenario, if all elements are the same, the Counter will have just one entry, but since n is the determining factor (assuming k doesn't scale with n), the space complexity remains O(n).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which one best describes the time complexity of the following code?

1int factorial(int n) {
2  if (n < 0) {
3    return -1;
4  } else if (n == 0) {
5    return 1;
6  } else {
7    return n * factorial(n - 1);
8  }
9}

Recommended Readings

Sliding Window Maximum

https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫