Candy [Hard/Medium] — Two-Pass Greedy

Problem Statement

n children in a row with ratings. Give each at least 1 candy. Children with higher rating than neighbors get more candies. Return minimum total candies.

Input: [1,0,2] → Output: 5 ([2,1,2])
Input: [1,2,2] → Output: 4 ([1,2,1])

Intuition

Two passes: left→right (right neighbor higher → +1), then right→left (left neighbor higher → max of current and right+1).

Solutions

C++

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);
}

Java

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 sum=0; for(int x:c) sum+=x; return sum;
}

Python

def candy(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]:
            c[i] = max(c[i], c[i+1]+1)
    return sum(c)

Complexity

Time: O(n)
Space: O(n)