Beginner Friendly || Line By Line Explanation || Easy Candy Solution || Python || Java || Beats 95%+
Beats \n\n\n# JAVA CODE 1-2ms \n# UPVOTE IF U LIKE !!!\n\n# Intuition\n Describe your first thoughts on how to solve this problem. \nThe main intuition behind t
# Beats \n![image.png](https://assets.leetcode.com/users/images/b132f758-40f8-4e36-8898-57b76f9ae0d8_1694582712.425661.png)\n\n# JAVA CODE 1-2ms \n# UPVOTE IF U LIKE !!!\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe main intuition behind this problem is to ensure that children with higher ratings receive more candies than their neighbors, while still giving each child at least one candy. One way to approach this is to scan the ratings array from left to right and then from right to left, adjusting the number of candies given based on the rating comparisons.\n# Approach\n1. Initialize variables:\n\n- 1. "up_count" to count increasing ratings sequences (starts at 1).\n- 2. "down_count" to count decreasing ratings sequences (starts at 0).\n- 3. "candies_given" to keep track of the total number of candies given (starts at 1).\n- 4. "peak" to keep track of the peak of increasing ratings (starts at 0).\n2. Iterate through the ratings list starting from the second element.\n\n- 1. If the current rating is greater than the previous one, it\'s an increasing sequence:\n- - - Increment up_count.\n- - - Reset down_count to 0.\n- - - Increment candies_given by up_count.\n- - - Update peak to the value of up_count (as this is the peak of the current increasing sequence).\n- 2. If the current rating is equal to the previous one, reset counts:\n- - - Reset down_count and peak to 0.\n- - - Reset up_count to 1.\n- - - Increment candies_given by 1 (since they have the same rating, they should have the same number of candies).\n- 3. If the current rating is less than the previous one, it\'s a decreasing sequence:\n- - - Increment down_count.\n- - - Reset up_count to 1.\n- - - Increment candies_given by down_count.\n- - - If the current down_count is greater than or equal to peak, give an extra candy to the child at the peak of the decreasing sequence.\n3. Return candies_given, which represents the minimum number of candies given to satisfy the conditions\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time Complexity: $$O(n)$$ - We iterate through the ratings array twice, once from left to right and once from right to left.\n- Space Complexity: $$O(1)$$ - We use a constant amount of extra space for variables.\n\n\n# Code\n# Python\n```\n# Define a class named Solution.\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        up_count = 1  # Initialize a variable to count increasing ratings sequences.\n        down_count = 0  # Initialize a variable to count decreasing ratings sequences.\n        candies_given = 1  # Initialize the total count of candies given, starting with one.\n        peak = 0  # Initialize a variable to keep track of the peak of increasing ratings.\n\n        # Iterate through the ratings list starting from the second element.\n        for i in range(1, len(ratings)):\n            if ratings[i] > ratings[i - 1]:\n                # If the current rating is greater than the previous one, it\'s an increasing sequence.\n                up_count += 1\n                down_count = 0\n                candies_given += up_count  # Increment the candy count for the current child.\n                peak = up_count  # Update the peak for the current increasing sequence.\n            elif ratings[i] == ratings[i - 1]:\n                # If the current rating is equal to the previous one, reset counts.\n                down_count = 0\n                peak = 0\n                up_count = 1\n                candies_given += 1  # Increment the candy count for the current child (since they have the same rating).\n            else:\n                # If the current rating is less than the previous one, it\'s a decreasing sequence.\n                down_count += 1\n                up_count = 1\n                candies_given += down_count  # Increment the candy count for the current child.\n                if peak <= down_count:\n                    candies_given += 1  # Give an extra candy to the child at the peak of the decreasing sequence.\n\n        return candies_given  # Return the total number of candies given to all children.\n\n          \n```\n# JAVA\n```\n// Define a class named Solution.\nclass Solution {\n    // Define a method named candy.\n    public int candy(int[] ratings) {\n        // Check if the ratings array is empty; if so, return 0 candies.\n        if (ratings.length == 0)\n            return 0;\n        \n        int n = ratings.length; // Get the number of children.\n        int[] candies = new int[n]; // Create an array to store the number of candies for each child.\n\n        // Initialize each child with 1 candy (as a baseline).\n        for (int i = 0; i < n; i++) {\n            candies[i] = 1;\n        }\n\n        // Pass through the ratings array from left to right and adjust candies as needed.\n        for (int i = 1; i < n; i++) {\n            if (ratings[i] > ratings[i - 1]) {\n                candies[i] = 1 + candies[i - 1];\n            }\n        }\n\n        // Pass through the ratings array from right to left to ensure the right neighbors also get appropriate candies.\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {\n                candies[i] = 1 + candies[i + 1];\n            }\n        }\n\n        int totalCandies = 0; // Initialize a variable to store the total number of candies given.\n\n        // Sum up the candies for all children to get the total count.\n        for (int candyCount : candies) {\n            totalCandies += candyCount;\n        }\n\n        return totalCandies; // Return the total number of candies given to all children.\n    }\n}\n\n```\n# C++\n```\n// Define a class named Solution.\nclass Solution {\npublic:\n    // Define a method named candy.\n    int candy(vector<int>& ratings) {\n        int n = ratings.size(); // Get the number of children.\n        vector<int> left(n, 1), right(n, 1); // Create vectors to store left and right candy counts for each child.\n\n        // Calculate the left candies.\n        for (int i = 1; i < n; ++i) {\n            if (ratings[i] > ratings[i - 1]) {\n                left[i] = left[i - 1] + 1;\n            }\n        }\n\n        // Calculate the right candies.\n        for (int i = n - 2; i >= 0; --i) {\n            if (ratings[i] > ratings[i + 1]) {\n                right[i] = right[i + 1] + 1;\n            }\n        }\n\n        int totalCandies = 0; // Initialize a variable to store the total number of candies given.\n\n        // Calculate the maximum candies for each child from the left and right counts and sum them up.\n        for (int i = 0; i < n; ++i) {\n            totalCandies += max(left[i], right[i]);\n        }\n\n        return totalCandies; // Return the total number of candies given to all children.\n    }\n};\n\n```
['Dynamic Programming', 'Greedy', 'Python', 'C++', 'Java', 'Python3']