135. Candy

Description

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

 

Solutions

Solution: Greedy

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} ratings
 * @return {number}
 */
const candy = function (ratings) {
  const n = ratings.length;
  const allocates = Array.from({ length: n }, () => 1);

  for (let index = 1; index < n; index++) {
    if (ratings[index] > ratings[index - 1]) {
      allocates[index] = allocates[index - 1] + 1;
    }
  }

  for (let index = n - 2; index >= 0; index--) {
    if (ratings[index] <= ratings[index + 1]) continue;
    if (allocates[index] > allocates[index + 1]) continue;

    allocates[index] = allocates[index + 1] + 1;
  }

  return allocates.reduce((result, allocate) => result + allocate);
};