Algorithm

Problem Name: 135. Candy

problem Link: https://leetcode.com/problems/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 & Try With Live Editor

Input

x
–
+
cmd
ratings = [1,0,2]

Output

x
–
+
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];
    }
    return totalCandies;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
ratings = [1,0,2]

Output

x
–
+
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 & Try With Live Editor

Input

x
–
+
cmd
ratings = [1,2,2]

Output

x
–
+
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 & Try With Live Editor

Input

x
–
+
cmd
ratings = [1,2,2]

Output

x
–
+
cmd
4
Advertisements

Demonstration

Previous
#134 Leetcode Gas Station Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#136 Leetcode Single Number Solution in C, C++, Java, JavaScript, Python, C# Leetcode