✅ 99.20% Greedy Two & One Pass
Comprehensive Guide to Solving "Candy": Distributing Candies Like a Pro\n\n## Introduction & Problem Statement\n\nHey there, coding enthusiasts! Welcome back to
# Comprehensive Guide to Solving "Candy": Distributing Candies Like a Pro\n\n## Introduction & Problem Statement\n\nHey there, coding enthusiasts! Welcome back to another exciting coding session. Today\'s problem is a treat\u2014literally! We\'re going to solve the "Candy" problem. Imagine you have a bunch of kids lined up, each with a rating assigned to them. Your task is to distribute candies to these kids following two simple rules:\n\n1. Every child must get at least one candy.\n2. A child with a higher rating should get more candies than their immediate neighbors.\n\nSounds like a piece of cake, right? But here\'s the twist: you need to accomplish this with the fewest candies possible. Let\'s dig into the mechanics of this problem and how to approach it.\n\n## Key Concepts and Constraints\n\n### Why is This Problem Unique?\n\n1. **Child Ratings**: \n   The ratings of each child are your only guide in how you distribute the candies. Following the rules while using these ratings makes this problem an intriguing puzzle.\n  \n2. **Minimum Candies**: \n   You\'re not just distributing candies willy-nilly; the goal is to meet the conditions using the least amount of candy.\n\n3. **Constraints**: \n   - The length of the ratings array, `n` , is between  $$1$$  and $$ 2 \\times 10^4 $$.\n   - Ratings are integers between $$0$$ and $$ 2 \\times 10^4 $$.\n\n### Strategies to Tackle the Problem\n\n1. **Greedy Algorithm: Two-Pass Method**  \n   This method takes two passes through the ratings array to ensure that each child gets the appropriate amount of candy.\n\n2. **One-Pass Greedy Algorithm: Up-Down-Peak Method**  \n   This more advanced method uses a single pass and employs three key variables\u2014Up, Down, and Peak\u2014to efficiently determine the minimum number of candies needed.\n\n---\n\n## Live Coding + Explenation of Greedy Two Pass\nhttps://youtu.be/JqrZHuhljps?si=TxkUjNTZ1CxMviij\n\n## Greedy Algorithm: Two-Pass Method Explained\n\n### What is a Greedy Algorithm?\n\nA Greedy Algorithm makes choices that seem optimal at the moment. For this problem, we use a two-pass greedy approach to make sure each child gets the minimum number of candies that still satisfy the conditions.\n\n### The Nuts and Bolts of the Two-Pass Method\n\n1. **Initialize Candies Array**  \n   - We start by creating a `candies` array of the same length as the `ratings` array and initialize all its values to 1. This is the base case and ensures that every child will receive at least one candy, satisfying the first condition.\n  \n2. **Forward Pass: Left to Right**\n   - Now, we iterate through the `ratings` array from the beginning to the end. For each child (except the first), we compare their rating with the one to the left. If it\'s higher, we update the `candies` array for that child to be one more than the child on the left. This takes care of the second condition but only accounts for the child\'s left neighbor.\n   \n3. **Backward Pass: Right to Left**  \n   - After the forward pass, we loop through the array again but in the reverse direction. This time, we compare each child\'s rating with the child to their right. If the rating is higher, we need to make sure the child has more candies than the right neighbor. So, we update the `candies` array for that child to be the maximum between its current number of candies and one more than the right neighbor\'s candies. This ensures that both neighboring conditions are checked and satisfied.\n   \n4. **Summing it All Up**\n   - Finally, we sum up all the values in the `candies` array. This will give us the minimum total number of candies that need to be distributed to satisfy both conditions.\n  \n### Time and Space Complexity\n\n- **Time Complexity**: $$O(n)$$, because we make two passes through the array.\n- **Space Complexity**: $$O(n)$$, for storing the `candies` array.\n\n## Code Greedy\n``` Python []\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        n = len(ratings)\n        candies = [1] * n \n\n        for i in range(1, n):\n            if ratings[i] > ratings[i-1]:\n                candies[i] = candies[i-1] + 1\n\n        for i in range(n-2, -1, -1):\n            if ratings[i] > ratings[i+1]:\n                candies[i] = max(candies[i], candies[i+1] + 1)\n        \n        return sum(candies)\n```\n``` Go []\nfunc candy(ratings []int) int {\n    n := len(ratings)\n    candies := make([]int, n)\n    for i := range candies {\n        candies[i] = 1\n    }\n\n    for i := 1; i < n; i++ {\n        if ratings[i] > ratings[i-1] {\n            candies[i] = candies[i-1] + 1\n        }\n    }\n\n    for i := n - 2; i >= 0; i-- {\n        if ratings[i] > ratings[i+1] {\n            if candies[i] <= candies[i+1] {\n                candies[i] = candies[i+1] + 1\n            }\n        }\n    }\n\n    totalCandies := 0\n    for _, candy := range candies {\n        totalCandies += candy\n    }\n\n    return totalCandies\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn candy(ratings: Vec<i32>) -> i32 {\n        let n = ratings.len();\n        let mut candies = vec![1; n];\n\n        for i in 1..n {\n            if ratings[i] > ratings[i - 1] {\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n\n        for i in (0..n - 1).rev() {\n            if ratings[i] > ratings[i + 1] {\n                candies[i] = std::cmp::max(candies[i], candies[i + 1] + 1);\n            }\n        }\n\n        candies.iter().sum()\n    }\n}\n```\n``` C++ []\nclass Solution {\npublic:\n    int candy(std::vector<int>& ratings) {\n        int n = ratings.size();\n        std::vector<int> candies(n, 1);\n\n        for (int i = 1; i < n; ++i) {\n            if (ratings[i] > ratings[i - 1]) {\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n\n        for (int i = n - 2; i >= 0; --i) {\n            if (ratings[i] > ratings[i + 1]) {\n                candies[i] = std::max(candies[i], candies[i + 1] + 1);\n            }\n        }\n\n        int totalCandies = 0;\n        for (int candy : candies) {\n            totalCandies += candy;\n        }\n\n        return totalCandies;\n    }\n};\n```\n``` Java []\nclass Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length;\n        int[] candies = new int[n];\n        Arrays.fill(candies, 1);\n\n        for (int i = 1; i < n; i++) {\n            if (ratings[i] > ratings[i - 1]) {\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i] > ratings[i + 1]) {\n                candies[i] = Math.max(candies[i], candies[i + 1] + 1);\n            }\n        }\n\n        int totalCandies = 0;\n        for (int candy : candies) {\n            totalCandies += candy;\n        }\n\n        return totalCandies;\n    }\n}\n```\n``` C# []\npublic class Solution {\n    public int Candy(int[] ratings) {\n        int n = ratings.Length;\n        int[] candies = new int[n];\n        Array.Fill(candies, 1);\n\n        for (int i = 1; i < n; i++) {\n            if (ratings[i] > ratings[i - 1]) {\n                candies[i] = candies[i - 1] + 1;\n            }\n        }\n\n        for (int i = n - 2; i >= 0; i--) {\n            if (ratings[i] > ratings[i + 1]) {\n                candies[i] = Math.Max(candies[i], candies[i + 1] + 1);\n            }\n        }\n\n        int totalCandies = 0;\n        foreach (int candy in candies) {\n            totalCandies += candy;\n        }\n\n        return totalCandies;\n    }\n}\n```\n``` JavaScript []\n/**\n * @param {number[]} ratings\n * @return {number}\n */\nvar candy = function(ratings) {\n    const n = ratings.length;\n    const candies = new Array(n).fill(1);\n\n    for (let i = 1; i < n; i++) {\n        if (ratings[i] > ratings[i - 1]) {\n            candies[i] = candies[i - 1] + 1;\n        }\n    }\n\n    for (let i = n - 2; i >= 0; i--) {\n        if (ratings[i] > ratings[i + 1]) {\n            candies[i] = Math.max(candies[i], candies[i + 1] + 1);\n        }\n    }\n\n    return candies.reduce((a, b) => a + b, 0);\n};\n```\n``` PHP []\nclass Solution {\n\n    /**\n     * @param Integer[] $ratings\n     * @return Integer\n     */\n    function candy($ratings) {\n        $n = count($ratings);\n        $candies = array_fill(0, $n, 1);\n\n        for ($i = 1; $i < $n; $i++) {\n            if ($ratings[$i] > $ratings[$i - 1]) {\n                $candies[$i] = $candies[$i - 1] + 1;\n            }\n        }\n\n        for ($i = $n - 2; $i >= 0; $i--) {\n            if ($ratings[$i] > $ratings[$i + 1]) {\n                $candies[$i] = max($candies[$i], $candies[$i + 1] + 1);\n            }\n        }\n\n        return array_sum($candies);\n    }\n}\n```\n## One-Pass Greedy Algorithm: Up-Down-Peak Method\n\n### Why `Up`, `Down`, and `Peak`?\n\nThe essence of the one-pass greedy algorithm lies in these three variables: `Up`, `Down`, and `Peak`. They serve as counters for the following:\n\n- **`Up`:** Counts how many children have **increasing ratings** from the last child. This helps us determine how many candies we need for a child with a higher rating than the previous child.\n  \n- **`Down`:** Counts how many children have **decreasing ratings** from the last child. This helps us determine how many candies we need for a child with a lower rating than the previous child.\n\n- **`Peak`:** Keeps track of the **last highest point** in an increasing sequence. When we have a decreasing sequence after the peak, we can refer back to the `Peak` to adjust the number of candies if needed.\n\n### How Does it Work?\n\n1. **Initialize Your Counters**\n   - Start with `ret = 1` because each child must have at least one candy. Initialize `up`, `down`, and `peak` to 0.\n   \n2. **Loop Through Ratings**\n   - For each pair of adjacent children, compare their ratings. Here are the scenarios:\n   \n     - **If the rating is increasing**: Update `up` and `peak` by incrementing them by 1. Set `down` to 0. Add `up + 1` to `ret` because the current child must have one more candy than the previous child.\n     \n     - **If the rating is the same**: Reset `up`, `down`, and `peak` to 0, because neither an increasing nor a decreasing trend is maintained. Add 1 to `ret` because the current child must have at least one candy.\n     \n     - **If the rating is decreasing**: Update `down` by incrementing it by 1. Reset `up` to 0. Add `down` to `ret`. Additionally, if `peak` is greater than or equal to `down`, decrement `ret` by 1. This is because the peak child can share the same number of candies as one of the children in the decreasing sequence, which allows us to reduce the total number of candies.\n  \n3. **Return the Total Candy Count**\n   - At the end of the loop, `ret` will contain the minimum total number of candies needed for all the children, so return `ret`.\n\nBy using `up`, `down`, and `peak`, we can efficiently traverse the ratings list just once, updating our total candies count (`ret`) as we go. This method is efficient and helps us solve the problem in a single pass, with a time complexity of $$O(n)$$.\n### Time and Space Complexity\n\n- **Time Complexity**: $$O(n)$$, for the single pass through the ratings array.\n- **Space Complexity**: $$O(1)$$, as we only use a few extra variables.\n\n## Code One-Pass Greedy\n``` Python []\nclass Solution:\n    def candy(self, ratings: List[int]) -> int:\n        if not ratings:\n            return 0\n        \n        ret, up, down, peak = 1, 0, 0, 0\n        \n        for prev, curr in zip(ratings[:-1], ratings[1:]):\n            if prev < curr:\n                up, down, peak = up + 1, 0, up + 1\n                ret += 1 + up\n            elif prev == curr:\n                up = down = peak = 0\n                ret += 1\n            else:\n                up, down = 0, down + 1\n                ret += 1 + down - int(peak >= down)\n        \n        return ret\n\n```\n``` Go []\nfunc candy(ratings []int) int {\n    if len(ratings) == 0 {\n        return 0\n    }\n\n    ret, up, down, peak := 1, 0, 0, 0\n\n    for i := 0; i < len(ratings) - 1; i++ {\n        prev, curr := ratings[i], ratings[i+1]\n\n        if prev < curr {\n            up++\n            down = 0\n            peak = up\n            ret += 1 + up\n        } else if prev == curr {\n            up, down, peak = 0, 0, 0\n            ret += 1\n        } else {\n            up = 0\n            down++\n            ret += 1 + down\n            if peak >= down {\n                ret--\n            }\n        }\n    }\n\n    return ret\n}\n```\n``` Rust []\nimpl Solution {\n    pub fn candy(ratings: Vec<i32>) -> i32 {\n        if ratings.is_empty() {\n            return 0;\n        }\n\n        let mut ret = 1;\n        let mut up = 0;\n        let mut down = 0;\n        let mut peak = 0;\n\n        for i in 0..ratings.len() - 1 {\n            let (prev, curr) = (ratings[i], ratings[i + 1]);\n\n            if prev < curr {\n                up += 1;\n                down = 0;\n                peak = up;\n                ret += 1 + up;\n            } else if prev == curr {\n                up = 0;\n                down = 0;\n                peak = 0;\n                ret += 1;\n            } else {\n                up = 0;\n                down += 1;\n                ret += 1 + down;\n                if peak >= down {\n                    ret -= 1;\n                }\n            }\n        }\n\n        ret\n    }\n}\n```\n\n## Performance Comparison\n\n| Language  | Approach  | Time (ms)  | Memory (MB) |\n|-----------|-----------|------------|-------------|\n| Rust      | One Pass  | 1          | 2.1         |\n| Rust      | Two Pass  | 2          | 2.3         |\n| Java      | Two Pass  | 3          | 44.3        |\n| Go        | One Pass  | 9          | 6.2         |\n| C++       | Two Pass  | 11         | 17.8        |\n| Go        | Two Pass  | 14         | 6.6         |\n| PHP       | Two Pass  | 42         | 21.9        |\n| JavaScript| Two Pass  | 59         | 45.1        |\n| C#        | Two Pass  | 98         | 44.3        |\n| Python3   | One Pass  | 126        | 19.5        |\n| Python3   | Two Pass  | 139        | 19.2        |\n\n![h2.png](https://assets.leetcode.com/users/images/098d38e8-c14e-48b3-9c98-3394eb56d996_1694566150.8876379.png)\n\n## Live Coding & Explenation - One Pass\nhttps://youtu.be/_MVFeqfiDK4?si=t8El9b9mlUQneXDk\n\n## Code Highlights and Best Practices\n\n- The Two-Pass Greedy Algorithm is straightforward and effective, making it a solid approach for this problem.\n- The One-Pass Greedy Algorithm is even more efficient in terms of space complexity and is also a bit more challenging to understand.\n  \nBy mastering these approaches, you\'ll be well-equipped to tackle other optimization problems, which are common in coding interviews and competitive programming. So, are you ready to distribute some candies? Let\'s get coding!\n
['Array', 'Greedy', 'PHP', 'C++', 'Java', 'Go', 'Python3', 'Rust', 'JavaScript', 'C#']