Hard Difficulty
Candy

Array

Greedy

hard

## Candy

To solve the problem, we can use a greedy approach. We'll iterate over the ratings twice: once from left to right and then from right to left. In each iteration, we'll update the number of candies for each child based on their rating and their neighbors' ratings.

Here's the JavaScript code to implement this solution:

``````function distributeCandies(ratings) {
const n = ratings.length;
const candies = Array(n).fill(1); // Each child must have at least one candy

// Traverse from left to right
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}

// Traverse from right to left
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}

// Calculate the total number of candies
let totalCandies = 0;
for (let i = 0; i < n; i++) {
totalCandies += candies[i];
}

The time complexity of this solution is O(n), where n is the number of children (length of the `ratings` array). This is because we traverse the array twice, once from left to right and once from right to left, each in linear time.
The space complexity is O(n) as well. We use an additional `candies` array of size n to store the number of candies assigned to each child.