In this post we will solve the LeetCode 575. Distribute Candies problem.
This problem is not too difficult to get to an answer. Not sure if it was network traffic, but the different attempts, which were accepted, required a different approach. Once you get a first pass accepted, I would suggest that before you leave the LeetCode website, take a look at the implementations that perform best. I was going to implement some of those approaches but got late and had to move on with other tasks.
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. Constraints: o n == candyType.length o 2 <= n <= 10^4 o n is even. o -10^5 <= candyType[i] <= 10^5
In this problem Alice is given different candies. As we will see in the examples, a type of candy may appear once or more times.
Alice wishes to reduce her weight by reducing the number of candies she will have not missing on the variety that she likes.
We will solve this problem using the Java programming language and the VSCode IDE on a Windows computer. The simplest approach is to write your code on the online IDE provided by LeetCode. Since I want to have the test code and the code together, we will have to write a simple test scaffold. Please note that the test code IS NOT PART OF THE SOLUTION!
public int distributeCandies(int[] candyType) {
}
The signature for the function of interest has a single argument that contains the candies available to Alice. We need to return the number of different types of candies Alice will consume.
1,1,2,2,3,3 main <<< candyType: [1, 1, 2, 2, 3, 3] main <<< output: 3 main <<< output: 3 main <<< output: 3 main <<< output: 3 1,1,2,3 main <<< candyType: [1, 1, 2, 3] main <<< output: 2 main <<< output: 2 main <<< output: 2 main <<< output: 2 6,6,6,6 main <<< candyType: [6, 6, 6, 6] main <<< output: 1 main <<< output: 1 main <<< output: 1 main <<< output: 1 1,3,2,2,3,1,4,1 main <<< candyType: [1, 3, 2, 2, 3, 1, 4, 1] main <<< output: 4 main <<< output: 4 main <<< output: 4 main <<< output: 4 100000,0,100000,0,100000,0,100000,0,100000,0,100000,0 main <<< candyType: [100000, 0, 100000, 0, 100000, 0, 100000, 0, 100000, 0, 100000, 0] main <<< output: 2 main <<< output: 2 main <<< output: 2 main <<< output: 2
Each test case is separated from the next by two blank lines.
The first line in each test represents the input line. It holds the different candies made available to Alice. As you can see the first test case contains three different types of candies in a set of six total pieces.
Our test scaffold appears to read the input line, create an array and populate it with the input values. The contents of the array are then displayed to verify all is well so far. The test scaffold appears to call four implementations of the function of interest. For each function that is called the results are displayed.
/**
* Test scaffold
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read candy type int[] ****
int[] candyType = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< candyType: " + Arrays.toString(candyType));
// **** call function of interest and display result ****
System.out.println("main <<< output: " + distributeCandies0(candyType));
// **** call function of interest and display result ****
System.out.println("main <<< output: " + distributeCandies1(candyType));
// **** call function of interest and display result ****
System.out.println("main <<< output: " + distributeCandies2(candyType));
// **** call function of interest and display result ****
System.out.println("main <<< output: " + distributeCandies(candyType));
}
There is little to add to the description of the test scaffold. Each implementation of the function of interest is called and the results are displayed. Note that we are not saving and restoring the contents of the `candyType` int[]. There is no reason to do so. That said, in one of the implementations, the input array is sorted. Given that situation, the implementations that follow will receive as an input the sorted values. That said, with the exception of one implementation in which the array is sorted, the code does not take advantage of this fact.
/**
* Return the maximum number of different types of candies
* she can eat if she only eats n / 2 of them.
* Using priority queue.
*
* 206 / 206 test cases passed.
* Status: Accepted
* Runtime: 248 ms
* Memory Usage: 113.9 MB
*/
static public int distributeCandies0(int[] candyType) {
// **** initialization ****
int nHalf = candyType.length / 2;
PriorityQueue<Integer> pq = new PriorityQueue<>();
// **** populate priority queue ****
for (int c : candyType) pq.add(c);
// **** remove elements from priority queue counting different flavors ****
int diffCnt = 1;
int prev = pq.remove();
while (!pq.isEmpty()) {
// **** for ease of use ****
int c = pq.remove();
// **** count if we found a different candy ****
if (c != prev) {
prev = c;
diffCnt++;
}
// **** we are done ****
if (diffCnt >= nHalf) return nHalf;
}
// **** return maximum number of different candies ****
return diffCnt;
}
In this implementation we will use a priority queue. I just wanted to experiment with such data structures.
We start by populating the priority queue. We then pull the values in a loop. The values would be sorted coming out of the priority queue. If the number of different candies reaches the venue n / 2 our loop returns n / 2 candies. If we complete the last loop, we return the number of different candies.
Please take a look at the comments section in this implementation. The execution time is not that great. Let’s see if we can do better!
/**
* Return the maximum number of different types of candies
* she can eat if she only eats n / 2 of them.
* Using a hashmap.
*
* 206 / 206 test cases passed.
* Status: Accepted
* Runtime: 69 ms
* Memory Usage: 114.7 MB
*/
static public int distributeCandies1(int[] candyType) {
// ***** initialization ****
int nHalf = candyType.length / 2;
HashMap<Integer, Integer> cts = new HashMap<>();
// **** populate candy types hashmap ****
for (int c : candyType) {
Integer cnt = cts.putIfAbsent(c, 1);
if (cnt != null) cts.put(c, ++cnt);
}
// **** count of different candies ****
int diffCnt = cts.size();
// **** return maximum number of different candies ****
if (diffCnt >= nHalf) return nHalf;
else return diffCnt;
}
In this case we will use a hashmap. It seems like we would be processing more information than we need to. This will become apparent when we look at other implementations of the function of interest.
We start by populating the hashmap with the different candies. After the hashmap is full, we get the size of the hashmap which contains the number of different candies. Note that a hashmap contains a pair. In this problem we are interested in the number of different candies bit not on the count of each type.
When all is said and done we return the maximum number of candies Alice will consume.
Take a look at the comments section of this implementation. We did better, but due to the unused data, we should be able to improve on the runtime!
/**
* Return the maximum number of different types of candies
* she can eat if she only eats n / 2 of them.
* Sort candy type array.
*
* Execution: O(n * log(n)) - Space: O(1)
*
* 206 / 206 test cases passed.
* Status: Accepted
* Runtime: 46 ms
* Memory Usage: 99.4 MB
*/
static public int distributeCandies2(int[] candyType) {
// **** initialization ****
int n = candyType.length;
int nHalf = n / 2;
int diffCnt = 1;
// **** sort candy type array - O(n * log(n) ****
Arrays.sort(candyType);
// **** count different candy types - O(n) ****
int type = candyType[0];
for (int i = 1; i < n; i++) {
if (candyType[i] != type) {
// **** ****
diffCnt++;
// **** ****
type = candyType[i];
// **** ****
if (diffCnt >= nHalf) return nHalf;
}
}
// **** return maximum number of different candies ****
return diffCnt;
}
In this implementation of the function of interest instead of using a hashmap we decided to use an array. The problem is that for this algorithm to work, the data in the input array needs to be sorted; so we start by sorting the array.
The loop counts the different types of candies as we traverse the input array. There is a test to exit the loop once the types of candies has reached n / 2.
If the loop completes, we return the number of different types of candies found in the input array.
If you take the time to look at the comments section of the last implementation, it seems that we did better than the previous implementation.
/**
* Return the maximum number of different types of candies
* she can eat if she only eats n / 2 of them.
* Using hashset.
*
* 206 / 206 test cases passed.
* Status: Accepted
* Runtime: 32 ms
* Memory Usage: 41 MB
*/
static public int distributeCandies(int[] candyType) {
// ***** initialization ****
HashSet<Integer> cts = new HashSet<>();
// **** populate candy types hashset - O(n) ****
for (int c : candyType) cts.add(c);
// **** return maximum number of different candies ****
return Math.min(cts.size(), candyType.length / 2);
}
In this implementation we use a hashset. This eliminates the use of the additional data of a hashmap.
After declaring the hashset we populate it with all the values from the input array.
Now we can determine the result by returning the minimum value between the hashset size and n / 2.
Please look at the comments section of this function. We shaved some additional time.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named DistributeCandies.
Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not memorize solutions.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.
Thanks for reading, feel free to connect with me John Canessa at LinkedIn.
Enjoy;
John