One-pass constant space Java solution
Hi guys!\n\nThis solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:
Hi guys!\n\nThis solution picks each element from the input array only once. First, we give a candy to the first child. Then for each child we have three cases:\n\n 1. His/her rating is equal to the previous one -> give 1 candy.\n 2. His/her rating is greater than the previous one -> give him (previous + 1) candies.\n 3. His/her rating is less than the previous one -> don't know what to do yet, let's just count the number of such consequent cases.\n \nWhen we enter 1 or 2 condition we can check our count from 3. If it's not zero then we know that we were descending before and we have everything to update our total candies amount: number of children in descending sequence of raitings - coundDown, number of candies given at peak - prev (we don't update prev when descending). Total number of candies for "descending" children can be found through arithmetic progression formula (1+2+...+countDown). Plus we need to update our peak child if his number of candies is less then or equal to countDown. \n\nHere's a pretty concise code below.\n\n----------\n\n    public class Solution {\n        public int candy(int[] ratings) {\n            if (ratings == null || ratings.length == 0) return 0;\n            int total = 1, prev = 1, countDown = 0;\n            for (int i = 1; i < ratings.length; i++) {\n                if (ratings[i] >= ratings[i-1]) {\n                    if (countDown > 0) {\n                        total += countDown*(countDown+1)/2; // arithmetic progression\n                        if (countDown >= prev) total += countDown - prev + 1;\n                        countDown = 0;\n                        prev = 1;\n                    }\n                    prev = ratings[i] == ratings[i-1] ? 1 : prev+1;\n                    total += prev;\n                } else countDown++;\n            }\n            if (countDown > 0) { // if we were descending at the end\n                total += countDown*(countDown+1)/2;\n                if (countDown >= prev) total += countDown - prev + 1;\n            }\n            return total;\n        }\n    }\n\nHave a nice coding!
['Java']