Minimum Candies for Children's Ratings
Problem
Children stand in a line, each with a rating. Hand out candies so every child gets at least one, and any child with a strictly higher rating than a neighbour gets strictly more candies than that neighbour. Minimise the total. The clean fix: two sweeps. The left-to-right pass enforces "higher than left neighbour gets more than left neighbour." The right-to-left pass enforces "higher than right neighbour gets more than right neighbour" — taking the max of the two passes per child satisfies both at once.
Input
ratings = [1, 0, 2]Output
5Candies become [2, 1, 2]. Total = 5.
def candy(ratings):
n = len(ratings)
c = [1] * n
for i in range(1, n):
if ratings[i] > ratings[i - 1]:
c[i] = c[i - 1] + 1
for i in range(n - 2, -1, -1):
if ratings[i] > ratings[i + 1]:
c[i] = max(c[i], c[i + 1] + 1)
return sum(c)function candy(ratings) {
const n = ratings.length;
const c = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
}
for (let i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
}
return c.reduce((s, x) => s + x, 0);
}class Solution {
public int candy(int[] ratings) {
int n = ratings.length;
int[] c = new int[n];
Arrays.fill(c, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
}
int total = 0;
for (int x : c) total += x;
return total;
}
}int candy(vector<int>& ratings) {
int n = ratings.size();
vector<int> c(n, 1);
for (int i = 1; i < n; i++) {
if (ratings[i] > ratings[i - 1]) c[i] = c[i - 1] + 1;
}
for (int i = n - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) c[i] = max(c[i], c[i + 1] + 1);
}
int total = 0;
for (int x : c) total += x;
return total;
}