Java Solution for Candy Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition behind this approach is to use two passes to distribute candies to childr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition behind this approach is to use two passes to distribute candies to children. In the first pass, we traverse the ratings from left to right and assign candies to each child based on the ratings of the previous child. If the rating of the current child is higher than the previous child, we assign one more candy than the previous child. Otherwise, we assign one candy. In the second pass, we traverse the ratings from right to left and update the candies assigned to each child based on the ratings of the next child. If the rating of the current child is higher than the next child, we assign one more candy than the next child. We take the maximum of the candies assigned in both passes for each child and return the sum of all candies assigned.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Check if the input array ratings is null or empty. If so, return 0, as there are no children to distribute candies to.\n2. Initialize an array candies of the same length as ratings to store the candies assigned to each child.\n3. Assign one candy to the first child.\n4. Traverse the ratings from left to right and assign candies to each child based on the ratings of the previous child. If the rating of the current child is higher than the previous child, assign one more candy than the previous child. Otherwise, assign one candy.\n5. Traverse the ratings from right to left and update the candies assigned to each child based on the ratings of the next child. If the rating of the current child is higher than the next child, assign one more candy than the next child. Take the maximum of the candies assigned in both passes for each child.\n6. Return the sum of all candies assigned.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n), where n is the length of the input array ratings. The algorithm iterates through the array twice, performing constant-time operations for each element.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n), as the algorithm uses an additional array candies of the same length as ratings to store the candies assigned to each child.\n\n# Code\n```\nclass Solution \n{\n    public int candy(int[] ratings) \n    {\n        if (ratings == null || ratings.length == 0) \n        {\n            return 0;\n        }\n        int[] candies = new int[ratings.length];\n        candies[0] = 1;\n        //from let to right\n        for (int i = 1; i < ratings.length; i++) \n        {\n            if (ratings[i] > ratings[i - 1]) \n            {\n                candies[i] = candies[i - 1] + 1;\n            }\n            else \n            {\n                // if not ascending, assign 1\n                candies[i] = 1;\n            }\n        }\n        int result = candies[ratings.length - 1];\n        //from right to left\n        for (int i = ratings.length - 2; i >= 0; i--) \n        {\n            int cur = 1;\n            if (ratings[i] > ratings[i + 1]) \n            {\n                cur = candies[i + 1] + 1;\n            }\n            result += Math.max(cur, candies[i]);\n            candies[i] = cur;\n        }\n        return result;\n\n    }\n}\n```
['Java']