135. Candy

Time: O(n)

Space: O(n)

Intuition

Two greedy passes: left-to-right ensures a child with higher rating than its left neighbour gets more candy. Right-to-left ensures a child with higher rating than its right neighbour gets more candy. Take the max at each position.

Algorithm

1Initialise candies[i] = 1 for all i.
2Left pass: for i from 1 to n-1: if ratings[i] > ratings[i-1], candies[i] = candies[i-1]+1.
3Right pass: for i from n-2 down to 0: if ratings[i] > ratings[i+1], candies[i] = max(candies[i], candies[i+1]+1).
4Return sum(candies).

Example Walkthrough

Input: ratings = [1,0,2]

1.Init: [1,1,1]. Left pass: ratings[2]=2>0 -> candies[2]=2. -> [1,1,2].
2.Right pass: ratings[0]=1>0 -> candies[0]=max(1,1+1)=2. -> [2,1,2].
3.Sum=5.

Output: 5

Common Pitfalls

•The right pass must take max(candies[i], candies[i+1]+1) - do not blindly overwrite the left-pass value.

135.cs

// Approach: Greedy with two passes to independently satisfy left-neighbor and right-neighbor constraints.
// Initialise every child with 1 candy (the minimum allowed).
// Left-to-right pass: if ratings[i] > ratings[i-1], set candies[i] = candies[i-1] + 1.
// Right-to-left pass: if ratings[i] > ratings[i+1], set candies[i] = max(candies[i], candies[i+1] + 1).
// Taking the max in the right-to-left pass ensures both constraints are satisfied simultaneously.
// Summing all values gives the minimum total candy required.
// Time: O(n) Space: O(n) for the candy array.

public class Solution
{
    public int Candy(int[] ratings)
    {
        int n = ratings.Length;

        int ans = 0;
        int[] l = new int[n];
        int[] r = new int[n];
        Array.Fill(l, 1);
        Array.Fill(r, 1);

        for (int i = 1; i < n; ++i)
        {
            if (ratings[i] > ratings[i - 1])
                l[i] = l[i - 1] + 1;
        }

        for (int i = n - 2; i >= 0; --i)
        {
            if (ratings[i] > ratings[i + 1])
                r[i] = r[i + 1] + 1;
        }

        for (int i = 0; i < n; ++i)
            ans += Math.Max(l[i], r[i]);

        return ans;
    }
}

Was this solution helpful?