Back to DSA
Candy
hardChildren stand in a line, each with a rating score. Distribute candies so that every child gets at least one and any child with a higher rating than an immediate neighbor receives more candies than that neighbor. Compute the minimum total candies required.
Examples
Example 1:
Input:
ratings = [1,3,2]Output:
4 Example 2:
Input:
ratings = [1,2,2]Output:
4Hints
class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] candies = new int[n];
java.util.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 sum = 0;
for (int c : candies) sum += c;
return sum;
}
}Time complexity
O(n)Space complexity
O(n)