← Back to Index

📚 Candy – Java Cheat Sheet

📌 What Is It?

The Candy problem involves distributing candies to children standing in a line such that:

• Each child must have at least one candy.
• Children with a higher rating than their neighbors must receive more candies than their neighbors.

The goal is to determine the minimum number of candies required to satisfy these conditions.

🧱 Pattern Template

Two-Pass Greedy Algorithm

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        // Left-to-right pass
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Right-to-left pass
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        // Calculate the total candies
        int totalCandies = 0;
        for (int candy : candies) {
            totalCandies += candy;
        }

        return totalCandies;
    }
}

▶️ View Animation

🎥 Video Explanation

For a detailed explanation, watch this video: Candy Problem Explanation by NeetCode IO

📊 Time Complexity

• Time Complexity: O(N), where N is the number of children.
• Space Complexity: O(N), for the candies array.

✅ Use Cases

• Optimizing resource allocation based on constraints.
• Solving problems involving relative rankings or ratings.

📘 Common LeetCode Problems

• 135. Candy [Hard] Greedy

🧪 Example

Input: ratings = [1,0,2]
Output: 5

Explanation:
- Give 2 candies to the child with a rating of 2.
- Give 1 candy to the child with a rating of 0.
- Give 2 candies to the child with a rating of 1.
- Total candies = 2 + 1 + 2 = 5.

💡 Pro Tips

• Use a two-pass greedy approach to ensure both left and right neighbors are satisfied.
• In the left-to-right pass, ensure higher-rated children get more candies than their left neighbors.
• In the right-to-left pass, ensure higher-rated children get more candies than their right neighbors.
• Take the maximum value during the second pass to satisfy both conditions.