There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
- Each child must have at least one candy.
- Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?
The simplest approach makes use of a 1-d array, to keep a track of the candies given to the students. Firstly, we give 1 candy to each student. Then, we start scanning the array from left-to-right. At every element encountered, firstly, if the current element's ratings, , is larger than the previous element() and , then we update as .Thus, now the candy distribution for these two elements and becomes correct for the time being(locally). In the same step, we also check if the current element's ratings, , is larger than the next element's ratings, i.e. . If so, we again update . We continue this process for the whole array. If in any traversal, no updation of the array occurs, it means we've reached at the final required distribution of the candies and we can stop the traversals. To keep a track of this we make use of a which is set to if any updation occurs in a traversal.
At the end, we can sum up all the elements of the array to obtain the required minimum number of candies.
Java
public class Solution { public int candy(int[] ratings) { int[] candies = new int[ratings.length]; Arrays.fill(candies, 1); boolean flag = true; int sum = 0; while (flag) { flag = false; for (int i = 0; i < ratings.length; i++) { if (i != ratings.length - 1 && ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) { candies[i] = candies[i + 1] + 1; flag = true; } if (i > 0 && ratings[i] > ratings[i - 1] && candies[i] <= candies[i - 1]) { candies[i] = candies[i - 1] + 1; flag = true; } } } for (int candy : candies) { sum += candy; } return sum; } }
Complexity Analysis
Algorithm
In this approach, we make use of two 1-d arrays and . The array is used to store the number of candies required by the current student taking care of the distribution relative to the left neighbours only. i.e. Assuming the distribution rule is: The student with a higher ratings than its left neighbour should always get more candies than its left neighbour. Similarly, the array is used to store the number of candies candies required by the current student taking care of the distribution relative to the right neighbours only. i.e. Assuming the distribution rule to be: The student with a higher ratings than its right neighbour should always get more candies than its right neighbour. To do so, firstly we assign 1 candy to each student in both and array. Then, we traverse the array from left-to-right and whenever the current element's ratings is larger than the left neighbour we update the current element's candies in the array as , since the current element's candies are always less than or equal candies than its left neighbour before updation. After the forward traversal, we traverse the array from left-to-right and update as , whenever the current() element has a higher ratings than the right() element.
Now, for the student in the array, we need to give to it, in order to satisfy both the left and the right neighbour relationship. Thus, at the end, we obtain the minimum number of candies required as:
The following animation illustrates the method:
Java
public class Solution { public int candy(int[] ratings) { int sum = 0; int[] left2right = new int[ratings.length]; int[] right2left = new int[ratings.length]; Arrays.fill(left2right, 1); Arrays.fill(right2left, 1); for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { left2right[i] = left2right[i - 1] + 1; } } for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { right2left[i] = right2left[i + 1] + 1; } } for (int i = 0; i < ratings.length; i++) { sum += Math.max(left2right[i], right2left[i]); } return sum; } }
Complexity Analysis
Time complexity : . and arrays are traversed thrice.
Space complexity : . Two arrays and of size are used.
Algorithm
In the previous approach, we used two arrays to keep track of the left neighbour and the right neighbour relation individually and later on combined these two. Instead of this, we can make use of a single array to keep the count of the number of candies to be allocated to the current student. In order to do so, firstly we assign 1 candy to each student. Then, we traverse the array from left-to-right and distribute the candies following only the left neighbour relation i.e. whenever the current element's ratings is larger than the left neighbour and has less than or equal candies than its left neighbour, we update the current element's candies in the array as . While updating we need not compare and , since before updation. After this, we traverse the array from right-to-left. Now, we need to update the element's candies in order to satisfy both the left neighbour and the right neighbour relation. Now, during the backward traversal, if , considering only the right neighbour criteria, we could've updated as . But, this time we need to update the only if . This happens because, this time we've already altered the array during the forward traversal and thus isn't necessarily less than or equal to . Thus, if , we can update as , which makes satisfy both the left neighbour and the right neighbour criteria.
Again, we need sum up all the elements of the array to obtain the required result.
java
public class Solution { public int candy(int[] ratings) { int[] candies = new int[ratings.length]; Arrays.fill(candies, 1); for (int i = 1; i < ratings.length; i++) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] + 1; } } int sum = candies[ratings.length - 1]; for (int i = ratings.length - 2; i >= 0; i--) { if (ratings[i] > ratings[i + 1]) { candies[i] = Math.max(candies[i], candies[i + 1] + 1); } sum += candies[i]; } return sum; } }
Complexity Analysis
Time complexity : . The array of size is traversed thrice.
Space complexity : . An array of size is used.
Algorithm
This approach relies on the observation(as demonstrated in the figure below as well) that in order to distribute the candies as per the given criteria using the minimum number of candies, the candies are always distributed in terms of increments of 1. Further, while distributing the candies, the local minimum number of candies given to a student is 1. Thus, the sub-distributions always take the form: or , whose sum is simply given by .
Now, we can view the given as some rising and falling slopes. Whenever the slope is rising, the distribution takes the form: . Similarly, a falling slope takes the form: . An issue that arises now is that the local peak point can be included in only one of the slopes. Whether to include the local peak point() in the rising slope or the falling slope?
In order to decide it, we can observe that in order to satisfy both the right neighbour and the left neighbour criteria, the peak point's count needs to be the max. of the counts determined by the rising and the falling slopes. Thus, in order to determine the number of candies required, the peak point needs to be included in the slope which contains more number of points. The local valley point can also be included in only one of the slopes, but this issue can be resolved easily, since the local valley point will always be assigned a candy count of 1(which can be subtracted from the next slope's count calculations).
Coming to the implementation, we maintain two variables and to determine the occurence of a peak or a valley. We also use and variables to keep a track of the count of elements on the rising slope and on the falling slope respectively(without including the peak element). We always update the total count of at the end of a falling slope following a rising slope (or a mountain). The leveling of the points in also works as the end of a mountain. At the end of the mountain, we determine whether to include the peak point in the rising slope or in the falling slope by comparing the and variables up to that point. Thus, the count assigned to the peak element becomes: . At this point, we can reset the and variables indicating the start of a new mountain.
The following figure shows the cases that need to be handled for this example:
rankings: [1 2 3 4 5 3 2 1 2 6 5 4 3 3 2 1 1 3 3 3 4 2]
From this figure, we can see that the candy distributions in the subregions always take the form or . For the first mountain comprised by the regions and , while assigning candies to the local peak point(), it needs to be included in to satisfy the left neighbour criteria. The local valley point at the end of region () marks the end of the first mountain(region ). While performing the calculations, we can include this point in either the current or the following mountain. The marks the end of the second mountain due to levelling of the and . Since, region has more points than region , the local peak() needs to be included in region to satisfy the right neighbour criteria. Now, the third mountain can be considered as a mountian with no rising slope() but only a falling slope. Similarly, also act as the mountain ends due to the levelling of the points.
java
public class Solution { public int count(int n) { return (n * (n + 1)) / 2; } public int candy(int[] ratings) { if (ratings.length <= 1) { return ratings.length; } int candies = 0; int up = 0; int down = 0; int old_slope = 0; for (int i = 1; i < ratings.length; i++) { int new_slope = (ratings[i] > ratings[i - 1]) ? 1 : (ratings[i] < ratings[i - 1] ? -1 : 0); if ((old_slope > 0 && new_slope == 0) || (old_slope < 0 && new_slope >= 0)) { candies += count(up) + count(down) + Math.max(up, down); up = 0; down = 0; } if (new_slope > 0) up++; if (new_slope < 0) down++; if (new_slope == 0) candies++; old_slope = new_slope; } candies += count(up) + count(down) + Math.max(up, down) + 1; return candies; } };
Complexity Analysis
Time complexity : . We traverse the array once only.
Space complexity : . Constant Extra Space is used.
Analysis written by: @vinod23