Sliding Window Technique - Part 3

Sliding window is a great technique to solve problems in linear time. It usually involves an input of size N, and a window of size K, and thus the problem can be solved in O(N)-time with O(K)-space. This is an example whereby such technique can be applied:

Number of Unique Flavors After Sharing K Candies - LeetCode

2107. Number of Unique Flavors After Sharing K Candies

Medium

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 the 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 the 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.

Example 4:

Input: candies = [2,4,5], k = 3
Output: 0
Explanation:
You have to give all the candies.
You do not have any candies left over, so return 0.

 

Constraints:

• 1 <= candies.length <= 105
• 1 <= candies[i] <= 105
• 0 <= k <= candies.length

Accepted

135

Submissions

196

The sliding window will have size K, you can add/remove from the extremities of the window, and process the results accordingly. The code is down below, cheers, ACC.

public int ShareCandies(int[] candies, int k)
{
    Hashtable countNumbers = new Hashtable();
    foreach (int c in candies)
    {
        if (!countNumbers.ContainsKey(c)) countNumbers.Add(c, 0);
        countNumbers[c] = (int)countNumbers[c] + 1;
    }

    //Sliding window approach
    int maxNumberFlavors = 0;
    for (int i = 0; i < candies.Length; i++)
    {
        //Remove the current (rightmost)
        if (countNumbers.ContainsKey(candies[i]))
        {
            countNumbers[candies[i]] = (int)countNumbers[candies[i]] - 1;
            if ((int)countNumbers[candies[i]] <= 0) countNumbers.Remove(candies[i]);
        }

        if (i == k - 1)
        {
            maxNumberFlavors = countNumbers.Count;
        }
        else if (i >= k)
        {
            //Add the leftmost
            int index = i - k;
            if (!countNumbers.ContainsKey(candies[index])) countNumbers.Add(candies[index], 0);
            countNumbers[candies[index]] = (int)countNumbers[candies[index]] + 1;

            maxNumberFlavors = Math.Max(maxNumberFlavors, countNumbers.Count);
        }
    }

    return maxNumberFlavors;
}