Leetcode•Jul 08, 2025

Candy

Hazrat Ali

Leetcode

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.

Solution
/**
 * @param {number[]} ratings
 * @return {number}
 */
const candy = ratings => {
  if (!ratings || ratings.length === 0) return 0;

  const n = ratings.length;

 
  const arr = Array(n).fill(0);
  arr[0] = 1;

 
  for (let i = 1; i < n; i++) {
    arr[i] = ratings[i] > ratings[i - 1] ? arr[i - 1] + 1 : 1;
  }

 
  let sum = arr[n - 1];

  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) {
      arr[i] = Math.max(arr[i], arr[i + 1] + 1);
    }

    sum += arr[i];
  }

  return sum;
};


Comments