Fully explained C++ solution || Clean code || Beats 95 % of solutions || Easy to understand
Intuition\nTo maintain the given rule, the solution uses a two-pass approach:\n\n- First Pass (Forward Traversal):\n\nIn the first pass, the code iterates throu
# Intuition\nTo maintain the given rule, the solution uses a two-pass approach:\n\n- **First Pass (Forward Traversal):**\n\nIn the first pass, the code iterates through the ratings from left to right. For each child, it checks if the child to the right has a higher rating. If so, it gives the current child one more candy than the child to the left. This step ensures that children with higher ratings receive more candies than their lower-rated neighbours.\n\n- **Second Pass (Backward Traversal):**\n\nIn the second pass, the code iterates through the ratings from right to left. For each child, it checks if the child to the left has a higher rating and ***hasn\'t received more candies already*** (this is to prevent over-candying). If both conditions are met, it gives the left child more candy than the rigth child.\n\nBy performing these two passes, the solution guarantees that both conditions are met while minimizing the total number of candies distributed. The key insight is that you can start with an initial distribution of one candy per child and adjust it as needed based on the ratings and neighboring children. This approach ensures fairness and satisfies the problem constraints efficiently.\n\nIn summary, the intuition of this solution is to iteratively adjust the number of candies given to each child based on their ratings and the ratings of their neighbors, ensuring that the conditions of the problem are met while minimizing the total number of candies distributed. It\'s a greedy approach that works by making local decisions to achieve a globally optimal solution.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\nHere\'s how the code works:\n\nIt first initializes a vector called \'candy\' with the same length as the input \'ratings\' vector, with each element set to "1". Each child is initially given one candy.\n\nIn the first pass (forward traversal), it checks for increasing ratings. If the rating of the next child is higher than the current child, it gives the next child one more candy than the current child. This ensures that children with higher ratings receive more candies.\n\nIn the second pass (backward traversal), it checks for decreasing ratings. **If the rating of the previous child is higher, and the previous child hasn\'t received more candies already**, it gives the previous child one more candy to satisfy the rule.\n\nFinally, it calculates the total number of candies distributed by summing up the elements in the candy vector and returns that value as the minimum total number of candies needed to satisfy the constraints.\n\nThis code guarantees that the constraints are met while minimizing the total number of candies distributed.\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: O(n)\n10ms RUNTIME - Beats 95% solutions\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\n# Code\n```\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        int n = ratings.size() ;\n        vector<int> candy(n, 1) ;\n        \n        //First Pass:Forward traversal to handle increasing ratings\n        for(int i = 0; i<n-1; i++) {\n            if(ratings[i+1] > ratings[i])\n                candy[i+1] = candy[i] + 1 ; //If the next child has a higher rating, give them one more candy than previous child\n        }\n        \n        //Second Pass:Backward traversal to handle decreasing ratings\n        for(int i = n-1; i>0; i--) {\n            if(ratings[i-1] > ratings[i] && candy[i-1] <= candy[i])\n                candy[i-1] = candy[i] + 1 ; \n                //If the previous child has a higher rating and hasn\'t received more candy, give them more candy than current child\n        }\n\n        int totalCandy = 0 ;\n        for(int i = 0; i<n; i++)\n            totalCandy = totalCandy + candy[i] ;\n        \n        return totalCandy ;\n    }\n};\n```\n# IF YOU UNDERSTOOD AND LIKED THE CODE, PLEASE UPVOTE
['Array', 'Greedy', 'C++']