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.
Examples:
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 in Python
To solve the problem of distributing candies based on the ratings, we can use a two-pass greedy algorithm. The idea is to ensure that each child gets more candies than their neighbors if they have a higher rating, while also ensuring that each child gets at least one candy.
Approach:
- Initialize Candies Array: Create an array
candiesof the same length asratings, initialized with 1 candy for each child because each child must have at least one candy. - Left-to-Right Pass: Traverse the
ratingsarray from left to right. For each child, if the current child’s rating is higher than the previous child’s rating, increment the current child’s candy count to be one more than the previous child’s candy count. - Right-to-Left Pass: Traverse the
ratingsarray from right to left. For each child, if the current child’s rating is higher than the next child’s rating, update the current child’s candy count to be the maximum of the current candy count and one more than the next child’s candy count. - Sum Up Candies: Sum all the values in the
candiesarray to get the minimum number of candies required.
Python
from typing import List
class Solution:
def candy(self, ratings: List[int]) -> int:
n = len(ratings)
if n == 0:
return 0
# Step 1: Initialize candies array with 1 candy for each child
candies = [1] * n
# Step 2: Left-to-right pass
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
candies[i] = candies[i - 1] + 1
# Step 3: Right-to-left pass
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
candies[i] = max(candies[i], candies[i + 1] + 1)
# Step 4: Sum up the candies
return sum(candies)Explanation:
- Initialization: We start by initializing the
candiesarray with all elements set to 1, as every child must have at least one candy. - Left-to-Right Pass:
- For each child from the second to the last, we check if their rating is greater than the previous child’s rating.
- If so, we give the current child one more candy than the previous child.
- Right-to-Left Pass:
- For each child from the second to the last (moving backwards), we check if their rating is greater than the next child’s rating.
- If so, we update the current child’s candy count to be the maximum of its current candy count or one more than the next child’s candy count. This ensures that we maintain the property from both directions.
- Sum Up Candies: Finally, we sum up all the values in the
candiesarray to get the total number of candies required.
This algorithm ensures that both constraints are met efficiently, with a time complexity of O(n) and a space complexity of O(n).
Solution in Javascript
JavaScript
/**
* @param {number[]} ratings
* @return {number}
*/
var candy = function(ratings) {
const n = ratings.length;
if (n === 0) return 0;
// Step 1: Initialize candies array with 1 candy for each child
const candies = new Array(n).fill(1);
// Step 2: Left-to-right pass
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Step 3: Right-to-left pass
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// Step 4: Sum up the candies
return candies.reduce((a, b) => a + b, 0);
};Solution in Java
Java
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
if (n == 0) return 0;
// Step 1: Initialize candies array with 1 candy for each child
int[] candies = new int[n];
for (int i = 0; i < n; i++) {
candies[i] = 1;
}
// Step 2: Left-to-right pass
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Step 3: Right-to-left pass
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.max(candies[i], candies[i + 1] + 1);
}
}
// Step 4: Sum up the candies
int totalCandies = 0;
for (int candy : candies) {
totalCandies += candy;
}
return totalCandies;
}
}Solution in C#
C#
public class Solution {
public int Candy(int[] ratings) {
int n = ratings.Length;
if (n == 0) return 0;
// Step 1: Initialize candies array with 1 candy for each child
int[] candies = new int[n];
for (int i = 0; i < n; i++) {
candies[i] = 1;
}
// Step 2: Left-to-right pass
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
// Step 3: Right-to-left pass
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candies[i] = Math.Max(candies[i], candies[i + 1] + 1);
}
}
// Step 4: Sum up the candies
int totalCandies = 0;
for (int i = 0; i < n; i++) {
totalCandies += candies[i];
}
return totalCandies;
}
}