Candy

mosesg1123
Jun 13
4 min read

"Candy" is one of those deceptively simple problems that tests your ability to think through constraints and find a clean, efficient strategy. The "Candy" problem is a classic greedy algorithm challenge often asked in interviews. It tests whether you can distribute limited resources while meeting strict conditions on relative ranking — something that comes up surprisingly often in real-world systems.

Problem Statement

There are n children standing in a line. Each child is assigned a rating value via the array ratings. You are to give each child at least one candy. Children with a higher rating than their immediate neighbors must get more candies than those neighbors.

Return the minimum number of candies you must distribute to satisfy all conditions.

Example 1:

Input: ratings = [1, 0, 2]
Output: 5
Explanation: You can allocate candies as [2,1,2].

Example 2:

Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate candies as [1,2,1].

1. Clarify Requirements Before Jumping Into Code

Does every child get at least one candy? → Yes, that’s required.
Can multiple children have the same rating? → Yes.
If two neighbors have the same rating, do they need different candies? → No. Only children with strictly higher ratings must get more candies.
Can we use extra space? → Yes, O(n) space is fine.

2. Identify the Category of the Question

This is a Greedy Algorithm problem with hints of dynamic programming.

It’s about:

Distributing resources based on local comparisons.
Minimizing total output while satisfying constraints.

Common patterns:

Two-pass scans
Local-global decision balancing
State tracking in an auxiliary array

3. Consider a Brute‑Force Approach to Understand the Problem

Start by giving everyone 1 candy.

Then iterate repeatedly:

If a child has a higher rating than their left or right neighbor, but doesn’t have more candies, increase their candy count.
Repeat until there are no more changes.

Time Complexity: O(n²) in the worst case. We can do better!

4. Brainstorm More Solutions

To find a more efficient solution, let's try simplifying the problem a bit.

What if I didn't have to take into account both neighbors? What if I only needed to account for the left neighbors?

Then I could do this in one pass. I would give every child 1 candy, then I could iterate from left-to-right. If ratings[i] > ratings[i-1], then I give candies[i] = candies[i-1] + 1.

Now, what if I only need to account for the right neighbors? The answer is the same, but in reverse! We scan from right to left, and if ratings[i] > ratings[i+1], then I give candies[i] = candies[i+1] + 1.

So now that I know how to each neighbor individually, how do I handle them together?

Can I simply combine my two solutions into one?

There's one challenge: after my first left-to-right scan, candies[i] could potentially have an updated value. How do I combine that updated candy value with the candies I want to allocate from my right-to-left scan?

I can just pick the bigger one! That way I'm guaranteed to just choose the candy value that will satisfy both neighbors.

Formalizing that into logic:

Scan from left to right
- If ratings[i] > ratings[i-1], give candies[i] = candies[i-1] + 1
- Otherwise, keep candies[i] at 1
Scan from right to left
- If ratings[i] > ratings[i+1], give candies[i] whichever is larger: candies[i] or candies[i+1] + 1 (i.e. max(candies[i], candies[i+1] + 1))
To calculate the result, sum the array!

Example:

ratings = [1, 0, 2]
left pass:  [1, 1, 2]
right pass: [2, 1, 2]
sum = 5

Time Complexity: This give us an O(n) solution

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute Force	O(n²)	O(n)	Simple to implement	Too slow for large n
Two-Pass Greedy (Optimal)	O(n)	O(n)	Fast, handles all edge cases	Slightly less intuitive

6. Write Pseudocode to Structure Your Thoughts

initialize candies[] = [1] * n

left to right:
  if ratings[i] > ratings[i-1]:
    candies[i] = candies[i-1] + 1

right to left:
  if ratings[i] > ratings[i+1]:
    candies[i] = max(candies[i], candies[i+1] + 1)

return sum(candies)

7. Consider Edge Cases

All ratings equal → every child gets 1 candy.
Strictly increasing ratings → [1,2,3,...]
Strictly decreasing ratings → [n,n-1,...]
Zig-zag pattern → requires adjustments in both passes.

8. Write Full Code Syntax (Java)

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

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

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

        int total = 0;
        for (int c : candies) {
            total += c;
        }

        return total;
    }
}

9. Test Your Code

System.out.println(candy(new int[]{1, 0, 2}));       // 5
System.out.println(candy(new int[]{1, 2, 2}));       // 4
System.out.println(candy(new int[]{1, 2, 3, 4}));    // 10
System.out.println(candy(new int[]{4, 3, 2, 1}));    // 10
System.out.println(candy(new int[]{1, 3, 2, 2, 1})); // 7

10. Key Lessons to Remember for Future Questions

Two-pass greedy algorithms work well when you have bidirectional constraints.
When you're stuck, simplify the problem!
Don't be afraid to use two sweeps to satisfy local maxima/minima.
Always think about the structure of the problem - greedy strategies often emerge from recognizing local conditions.
This problem frequently appears in various forms - think salary bonuses, ranking systems, or reward distributions.

Good Luck and Happy Coding!