Candy
Each child gets at least one candy; higher-rated child gets more than smaller-rated neighbors. Minimum candies via two passes.
4 min read
greedy array
Problem#
Each child gets at least 1 candy. A child with a higher rating than an adjacent child must get more candy. Return the minimum total candies.
Examples#
[1,0,2]→5([2,1,2])[1,2,2]→4([1,2,1])
Constraints#
1 <= n <= 2 * 10^4.
Hints#
Hint 1
Two passes: left-to-right enforces “right > left” constraints; right-to-left enforces “left > right”. Take max at each index.
Approach#
Two passes. Initialize all to 1. Left pass: if ratings[i] > ratings[i-1], candy[i] = candy[i-1] + 1. Right pass: if ratings[i] > ratings[i+1], candy[i] = max(candy[i], candy[i+1] + 1).
Solution#
class Solution {public: 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); return accumulate(c.begin(), c.end(), 0); }};func candy(ratings []int) int { n := len(ratings) c := make([]int, n) for i := range c { c[i] = 1 } for i := 1; i < n; i++ { if ratings[i] > ratings[i-1] { c[i] = c[i-1] + 1 } } for i := n - 2; i >= 0; i-- { if ratings[i] > ratings[i+1] && c[i] <= c[i+1] { c[i] = c[i+1] + 1 } } sum := 0 for _, v := range c { sum += v } return sum}from typing import List
class Solution: def candy(self, ratings: List[int]) -> int: 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] and c[i] <= c[i + 1]: c[i] = c[i + 1] + 1 return sum(c)var candy = function(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] <= c[i + 1]) c[i] = c[i + 1] + 1; } let sum = 0; for (const v of c) sum += v; return sum;};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] <= c[i + 1]) c[i] = c[i + 1] + 1; } int sum = 0; for (int v : c) sum += v; return sum; }}function candy(ratings: number[]): number { const n = ratings.length; const c: number[] = 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] <= c[i + 1]) c[i] = c[i + 1] + 1; } let sum = 0; for (const v of c) sum += v; return sum;}Editorial#
Each constraint (“more than left neighbor”, “more than right neighbor”) creates a directional requirement. Two opposite-direction passes satisfy each independently; taking the max at each index satisfies both. Equal ratings impose no constraint, so the runs reset.
Complexity#
- Time: O(n).
- Space: O(n).
Concept revision#
Related#