Last updated on March 2nd, 2025 at 02:27 pm
Here, we see a Candy LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Greedy
Level of Question
Hard
Candy LeetCode Solution
Table of Contents
1. Problem Statement
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.
2. Coding Pattern Used in Solution
The coding pattern used in all the provided implementations is Greedy Algorithm. The problem involves distributing candies to children based on their ratings, ensuring that:
- Each child gets at least one candy.
- Children with higher ratings get more candies than their neighbors.
The solution uses a greedy approach by iterating through the ratings array twice (once from left to right and once from right to left) to ensure the conditions are met.
3. Code Implementation in Different Languages
3.1 Candy C++
class Solution {
public:
int candy(vector<int>& ratings) {
int n = ratings.size();
int candy = n, i=1;
while(i<n){
if(ratings[i] == ratings[i-1]){
i++;
continue;
}
int peak = 0;
while(ratings[i] > ratings [i-1]){
peak++;
candy += peak;
i++;
if(i == n) return candy;
}
int valley = 0;
while(i<n && ratings[i] < ratings[i-1]){
valley++;
candy += valley;
i++;
}
candy -= min(peak, valley); //Keep only the higher peak
}
return candy;
}
};
3.2 Candy Java
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
}
3.3 Candy JavaScript
var candy = function(ratings) {
const n = ratings.length;
const candies = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
return candies.reduce((a, b) => a + b, 0);
};
3.4 Candy Python
class Solution(object):
def candy(self, ratings):
n = len(ratings)
candies = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i-1]:
candies[i] = candies[i-1] + 1
for i in range(n-2, -1, -1):
if ratings[i] > ratings[i+1]:
candies[i] = max(candies[i], candies[i+1] + 1)
return sum(candies)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n) | O(1) |
| Java | O(n) | O(n) |
| JavaScript | O(n) | O(n) |
| Python | O(n) | O(n) |