【Video】O(n) Time, O(1) Space Solution - Python, JavaScript, Java, C++
Intuition\nKeep two peak values and subtract the lower peak from total.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/f5oFx-X0eS4\n\n### \u2B50\uFE0F\u2B50\uFE
# Intuition\nKeep two peak values and subtract the lower peak from total.\n\n---\n\n# Solution Video\n\nhttps://youtu.be/f5oFx-X0eS4\n\n### \u2B50\uFE0F\u2B50\uFE0F Don\'t forget to subscribe to my channel! \u2B50\uFE0F\u2B50\uFE0F\n\n**\u25A0 Subscribe URL**\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\nSubscribers: 9,731\nThank you for your support!\n\n---\n\n# Approach\n\n## \u25A0 Step 1\nIntialize `total_candies` with `len(ratings)` because at least all children has one candy.\n\n## \u25A0 Step 2\nWe iterate through `ratings` one by one.\n\n### case1\n```\nif ratings[i] == ratings[i - 1]:\n```\nwe don\'t have to give a candy to the current `i` child because current `i` child has the same rating with previous child. Just increment `i` and continue.\n\n### case2\n```\nwhile i < n and ratings[i] > ratings[i - 1]:\n```\nThis case indicates that the current `i` child has higher raiting than `i - 1` previous child. In this case, we need to give candies to the current `i` child.\n\nAdd `+1` to `current_peak` and add `current_peak` to `total_candies` and incremtnt `i`. this process continues until we don\'t meet case2 `while condition` above.\n\nLet me explain `current_peak` in "How it works" section.\n\n### case3\n```\nwhile i < n and ratings[i] < ratings[i - 1]:\n```\nThis case indicates that the current `i` child has lower raiting than `i - 1` previous child. In this case, actually we do the same thing of `case2`. Because even if input is decreasing order `[9,5,3,1]`, we need to give candies to the current `i` child. In the end, total candies are 10 `[4,3,2,1]`. we need some extra candies.\n\nAdd `+1` to `current_valley` and add `current_valley` to `total_candies` and incremtnt `i`. this process continues until we don\'t meet case 3 `while condition` above.\n\nLet me explain `current_valley` in "How it works" section.\n\nIn the last of Step 2, subtract minium of `current_peak` or `current_valley` from `total_candies`.\n\n# How it works\nLet\'s think with this input. \n```\nInput: ratings = [2,4,6,7,3,2,2]\n```\n```\ntotal_candies(Let\'s say "total") = 7 (length of input array)\ncurrent_peak(Let\'s say "peak") = 0\ncurrent_valley(Let\'s say "valley") = 0\n\n```\nIn Step2, starting from `index 1`.\n```\n\u25A0 Case2\ncondtion: while i < n and ratings[i] > ratings[i - 1]:\n\nindex 1 > index 0, so peak = 1, valley = 0, total = 8 (7 + 1)\nindex 2 > index 1, so peak = 2, valley = 0, total = 10 (8 + 2)\nindex 3 > index 2, so peak = 3, valley = 0, total = 13 (10 + 3)\nindex 4 < index 3, then stop Case2\n\nOur code distrubtes candies like this so far\nfrom [1,1,1,1,1,1,1]\nto   [1,2,3,4,1,1,1](total 13 candies)\n```\n```\n\u25A0 Case3\ncondtion: while i < n and ratings[i] < ratings[i - 1]:\n\nindex 4 < index 3, so peak = 3, valley = 1, total = 14 (13 + 1)\nindex 5 < index 4, so peak = 3, valley = 2, total = 16 (14 + 2)\nindex 6 == index 5, then stop Case3\n\nOur code distrubtes candies like this so far\nfrom [1,2,3,4,1,1,1](Case2)\nto   [1,2,3,4,2,3,1](total 16 candies)\n```\n\nLet me explain `total_candies -= min(current_peak, current_valley)`\nBefore that, `the last rating(index 6)` is equal to `index 5`, so we don\'t do anything(meet `Case1`). Let me skip it.\n\nNow Look at this. When ratings = `[2,4,6,7,3,2,2]`\n```\nThis is real distribution, In other words, the minimum number of\ncandies you need to have to distribute\n\n[1,2,3,4,2,1,1] = 14 candies\n[1,1,1,1,1,1,1]\n[0,1,2,3,1,0,0](additional candies for each children)\n```\n```\nHow our code distributes candies\n\n[1,2,3,4,2,3,1] = 16 candies\n[1,1,1,1,1,1,1]\n[0,1,2,3,1,2,0](additional candies for each children)\n```\n\nCompare distribution of adittional candies.\n```\n[0,1,2,3,1,0,0](Real)\n[0,1,2,3,1,2,0](Our code)\n```\nOur code distributes `extra 2 candies` at `index 5` which is equal to minimum of `current_peak` or `current_valley`. That\'s because actually we add peaks twice as a `peak` and as a `valley` in Case2 and Case3. For this question, we need peak value only once. More precisely, we need only higher peak between range of one of `peak` and `valley` combinations(in this case between `index1` and `index5`), because of constraints from the description saying "Children with a higher rating get more candies than their neighbors".\n\nThat\'s why we need to substract `minimum peak` from `total_candies`. In this case `16 - 2`. `peak = 3` vs `valley = 2`\n\n```\nOutput: 14\n```\n\n# Complexity\n- Time complexity: O(n)\n\'n\' is the number of elements in the \'ratings\' list. This is because we are using a single loop to iterate through the ratings, and within the loop, we perform constant time operations.\n\n- Space complexity: O(1), which means it uses a constant amount of additional memory regardless of the size of the \'ratings\' list. The only variables that consume memory are \'n\', \'total_candies\', \'i\', \'current_peak\', and \'current_valley\', and these variables do not depend on the input size \'n\'.\n\n```python []\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        n = len(ratings)\n        total_candies = n\n        i = 1\n\n        while i < n:\n            if ratings[i] == ratings[i - 1]:\n                i += 1\n                continue\n\n            current_peak = 0\n            while i < n and ratings[i] > ratings[i - 1]:\n                current_peak += 1\n                total_candies += current_peak\n                i += 1\n            \n            if i == n:\n                return total_candies\n\n            current_valley = 0\n            while i < n and ratings[i] < ratings[i - 1]:\n                current_valley += 1\n                total_candies += current_valley\n                i += 1\n\n            total_candies -= min(current_peak, current_valley)\n\n        return total_candies\n```\n```javascript []\n/**\n * @param {number[]} ratings\n * @return {number}\n */\nvar candy = function(ratings) {\n    const n = ratings.length;\n    let totalCandies = n;\n    let i = 1;\n\n    while (i < n) {\n        if (ratings[i] === ratings[i - 1]) {\n            i++;\n            continue;\n        }\n\n        let currentPeak = 0;\n        while (i < n && ratings[i] > ratings[i - 1]) {\n            currentPeak++;\n            totalCandies += currentPeak;\n            i++;\n        }\n\n        if (i === n) {\n            return totalCandies;\n        }\n\n        let currentValley = 0;\n        while (i < n && ratings[i] < ratings[i - 1]) {\n            currentValley++;\n            totalCandies += currentValley;\n            i++;\n        }\n\n        totalCandies -= Math.min(currentPeak, currentValley);\n    }\n\n    return totalCandies;    \n};\n```\n```java []\nclass Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length;\n        int totalCandies = n;\n        int i = 1;\n\n        while (i < n) {\n            if (ratings[i] == ratings[i - 1]) {\n                i++;\n                continue;\n            }\n\n            int currentPeak = 0;\n            while (i < n && ratings[i] > ratings[i - 1]) {\n                currentPeak++;\n                totalCandies += currentPeak;\n                i++;\n            }\n\n            if (i == n) {\n                return totalCandies;\n            }\n\n            int currentValley = 0;\n            while (i < n && ratings[i] < ratings[i - 1]) {\n                currentValley++;\n                totalCandies += currentValley;\n                i++;\n            }\n\n            totalCandies -= Math.min(currentPeak, currentValley);\n        }\n\n        return totalCandies;        \n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n       int n = ratings.size();\n        int totalCandies = n;\n        int i = 1;\n\n        while (i < n) {\n            if (ratings[i] == ratings[i - 1]) {\n                i++;\n                continue;\n            }\n\n            int currentPeak = 0;\n            while (i < n && ratings[i] > ratings[i - 1]) {\n                currentPeak++;\n                totalCandies += currentPeak;\n                i++;\n            }\n\n            if (i == n) {\n                return totalCandies;\n            }\n\n            int currentValley = 0;\n            while (i < n && ratings[i] < ratings[i - 1]) {\n                currentValley++;\n                totalCandies += currentValley;\n                i++;\n            }\n\n            totalCandies -= min(currentPeak, currentValley);\n        }\n\n        return totalCandies;        \n    }\n};\n```\n\n---\n\nThank you for reading my post. Please upvote it and don\'t forget to subscribe to my channel!\n\n### \u2B50\uFE0F Subscribe URL\nhttp://www.youtube.com/channel/UC9RMNwYTL3SXCP6ShLWVFww?sub_confirmation=1\n\n### \u2B50\uFE0F Twitter\nhttps://twitter.com/CodingNinjaAZ\n\n### \u2B50\uFE0F My latest video \n#209 - Minimum Size Subarray Sum\n\nhttps://youtu.be/s26WQrtMKBQ
['Array', 'C++', 'Java', 'Python3', 'JavaScript']