Leetcode Candy problem solution YASH PAL, 31 July 2024 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: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. 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