## 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 &

Input

cmd
ratings = [1,0,2]

Output

cmd
5

### #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];
}
}
}
``````
Copy The Code &

Input

cmd
ratings = [1,0,2]

Output

cmd
5

### #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 &

Input

cmd
ratings = [1,2,2]

Output

cmd
4

### #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 &

Input

cmd
ratings = [1,2,2]

Output

cmd
4