Leetcode 135. Candy
Problem Explanation:
There are N
number of children standing in line. A rating is assigned to each child. The task here is that we have to distribute candies to these children according to the following rules:
- Each child must get at least one candy.
- Children with a higher rating get more candies than their neighboring child.
You objective is giving out the minimum amount of candies that you can.
For instance, let's take an example:
Example:
Input: [1,0,2]
- Here, we have 3 children having ratings [1,0,2]
- Since all must be given at least one candy, let's distribute one candy each to all three. [1,1,1]
- Now we have child with rating 0 that has the same amount of candy as the child to its right (with a rating of 2), which is not correct. So, we add one more candy to the third child, making the distribution [1,1,2]
- At this point, we effectively have higher rating child having more candies than its lower rating neighbour
Output: 1+1+2=4
Solution Explanation:
We use a very straightforward greedy approach to solve the problem. This involves going from left to right and then from right to left using two seperate loops.
We initally create two arrays for maintaining the amount of candy, one for moving left to right and the other from moving right to left.
Then we move from left to right, and if a child has higher rating than the the previous, then we update the candy count in the left to right array as one more than previous.
Next step is to move from right to left and update candy count in a similar manner.
Finally, we iterate over the two arrays and for each index choose the maximum candy count from left to right and right to left arrays since we have calculated them independently.
C++ Solution:
1 2c++ 3class Solution { 4 public: 5 int candy(vector<int>& ratings) { 6 const int n = ratings.size(); 7 int ans = 0; 8 vector<int> l(n, 1); 9 vector<int> r(n, 1); 10 11 // move from left to right 12 for (int i = 1; i < n; ++i) 13 if (ratings[i] > ratings[i - 1]) 14 l[i] = l[i - 1] + 1; 15 16 // move from right to left 17 for (int i = n - 2; i >= 0; --i) 18 if (ratings[i] > ratings[i + 1]) 19 r[i] = r[i + 1] + 1; 20 21 // choose the maximum candy count from l and r 22 for (int i = 0; i < n; ++i) 23 ans += max(l[i], r[i]); 24 25 return ans; 26 } 27};
Python Solution:
1 2python 3class Solution: 4 def candy(self, ratings: List[int]) -> int: 5 n = len(ratings) 6 l = [1]*n 7 r = [1]*n 8 ans = 0 9 10 # move from left to right 11 for i in range(1, n): 12 if ratings[i] > ratings[i - 1]: 13 l[i] = l[i - 1] + 1 14 15 # move from right to left 16 for i in range(n - 2, -1, -1): 17 if ratings[i] > ratings[i + 1]: 18 r[i] = r[i + 1] + 1 19 20 # choose the maximum candy count from l and r 21 for i in range(n): 22 ans += max(l[i], r[i]) 23 24 return ans
Java Solution:
1 2java 3class Solution { 4 public int candy(int[] ratings) { 5 int n = ratings.length; 6 int[] left = new int[n]; 7 int[] right = new int[n]; 8 9 Arrays.fill(left, 1); 10 Arrays.fill(right, 1); 11 12 for (int i = 1; i < n; i++) 13 if (ratings[i] > ratings[i - 1]) 14 left[i] = left[i - 1] + 1; 15 16 for (int i = n - 2; i >= 0; i--) 17 if (ratings[i] > ratings[i + 1]) 18 right[i] = right[i + 1] + 1; 19 20 int ans = 0; 21 22 for (int i = 0; i < n; i++) 23 ans += Math.max(left[i], right[i]); 24 25 return ans; 26 } 27};
JavaScript Solution:
1 2javascript 3var candy = function(ratings) { 4 let n = ratings.length; 5 let left = new Array(n).fill(1); 6 let right = new Array(n).fill(1); 7 let ans = 0; 8 9 for(let i = 1; i < n; i++) { 10 if (ratings[i] > ratings[i - 1]) { 11 left[i] = left[i-1] + 1; 12 } 13 } 14 15 for(let i = n-2; i >= 0; i--) { 16 if (ratings[i] > ratings[i + 1]) { 17 right[i] = right[i+1] + 1; 18 } 19 } 20 21 for(let i = 0; i< n; i++) { 22 ans += Math.max(left[i], right[i]); 23 } 24 25 return ans; 26};
C# Solution:
1 2csharp 3public class Solution { 4 public int Candy(int[] ratings) { 5 int n = ratings.Length; 6 int[] left = new int[n]; 7 int[] right = new int[n]; 8 int candy = 0; 9 10 for (int i = 0; i < n; i++) { 11 left[i] = 1; 12 right[i] = 1; 13 } 14 15 for (int i = 1; i < n; i++) { 16 if (ratings[i] > ratings[i - 1]) 17 left[i] = left[i - 1] + 1; 18 } 19 20 for (int i = n - 2; i >= 0; i--) { 21 if (ratings[i] > ratings[i + 1]) 22 right[i] = right[i + 1] + 1; 23 } 24 25 for (int i = 0; i < n; i++) { 26 candy += Math.Max(left[i], right[i]); 27 } 28 29 return candy; 30 } 31}
This problem is solved using a greedy approach. The main idea behind the algorithm is that each child should be given at least one candy and children with a higher rating get more candies than their neighboring child.
The algorithm is implemented in Python, Javascript, Java, C++, and C#. It uses two loops, one travelling from left to right and the other one from right to left, ensuring that each child having higher rating than the neighboring child gets more candy.
It is implemented in the following manner:
- Initialize two lists (arrays) left and right both of size equal to the number of children, each being assigned a minimum of 1 candy.
- Iterate left to right on the ratings, if the current child's rating is higher than the previous child then assign one more candy than the previous child to the current child in the left array.
- Similarly, repeat the iteration from right to left applying the same rule and update the right array.
- Now, you have number of candies calculated from both directions independently. Finally, to get the minimum candies, you need to take maximum of the candies calculated from left or right at each child.
- Add all the candies to get the minimum total candies required.
This greedy approach ensures that the minimum total candy is distributed such that the child with higher rating gets more candy than its neighbor.
Although this problem has a very straight forward solution through a greedy approach, it is always recommended to understand and analyze the problem before rushing to the solution.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.