🔥 Easy C++ Solution using Prefix and Suffix Vectors 🔥
\n# Approach\n Describe your approach to solving the problem. \n1. Initialize two arrays pref and suff with the same size as the ratings array, all set to 1. Th
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize two arrays `pref` and `suff` with the same size as the ratings array, all set to 1. This ensures that each child starts with at least `one` candy.\n\n2. Loop through the ratings array from left to right. For each child, compare their rating with the rating of the previous child (if any). If the current child\'s rating is greater than the previous child\'s rating, increment the number of candies given to the current child by 1 more than what the previous child received `(pref[i] = 1 + pref[i-1])`.\n\n3. Loop through the ratings array from right to left. For each child, compare their rating with the rating of the next child (if any). If the current child\'s rating is greater than the next child\'s rating, update the number of candies given to the current child by taking the maximum of its current value and 1 plus what the next child received `(suff[i] = max(suff[i], 1 + suff[i+1]))`.\n\n4. Initialize a variable `ans` to keep track of the total number of candies needed.\n\n5. Loop through the ratings array one more time, and for each child, calculate the maximum number of candies they should receive by taking the maximum of the values in `pref` and `suff` for that child. Add this maximum value to `ans`.\n\n6. Return `ans`, which represents the` total minimum number of candies required to satisfy the conditions`.\n# Complexity\n- Time complexity: $$O(n)$$\n We traverse the ratings array three times independently, and each traversal takes `linear time`.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n We use two additional arrays `pref` and `suff`, each of size `n`, for storing intermediate results.\n# Code\n```\nclass Solution {\npublic:\n  int candy(vector<int>& ratings) {\n        int n = ratings.size();\n        vector<int>pref(n , 1);\n        vector<int>suff(n , 1);\n        for(int i = 1;i<n; i++){\n            if(ratings[i]>ratings[i-1]) pref[i] = 1 + pref[i-1];\n        }\n        for(int i = n-2;i>=0; i--){\n            if(ratings[i]>ratings[i+1]) suff[i] = 1 + suff[i+1];\n        }\n\n        int ans = 0; \n        for(int i=0;i<n; i++) ans += max(pref[i] , suff[i]);\n        return ans;\n    }\n};\n```
['Array', 'Greedy', 'C++']