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];
  }
 
  return totalCandies;
}

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.