EASY 0(N) SOLUTION
PLEASE UPVOTE MY SOLUTION IG YOU LIKE IT\n# CONNECT WITH ME\n### https://www.linkedin.com/in/pratay-nandy-9ba57b229/\n### https://www.instagram.com/pratay_nandy
# **PLEASE UPVOTE MY SOLUTION IG YOU LIKE IT**\n# **CONNECT WITH ME**\n### **[https://www.linkedin.com/in/pratay-nandy-9ba57b229/]()**\n### **[https://www.instagram.com/pratay_nandy/]()**\n# Problem Statement\n- The problem statement is as follows: You are given a list of ratings for a group of children, and you want to distribute candies to these children based on the following rules:\n\n1. Each child must have at least one candy.\n2. Children with a higher rating than their neighbors must get more candies.\n- The goal is to minimize the total number of candies used while satisfying these rules\n# Approach\n\nHere\'s the approach used in the provided C++ code:\n\n- Initialize a vector left with the same size as the input ratings vector. This vector will store the number of candies given to each child based on the ratings from the left side.\n\n- First Pass (from left to right):\n\n- Iterate through the ratings vector from left to right (from index 1 to the end).\nIf the current child\'s rating is greater than the previous child\'s rating, increment the number of candies given to the current child by one more than what the previous child received (i.e., left[i] = left[i-1] + 1).Otherwise, leave left[i] as 1 because the current child\'s rating is not greater than the previous one.\nInitialize a variable right to 1. This variable will be used to keep track of the number of candies given to the children from the right side.\n\n- Second Pass (from right to left):\n\n- Iterate through the ratings vector from right to left (from the second-to-last element to the first element).\nIf the current child\'s rating is greater than the next child\'s rating, increment right by 1 (since this child needs more candies than the next one).\n- Update left[i] by taking the maximum of its current value and right (to ensure that the child gets the maximum of what they need from both sides).\n- If the current child\'s rating is not greater than the next one, reset right to 1, indicating that this child starts a new descending sequence.\n- Calculate the total sum of candies in the left vector, which represents the minimum total number of candies needed to satisfy the given rules.\n\n- Return the total sum as the result.\n\nThis approach ensures that each child receives the required minimum number of candies while taking into account both left and right ratings comparisons. The final result is the minimum total number of candies needed to satisfy the rulesThe problem statement is as follows: You are given a list of ratings for a group of children, and you want to distribute candies to these children based on the following rules:\n\n# Complexity\n- Time complexity:**0(N)**\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:**0(N)**\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        vector<int>left(ratings.size()+1,1);\n        // vector<int>right(ratings.size()+1,1);\n        for(int i = 1; i < ratings.size(); i++ )\n        {\n            if(ratings[i]>ratings[i-1])\n            {\n                left[i]=left[i-1]+1;\n            }\n        }\n        int right = 1;\n        for(int i = ratings.size()-2;i>=0;i--)\n        {\n            if(ratings[i] > ratings[i+1])\n            {\n                right++;\n                left[i]=max(right, left[i]);\n            }\n            else\n            right = 1;\n        }\n        int sum = 0 ;\n        for(int i = 0; i < ratings.size(); i++ )\n            sum+=left[i];\n        return sum;\n    }\n};\n```
['Array', 'C++']