Leetcode Candy problem solution

YASH PAL,

In this Leetcode Candy problem 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:

  1. Each child must have at least one candy.
  2. 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.

Leetcode Candy problem solution

Problem solution in Python.

from itertools import *
  
class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        dp = [1] * n
        
        for i in range(1, n):
            if ratings[i] > ratings[i - 1] and dp[i] <= dp[i - 1]:
                dp[i] = dp[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1] and dp[i] <= dp[i + 1]:
                dp[i] = dp[i + 1] + 1

        return sum(dp)

Problem solution in Java.

class Solution {
        public int candy(int[] nums) {
            
            int ans = 0;
            int n = nums.length;
            int[] candy = new int[n];
            
            for(int i=nums.length-1;i>0;i--){
                if(nums[i-1]>nums[i]){
                    candy[i-1] = candy[i]+1;
                }
            }
            
            for(int i=0;i<nums.length-1;i++)
            {
                if(nums[i]<nums[i+1] && candy[i]>=candy[i+1])
                {
                    candy[i+1] = candy[i]+1;
                }
                ans+=candy[i];
            }
            
            return n+ans+candy[n-1];
        }
}

Problem solution in C++.

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

Problem solution in C.

int data[100000];
int *ratings;
int n;

int fun(int p){
    if(data[p]) return data[p];
    data[p] = -0x7fffffff;
    if(!p){
        if(ratings[p] > ratings[p+1])
            return fun(p+1)+1;
        else
            return data[p] = 1;
    }
    if(p == n-1){
        if(ratings[p] > ratings[p-1])
            return fun(p-1)+1;
        else
            return data[p] = 1;
    }
    if(ratings[p-1] >= ratings[p] && ratings[p+1] >= ratings[p]){
        return data[p] = 1;
    }else if(ratings[p-1] < ratings[p] && ratings[p+1] < ratings[p]){
        int va = fun(p-1);
        int vb = fun(p+1);
        return data[p] = (va>vb?va:vb)+1;
    }else if(ratings[p-1] < ratings[p] && ratings[p+1] >= ratings[p]){
        return data[p] = fun(p-1)+1;
    }else if(ratings[p-1] >= ratings[p] && ratings[p+1] < ratings[p]){
        return data[p] = fun(p+1)+1;
    }
    return data[p];
}

int candy(int rating[], int len) {
    ratings = rating;
    memset(data,0,len*sizeof(int));
    n = len;
    int sum = 0;
    for(int i = 0;i < n;i ++)
        sum += fun(i);
    return sum;
}

coding problems solutions