Candy LeetCode Solution

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg Flipkart Goldman Sachs Google IBM Infosys Microsoft UberViews 7486

Problem Statement:

Candy LeetCode Solution: 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 neighbours.

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

Examples:

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.

Approach:

Idea:

We will solve the problem with a greedy approach. First, we will be iterating from left to right and will assign candies to a child based on its rating and the number of candies assigned to its previous child i.e., distribution relative to the left neighbours only. Similarly, we will iterate from right to left and will do the assignment based on the rating and the candies assigned to the previous child, i.e., distribution relative to the right neighbours only. Finally, the number of candies assigned to a child will be the maximum of the candies assigned from left to right and from right to left distribution.

So questions says distribute candies between kids in such a way that number of candies should be minimum. Now, what does that mean
We need to distribute candies to every kid in such a way that we will satisfy both of the below conditions but number of candies distributed should be minimum because to satisfy below conditions we can simply distribute 1000 1000 or 1000000 candies to each kid according to their rating, but we want to reduce number of candies as much as possible. So the conditions are:

  1. Each student should get atleast one candy
  2. The kid with higher rating should get more candies than it’s neighbours.

Solution approach

So we are using two loops here, first time we are moving from left to right, second time we are moving right to left. But why? why not only one loop we could have simply checked if rating[currentKid] > rating[currentKid – 1] && rating[currentKid] > rating[currentKid + 1]
This is because okay currentKid have greater rating than his previous and next kid but what if next kid has higher rating than his next kid or previous kid has higher rating than his previous kid ? than looping over array only ones will give wrong answers. That’s why we are looping over array of ratings twice and at a perticular time we are checking only one thing, if currentKid rating > previousKid rating and in 2nd loop we are checking if currentKid rating > nextKid rating.

Code:

Candy C++ Solution:

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> left(n,1);
        vector<int> right(n,1);
        
        for(int i=1;i<n;i++){
            if(ratings[i]>ratings[i-1])
                left[i] = left[i-1]+1;
        }
        for(int i=n-2;i>=0;i--){
            if(ratings[i]>ratings[i+1])
                right[i] = right[i+1]+1;
        }
        int ans=0;
        for(int i=0;i<n;i++)
            ans += max(left[i],right[i]);
        return ans;
    }
};

 

Complexity Analysis of  Candy LeetCode Solution:

Translate »