Algorithm
Problem Name: 135. Candy
There are n
children standing in a line. Each child is assigned a rating value given in the integer array ratings
.
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.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [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: ratings = [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.
Constraints:
n == ratings.length
1 <= n <= 2 * 104
0 <= ratings[i] <= 2 * 104
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int candy(int* ratings, int ratingsSize) {
int *candies;
int i, x;
if (ratingsSize < 2) return ratingsSize;
candies = malloc(ratingsSize * sizeof(int));
//assert(candies);
candies[0] = 1;
for (i = 1; i < ratingsSize; i ++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
} else {
candies[i] = 1;
}
}
x = candies[ratingsSize - 1];
for (i = ratingsSize - 2; i >= 0; i --) {
if (ratings[i] > ratings[i + 1]) {
if (candies[i] < = candies[i + 1]) {
candies[i] = candies[i + 1] + 1;
}
}
x += candies[i];
}
free(candies);
return x;
}
Copy The Code &
Try With Live Editor
Input
Output
#2 Code Example with Java Programming
Code -
Java Programming
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 totalCandies = candies[candies.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);
}
totalCandies += candies[i];
}
return totalCandies;
}
}
Copy The Code &
Try With Live Editor
Input
Output
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const candy = function(ratings) {
const candies = new Array(ratings.length).fill(1);
for (let i = 1; i < candies.length; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
let sum = candies[candies.length - 1];
for (let i = candies.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;
};
Copy The Code &
Try With Live Editor
Input
Output
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def candy(self, ratings):
dp = [1] * len(ratings)
for i in range(1, len(ratings)):
if ratings[i] > ratings[i - 1]:
dp[i] = dp[i - 1] + 1
for i in range(len(ratings) - 2, -1, -1):
if ratings[i] > ratings[i + 1] and dp[i] <= dp[i + 1]:
dp[i] = dp[i + 1] + 1
return sum(dp)
Copy The Code &
Try With Live Editor
Input
Output