Leetcode: Q1103 — Distribute Candies to People [Easy] (2024)

When you are trying to solve any of these problems, best way is to think about how you would do it in reality.

The concept here is that you give 1 candy to the first person, 2 to the second, 3 to the third and so forth until you run out of candies. Hence, you would need some sort of a counter to keep track of the number of candies you need to give to person X at a certain stage.

Let’s look at two examples to understand this further:

Example 1: You first initialize the array with all 0s, and a counter set to 1. Next you move through the array one by one assigning the current value of the counter to the current index and then incrementing the counter by 1. As a result, the first update (looking at the first row) you would have 1. In the next entry (represented by the second row) you put in 2, then 3 in the third entry (shown in 3rd row).

A point to note here is that since you have a total of 7 candies and you have distributed (1+2+3 = 6) candies so far, you only have 1 candy left while you counter = 4. Hence, what you do in this case is you just give the remaining candy to this person (case when candies to give < candies in hand).

Example 2: We apply the same process here as one in Example 1.

So once again, you start by giving 1 candy to the first person, increment counter, 2 candies to the second one, increment your counter again and so forth.

Note the difference in third row (third entry). At this stage you have (11–2–1 = 8) 8 candies in hand and your counter is 3, so you can give full 3 candies to this person. At row four, the loop starts over again with your counter now at 4 and remaining candies equal to 5 (11–3–2–1 = 5). Therefore, you give 4 candies to this person, totaling 5 candies to this person (1 from last stage, 4 in this stage).

Moving on, your counter is 5 but number of candies in hand is only 1 now, hence you give all the remaining candies to this person. So, the total would be 3 (1+2) for this person (previous stage total candies + this stage candies).

Now that we have a better understanding of the logic behind this problem, let’s look to translate that to code.

We will be running a while loop until we have no candy left. We have also created a result array that keeps track of all the candies to each person, an index variable to keep track of the person (0th person here is actually the first person) and give_candy variable to keep track of the number of candies we need to give at any stage to a person (this is our counter variable we have been talking about).

Next, we check if candies is less than the number of candies we need to give at this point (refer back to Example 1, when we were only able to give 1 candy to the 3rd person), if that is the case we give remaining candies to this person and set candies = 0. Otherwise we keep distributing candies to people based on the problem statement (1 to first, 2 to second, 3 to third and so forth) and decrementing the candies we have left accordingly.

The last if statement in there is when we come to the end of array (given candies to all available people) we go back to the first person.

In the end, we return our result array that holds how many candies each person has.

The Time complexity of this solution is O (k*n) where k is the number of loops around result array and n is the number of people.

The Space complexity of this solution is O(1) since we are using fixed amount of variables.

The run time on Leetcode came out to be high so, next let’s see how we can improve it.

Runtime: 114 ms, faster than 8.27% of Java online submissions for Distribute Candies to People.

Memory Usage: 36.6 MB, less than 100.00% of Java online submissions for Distribute Candies to People.

We made a few changes in this solution compared to Solution 1a: Removed the index variable as it was redundant (can use give_candy -1), removed the if statement at the end that was being used to reset the index variable to zero and used Modulus function to go back to the start of the array.

The Time complexity of this solution is again O(k*n), same as solution 1.

The Space complexity of this solution is also O(1) as before.

The run time has improved significantly on Leetcode, as shown below.

Runtime: 1 ms, faster than 90.44% of Java online submissions for Distribute Candies to People.

Memory Usage: 34 MB, less than 100.00% of Java online submissions for Distribute Candies to People.

If you want to clean the code a bit further, look at the code below.

The Time complexity of this solution is again O(k*n), same as solution 1.

The Space complexity of this solution is also O(1) as before.

The run time is also same on Leetcode.

Runtime: 1 ms, faster than 90.54% of Java online submissions for Distribute Candies to People.

Memory Usage: 33.8 MB, less than 100.00% of Java online submissions for Distribute Candies to People.

We can move one step further in cleaning up the previous code, as shown below.

Changed the while loop to see if candies is greater than 0 and storing candies in result array based on the min value between give_candy and candies.