Problem Statement

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.

Constraints:

• n == ratings.length
• 1 <= n <= 2 * 104
• 0 <= ratings[i] <= 2 * 104

Problem Link

Candy - LeetCode

Reference Video

https://www.youtube.com/watch?v=h6_lIwZYHQw

Code

class Solution {
public:
    int candy(vector<int>& ratings) {
        
        int n = ratings.size();
        
        vector<int> l2r(n,1);
        vector<int> r2l(n,1);
        
        for(int i=1;i<n;i++)
        {
            if(ratings[i]>ratings[i-1])//if the left side rating is less than the current rating
                l2r[i] = 1+l2r[i-1];
            
            
        }
        
        for(int i=n-2;i>=0;i--)
        {
            if(ratings[i]>ratings[i+1])//if the right side rating is more than the current rating
                r2l[i] = 1+r2l[i+1];
            
        }
        
        
        
        int sum = 0;
        
        for(int i=0;i<n;i++)
        {
           
            sum+=max(l2r[i],r2l[i]);
        }
        
        return sum;
        
        
    }
};