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:
What is the minimum candies you must give?
Example 1:
Input: [1,0,2] Output: 5 Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
The description was taken from https://leetcode.com/problems/candy/.
#O(N) Time, O(N) Spaceclass Solution: def candy(self, ratings: List[int]) -> int: result = len(ratings) * [1] for i in range(1, len(ratings)): if ratings[i] > ratings[i-1]: result[i] = result[i-1] + 1 for i in (range(len(ratings)-2, -1, -1)): if ratings[i] > ratings[i+1]: result[i] = max(result[i], result[i+1] +1) return sum(result)The problem requires us to return the minimum number of candies we'd need to distribute. When we see that key phrase, that is usually an indication that this will be a greedy problem.
Like other greedy problems, we will need to prioritize tasks. In this case, we will need to prioritize the children who received better ratings over the ones who didn't.
What we can do is make one initial pass from left to right and reward children with higher ratings than children to their left, then one more pass from right to left to do the same thing if the child doesn't already have more candy.
We will start by giving every child one piece of candy. We will do this by initializing our result array to be the length of the input array and give each index the initial value of one.
result = len(ratings) * [1]
Afterward, we will make our initial pass through the array. For each child, we will see if their rating was greater than the child to the left.
for i in range(1, len(ratings)): if ratings[i] > ratings[i-1]:
If it is, we will give the current child what the child to the left has, plus one.
result[i] = result[i-1] + 1
After we moved down the line of children in the classroom, we will start from the end and go back to the beginning.
for i in (range(len(ratings)-2, -1, -1)):
While we are moving back down the line, if we see a child with higher ratings than the child to its right, we need to keep in mind that it is possible the current child already has more candy than the child to its right.
To make sure we don't take any candy away from deserving children, we will see if the amount we were about to give them to go home with would be less than what they already have.
We will do this by taking the maximum of what the child already has and the amount the child to the right has.
if ratings[i] > ratings[i+1]: result[i] = max(result[i], result[i+1] +1)
After we have given out all of our candy, we will return the total candy given. This way, we can report our losses to the principal.
return sum(result)