Distinct Candies- LeetCode

This is the sixth question on our AlgoMaster Sheet. This is a pretty standard question and will help you to clear your fundamentals regarding Hashing, HashMaps, and C++ STL(Standard Template Library) in general. If you haven’t yet checked our STL Video or our article on C++ STL, please make sure to check them out before proceeding further.

Problem Statement:

Alice has n candies, where the ith candy is of type candyType[i]. Alice noticed that she started to gain weight, so she visited a doctor.

The doctor advised Alice to only eat n / 2 of the candies she has (n is always even). Alice likes her candies very much, and she wants to eat the maximum number of different types of candies while still following the doctor’s advice.

Given the integer array candyType of length n, return the maximum number of different types of candies she can eat if she only eats n / 2 of them.

Example 1:

Input: candyType = [1,1,2,2,3,3]
Output: 3
Explanation: Alice can only eat 6 / 2 = 3 candies. Since there are only 3 types, she can eat one of each type.

Example 2:

Input: candyType = [1,1,2,3]
Output: 2
Explanation: Alice can only eat 4 / 2 = 2 candies. Whether she eats types [1,2], [1,3], or [2,3], she still can only eat 2 different types.

Example 3:

Input: candyType = [6,6,6,6]
Output: 1
Explanation: Alice can only eat 4 / 2 = 2 candies. Even though she can eat 2 candies, she only has 1 type.

Constraints:

  • n == candyType.length
  • 2 <= n <= 104
  • n is even.
  • -105 <= candyType[i] <= 105

Intuition:

Let us look at a given example, to help us understand the question better.

For example, if we take our candyType = [1, 1, 2, 2, 3, 3]. If we look at the given array, we have 3 different types of candies – Candy1 is present 2 times, Candy2 is present 2 times and lastly Candy3 is present only a single time. But the question also has given us a limit- the limit set by the doctor. So according to the question, the Number of Different Types of Candies 3, the limit set by the doctor is 6 / 2 = 3, thus she can eat all the different types of candy- Candy1, Candy2 as well as Candy3. Thus, we return 3 in this case!!

As the question states, Alice can have a maximum number of candies up to N/2 times, or else she will gain a lot of weight. That’s why we cannot go beyond N/2, where N is the size of the given array candyType[]. That’s why we have to check whether the number of candies of different types exceeds N/2 or not.

Now. with everything being said. you should have an idea or slight approach to how to solve it. Let me elaborate a bit- Alice cannot eat more than N/2 different types of candies. Now the question arises of which data structure is optimal if we want to check how many different types of data type is present in an array- YES YES!! You guessed it right- We need to use HashMap or HashSet in this question.

Unordered-Maps-in-C++

The question now becomes a cakewalk- We just need to look out how many different types of candies are present in the candyType[] array. If the number of DIFFERENT TYPES of Candies is less than the limit set by the doctor(N / 2), we can safely return the Size of the Map. If the limit becomes greater than N / 2, then sadly for Alice she CAN NOT EAT ALL THE DIFFERENT TYPES OF CANDIES- the maximum she can eat is, as predefined by her doctor, N / 2 {N is the size of the array candyType[] }

If we closely look at the 3rd TestCase, the candyType[] array is [6, 6, 6, 6]. There is only a single type of Candy- Candy6 present in the array. So, irrespective of the limit set by the doctor, which in this case is- 4 / 2 = 2, Alice has to satisfy her thrust of candies by eating candies of only a SINGLE TYPE. So we return 1(One) in this case!!

Algorithm:-

  1. Calculate the size of the given candyType[] and store it in variable N.
  2. Count the limit set by the doctor, that is N / 2, and store it in our limit.
  3. Declare a HashMap or HashSet in the language of your choice.
  4. Next, we traverse over the array candyType[] and store the frequency of each candy in the hashMap we have declared above.
  5. In the end, we check if the number of different types of candies present in the candyType[] array, that is the size of the HashMap, is less than or equal to (<=) the limit set by the doctor. If true, we return the size of the map.
  6. Else we return the Limit Set by the Doctor.

Code:-

class Solution {
public:

    int distributeCandies(vector<int>& candyType) // Count the number of TYPES of candies by adding each type to a HashMap.
    {
        
        int n = candyType.size() ; // Store the size of the array candyType[]
        
        int limit = n / 2 ; // Calculate the Limit as N / 2
        
        unordered_map<int , int> map ; // HashMap will help us to store the number of different types of candies
        
        for(int nums : candyType)
        {
            map[nums]++ ; // Incrementing the count of different types of candies in the map
        }
        
        if(map.size() <= limit) // If the size of the map, that is, the number of different types of candies, is less than Limit
            return map.size() ; // Then we return the size of the Map
        
        else
            return limit ; // Otherwise Alice cannot eat all the different types of candies, she has to eat upto the Limit set by her doctor
        
}
};

// Time Complexity:  O(N)
// Space Complexity: O(N)
int distributeCandies(vector<int>& candyType)
{
        
        int n = candyType.size() ; 
        
        int limit = n / 2 ; 
        
        unordered_map<int , int> map ; 
        
        for(int nums : candyType)
        {
            map[nums]++ ; 
        }
        
        if(map.size() <= limit) 
            return map.size() ; 
        
        else
            return limit ; 
        
}
public int distributeCandies(int[] candyType) 
{
        int n = candyType.length ; 
        
        int limit = n / 2 ; 
        
        HashMap<Integer,Integer> map = new HashMap<>(); 
        
        for(int nums : candyType)
        {
            if(map.containsKey(nums))
                map.put( nums , map.get(nums)+1 ); 
            else
                map.put(nums,1);
        }
        
        if(map.size() <= limit) 
            return map.size() ; 
        
        else
            return limit ; 
}

Analysis of Time & Space Complexity:-

As we have traversed through the array candyType[] only once, thus the Time Complexity is only Linear and is O(N). Similarly, as we are using an external HashMap or HashSet, thus the Space Complexity is also Linear and is O(N).

If you have still any more doubts, make sure to check the following video by SUNYUL HOSSEN and also follow his YouTube Channel – CS FOR ALL for such amazing content!! For any questions, regarding the post, you can post down in the comment section!!

Contributors: Arghya Chatterjee: LinkedIn & Tanmay Dutta: LinkedIn

6 Comments

  1. Tanmay
    December 16, 2022

    This is the best article πŸ‘πŸ»

  2. Debasmita Banerjee
    December 16, 2022

    Well elaborated!πŸ™Œ

    • Team cfa
      December 16, 2022

      Thank you 😊 it will help us a lot

  3. Arnab paul
    December 16, 2022

    π™Άπš˜πš˜πš πšŠπš›πšπš’πšŒπš•πšŽ πŸ‘πŸ‘

  4. Deepanshu Dutta
    December 18, 2022

    Excellent article πŸ‘

  5. gate io labs
    January 29, 2023

    My colleague shared your article with me and I found it very useful after reading it. Great article, it helped me a lot. I also hope to make a beautiful website like your blog, hope you can give me some advice, my website:
    gate io labs

Leave a Comment