Greedy Approach || Explanation || For Beginners || Rating-Based Distribution ||
Intuition\nThe problem requires distributing candies to children based on their ratings while satisfying specific conditions. Each child must receive at least o
# Intuition\nThe problem requires distributing candies to children based on their ratings while satisfying specific conditions. Each child must receive at least one candy, and children with higher ratings must receive more candies than their immediate neighbors. The challenge is to determine the minimum number of candies needed while adhering to these constraints.\n\nTo solve this problem, we can think of it as needing to compare each child with their neighbors multiple times. A straightforward approach would be to iterate through the ratings several times, but that could lead to inefficiencies. Instead, we can use a two-pass technique to ensure that all conditions are met optimally.\n\n# Approach\n1. **Initialization:**\n   - Start by creating an array `candies` where each child initially receives 1 candy, as every child must have at least one candy.\n\n2. **Left-to-Right Pass:**\n   - Traverse the `ratings` array from left to right.\n   - For each child, check if their rating is higher than the previous child\'s rating. If it is, give the current child one more candy than the previous child.\n\n3. **Right-to-Left Pass:**\n   - Traverse the `ratings` array from right to left.\n   - For each child, check if their rating is higher than the next child\'s rating. If it is, ensure they have more candies than the next child. Use the maximum of their current candies and one more than the next child\'s candies.\n\n4. **Sum Up Candies:**\n   - Finally, sum all the values in the `candies` array to get the total number of candies needed.\n\n### Why This Works:\n- The left-to-right pass ensures that any child with a higher rating than their left neighbor receives more candies. However, this alone might not satisfy the conditions for all children, especially if the highest-rated child is followed by lower-rated children.\n- The right-to-left pass rectifies any issues by ensuring that children with a higher rating than their right neighbor also have more candies, fixing any discrepancies from the first pass.\n- This two-pass strategy ensures that the candy distribution meets all the conditions without missing any cases.\n\n# Edge Cases:\n1. **Single Child:**\n   - If there is only one child, they should receive exactly 1 candy.\n   \n   Example: `ratings = [5]` \u2192 Output: `1`\n   \n2. **Equal Ratings:**\n   - If multiple children have the same rating, they should all receive the same amount of candy (which would be at least 1).\n   \n   Example: `ratings = [2, 2, 2]` \u2192 Output: `3` (each child gets 1 candy)\n\n3. **Decreasing Ratings:**\n   - If ratings are in decreasing order, each child should receive fewer candies than the child before them.\n   \n   Example: `ratings = [3, 2, 1]` \u2192 Output: `6` (3 + 2 + 1)\n\n4. **Increasing Ratings:**\n   - If ratings are in increasing order, each child should receive more candies than the previous child.\n   \n   Example: `ratings = [1, 2, 3]` \u2192 Output: `6` (1 + 2 + 3)\n\n# Complexity\n- **Time complexity:**\n  - The time complexity is $$O(n)$$ because we make two passes over the list of ratings, where `n` is the number of children.\n\n- **Space complexity:**\n  - The space complexity is $$O(n)$$ because we use an additional array `candies` of the same size as the input `ratings`.\n\n# Code\n```java []\nclass Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length;\n        int ans = 0;\n        int[] candy = new int[n];\n\n        // Initialize each child with 1 candy\n        for (int i = 0; i < n; i++) {\n            candy[i] = 1;\n        }\n\n        // Left to right pass\n        for (int i = 1; i < n; i++) {\n            if (ratings[i] > ratings[i - 1]) {\n                candy[i] = candy[i - 1] + 1;\n            }\n        }\n\n        // Right to left pass and summing\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i] > ratings[i + 1]) {\n                candy[i] = Math.max(candy[i], candy[i + 1] + 1);\n            }\n            ans += candy[i];\n        }\n\n        // Add the last child\'s candy\n        ans += candy[n - 1];\n\n        return ans;\n    }\n}\n```\n``` cpp []\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        int n = ratings.size(), ans = 0;\n        vector<int> candy(n, 1);\n\n        for(int i = 1; i < n; i++){\n            if(ratings[i] > ratings[i - 1])\n                candy[i] = candy[i - 1] + 1;\n        }\n\n\n        for(int i = n - 2; i >= 0; i--){\n            if (ratings[i] > ratings[i + 1])\n                candy[i] = max(candy[i], candy[i + 1] + 1);\n            \n            ans += candy[i];\n        }\n\n        ans += candy[n - 1];\n\n        return ans;\n    }\n};\n```\n``` python []\nclass Solution:\n    def candy(self, ratings):\n        n = len(ratings)\n        candy = [1] * n\n\n        # Left to right pass\n        for i in range(1, n):\n            if ratings[i] > ratings[i - 1]:\n                candy[i] = candy[i - 1] + 1\n\n        # Right to left pass and summing\n        ans = 0\n        for i in range(n - 2, -1, -1):\n            if ratings[i] > ratings[i + 1]:\n                candy[i] = max(candy[i], candy[i + 1] + 1)\n            ans += candy[i]\n\n        # Add the last child\'s candy\n        ans += candy[-1]\n\n        return ans\n```
['Array', 'Greedy', 'C++', 'Java', 'Python3']