🚀 Beats 99.93% || Greedy || Two Solutions || C++ || Java || Python || Commented Code 🚀
Problem Description\nThe task is distributing candies to a group of n children standing in a line. Each child is assigned a rating value, represented as an inte
# Problem Description\nThe task is distributing candies to a group of `n` children standing in a line. Each child is assigned a **rating value**, represented as an **integer** array called `ratings`.\n\nFollow **two specific requirements** while distributing the candies:\n- Each child must have at least one candy.\n- Children with a higher rating should receive more candies than their neighbors.\n\nThe **goal** is to determine the **minimum** number of candies needed to satisfy these requirements and distribute the candies to the children accordingly.\n\n- **Constraints:**\n    - `n == ratings.length`\n    - `1 <= n <= 2 * 104`\n    - `0 <= ratings[i] <= 2 * 104`\n    - at **least one candy** for each child\n    - neighbours with **higher rating** have **more candies**\n\n\n---\n\n\n\n# Intuition\nHi there\uD83D\uDE00\nLet\'s take a look on this interesting problem.\n\nFor our candies task we have **two crucial requirements**: Each child must have **at least one** candy, and children with **higher ratings** than their **neighbors** have more candies than them... Interesting.\n\nLet\'s explore some ratings\' cases together:\n\n\n```\n2, 2, 2 \n```\nHere we can see that **each child** of them can have **one candy** since no one has higher rating than its neighbor.\n\n```\n1, 2, 2, 2 \n```\nHere we can see that the array of candies will be `1, 2, 1, 1`.\n\n```\n9, 8, 7\n```\nHere we can see that array of candies will be `3, 2, 1`.\n\n```\n7, 8, 9\n```\nHere we can see that array of candies will be `1, 2, 3`.\n\n\nI think now we have some **idea** about what is going on here\uD83E\uDD14\n- Children with **equal ratings** can have different candies and that won\'t violate our requirements since we are aiming for giving **minimum** candies.\n- We must take care of **decreasing** subarrays and **increasing** ones.\n\nHow can we use an approach that take care of these **observations**?\uD83D\uDE80\n\n## Two Pass Approach \nIn this approach we will:\n- Iterate from `left to right` to take care of **increasing** subarrays \n- Iterate from `right to left` to take care of **decreasing** subarrays\n- We **won\'t do anything** to **equal** neighbours since they won\'t affect our requirements\n\nLet\'s take an example:\n```\n9, 8, 8, 7, 7, 8, 9\n```\n**First** we have array of candes `1, 1, 1, 1, 1, 1, 1`\n\nAfter our **first pass** (from left to right) we will have array of candies `1, 1, 1, 1, 1, 2, 3`.\nWe can see that it **handled** the **increasing** subarray perfectly.\n\nAfter our **second pass**(from right to left) we will have array of candies `2, 1, 2, 1, 1, 2, 3 `.\nwe can see that it also **handled** the **decreasing** subarray perfectly.\n\nAlso, it handled the equal neighbours after the two passes. It finally minimized our candies. \n\n\n## One Pass Approach \nThis solution is more challenging since it requires us to handle the **three cases** in **one** pass. How can we start? \uD83E\uDD14\nWe saw before that we have three cases **increasing** subarrays,  **decreasing** subarrays and **equal** subbarrays.\nWe can start by intialize **three variables** to handle the three of them.\n\nFor **increasing** subarray we need one variable `up` to handle what candy we give to current child.\nfor each child in the **increasing** subarray increase the `up` variable by one and give the current child `up + 1` candies indicating that it must have more that the child before him\nwe will call `up + 1` as `peak` to mean the highest child in our subarray\n\nFor **equal** subarrays, only give them `one` candy and we will see that we only give one to the children in the middle of the subarray\n\nFor **decreasing** subarray here comes the challenge \nWe will introduce variable like first case called `down` but the purpose of it **not** indicating that we give candies to current child but, giving **one** candy to current child and **one** candy for each child before him in the decreasing subarray to meet the requirements.\n\nExample : `1, 2, 3, 3, 2, 1`\n![1.jpg](https://assets.leetcode.com/users/images/a99e9752-25cb-46f7-8d18-364b17088f96_1694573615.3577487.jpeg)\n\nBut what if we have **increasing** then **decreasing** subarrays?\nWe will have the **last** child of the first subarray as first child on the second and then we give each child in the decreasing subarray one candy except that child who is our `peak` until the length of the subarray is larger than the `peak`.\n\nExample : `1, 2, 3, 2, 1`\n![2.jpg](https://assets.leetcode.com/users/images/53bc278c-a910-47a6-846c-d8d85461c79c_1694573659.6552763.jpeg)\n\n\n\n---\n\n\n\n# Approach\n\n## Two Pass Approach\n### Steps\n- **Initialize** variables:\n    - `n` is number of children.\n    - `candies` to store candies for each child..\n- **First Pass** (Left to Right):\n    - For each child, **check** if the previous child has a **lower** rating and has **more** or **equal** candies.\n    - If **true**, give the current child one more candy than the previous child.\n- **Second Pass** (Right to Left):\n    - For each child, **check** if the next child has a **lower** rating and has **more** or **equal** candies.\n    - If **true**, give the current child one more candy than the next child.\n    \n- Calculate and return totalCandies.\n\n### Complexity\n- **Time complexity:** $$O(N)$$\nSince we are looping over the ratings array twice then the time complexity is `2*N` which is `O(N)`.\n- **Space complexity:** $$O(N)$$\nSince we are storing the number of candies for each child then the space complexity is `O(N)`.\n\n\n---\n\n## One Pass Approach\n### Steps\n- **Initialize** variables:\n    - `n` to store the number of children.\n    - `upCount` to keep track of consecutive increasing ratings.\n    - `downCount` to keep track of consecutive decreasing ratings.\n    - `peakCount` to store the number of candies at the peak of increasing ratings.\n    - `totalCandies` to count required candies.\n- **Iterate** Through Ratings:\n    - **compare** the child rating with the **previous** child\n    - If current child has a **higher** rating than previous one then update the variables and add `peakCount` to `totalCandies`.\n    - If current child has the **same** rating as previous one then update and add `1` to ``totalCandies``.\n    - If current child has a **lower** rating than previous one update and update `totalCandies` by adding `downCount` + 1, subtracting `1` if `peakCount` is greater than `downCount`.\n- **Return** `totalCandies`\n\n### Complexity\n- **Time complexity:** $$O(N)$$\nSince we are looping over the ratings array one time then the time complexity is `N` which is `O(N)`.\n- **Space complexity:** $$O(1)$$\nSince we are storing only couple of variables then the space complexity is `O(1)`.\n\n\n---\n\n\n\n# Code\n## Two Pass Approach\n```C++ []\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        int n = ratings.size(); // Get the number of children\n        \n        vector<int> candies(n, 1); // Initialize a vector to store the number of candies for each child\n        \n        // First pass: Check ratings from left to right\n        for(int i = 1; i < n; i++){\n            if(ratings[i - 1] < ratings[i] && candies[i - 1] >= candies[i]){\n                // If the current child has a higher rating and fewer or equal candies than the previous child,\n                // give them one more candy than the previous child\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n        \n        // Second pass: Check ratings from right to left\n        for(int i = n - 2; i >= 0; i--){\n            if(ratings[i + 1] < ratings[i] && candies[i + 1] >= candies[i]){\n                // If the current child has a higher rating and fewer or equal candies than the next child,\n                // give them one more candy than the next child\n                candies[i] = candies[i + 1] + 1;\n            }\n        }\n        \n        int totalCandies = 0;\n        \n        // Calculate the total number of candies needed\n        for(int i = 0; i < n; i++){\n            totalCandies += candies[i];\n        }\n        \n        return totalCandies;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length; // Get the number of children\n        \n        int[] candies = new int[n]; // Initialize an array to store the number of candies for each child\n        \n        // First pass: Check ratings from left to right\n        for (int i = 1; i < n; i++) {\n            if (ratings[i - 1] < ratings[i] && candies[i - 1] >= candies[i]) {\n                // If the current child has a higher rating and fewer or equal candies than the previous child,\n                // give them one more candy than the previous child\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n        \n        // Second pass: Check ratings from right to left\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i + 1] < ratings[i] && candies[i + 1] >= candies[i]) {\n                // If the current child has a higher rating and fewer or equal candies than the next child,\n                // give them one more candy than the next child\n                candies[i] = candies[i + 1] + 1;\n            }\n        }\n        \n        int totalCandies = 0;\n        \n        // Calculate the total number of candies needed\n        for (int i = 0; i < n; i++) {\n            totalCandies += candies[i] + 1;\n        }\n        \n        return totalCandies;\n    }\n}\n```\n```Python []\nclass Solution:\n    def candy(self, ratings) -> int:\n        n = len(ratings)  # Get the number of children\n        \n        candies = [1] * n  # Initialize a list to store the number of candies for each child\n        \n        # First pass: Check ratings from left to right\n        for i in range(1, n):\n            if ratings[i - 1] < ratings[i] and candies[i - 1] >= candies[i]:\n                # If the current child has a higher rating and fewer or equal candies than the previous child,\n                # give them one more candy than the previous child\n                candies[i] = candies[i - 1] + 1\n        \n        # Second pass: Check ratings from right to left\n        for i in range(n - 2, -1, -1):\n            if ratings[i + 1] < ratings[i] and candies[i + 1] >= candies[i]:\n                # If the current child has a higher rating and fewer or equal candies than the next child,\n                # give them one more candy than the next child\n                candies[i] = candies[i + 1] + 1\n        \n        total_candies = sum(candies)  # Calculate the total number of candies needed\n        \n        return total_candies\n```\n\n## One Pass Approach\n```C++ []\nclass Solution {\npublic:\n    int candy(vector<int>& ratings) {\n        int n = ratings.size(); // Get the number of children\n        int upCount = 0, downCount = 0, peakCount = 0, totalCandies = 1; // Initialize variables\n        \n        for(int i = 1; i < n ; i ++){\n            if(ratings[i - 1] < ratings[i]){\n                // If the current child has a higher rating than the previous one\n                downCount = 0;\n                upCount += 1;\n                peakCount = upCount + 1;\n                totalCandies += peakCount;\n            } else if(ratings[i - 1] == ratings[i]){\n                // If the current child has the same rating as the previous one\n                downCount = 0;\n                upCount = 0;\n                peakCount = 0;\n                totalCandies += 1;\n            } else {\n                // If the current child has a lower rating than the previous one\n                downCount += 1;\n                upCount = 0;\n                totalCandies += downCount + 1 - (peakCount > downCount);\n            }\n        }\n        \n        return totalCandies;\n    }\n};\n```\n```Java []\npublic class Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length; // Get the number of children\n        int upCount = 0, downCount = 0, peakCount = 0, totalCandies = 1; // Initialize variables\n        \n        for (int i = 1; i < n; i++) {\n            if (ratings[i - 1] < ratings[i]) {\n                // If the current child has a higher rating than the previous one\n                downCount = 0;\n                upCount += 1;\n                peakCount = upCount + 1;\n                totalCandies += peakCount;\n            } else if (ratings[i - 1] == ratings[i]) {\n                // If the current child has the same rating as the previous one\n                downCount = 0;\n                upCount = 0;\n                peakCount = 0;\n                totalCandies += 1;\n            } else {\n                // If the current child has a lower rating than the previous one\n                downCount += 1;\n                upCount = 0;\n                totalCandies += downCount + 1 - (peakCount > downCount ? 1 : 0);\n            }\n        }\n        \n        return totalCandies;\n    }\n}\n```\n```Python []\nclass Solution:\n    def candy(self, ratings) -> int:\n        n = len(ratings)  # Get the number of children\n        upCount = downCount = peakCount = 0\n        totalCandies = 1  # Initialize variables\n        \n        for i in range(1, n):\n            if ratings[i - 1] < ratings[i]:\n                # If the current child has a higher rating than the previous one\n                downCount = 0\n                upCount += 1\n                peakCount = upCount + 1\n                totalCandies += peakCount\n            elif ratings[i - 1] == ratings[i]:\n                # If the current child has the same rating as the previous one\n                downCount = 0\n                upCount = 0\n                peakCount = 0\n                totalCandies += 1\n            else:\n                # If the current child has a lower rating than the previous one\n                downCount += 1\n                upCount = 0\n                totalCandies += downCount + 1 - (1 if peakCount > downCount else 0)\n        \n        return totalCandies\n```\n\n\n![leet_sol.jpg](https://assets.leetcode.com/users/images/fa9927ee-3d40-447d-ae31-148ce5f55633_1694564084.5767484.jpeg)\n\n\n
['Greedy', 'C++', 'Java', 'Python3']