🚩 The Problem

Imagine a line of children, each with a performance rating. You’re tasked with distributing candies to them. But there’s a catch:

1. Every child must get at least one candy.

2. Children with a higher rating than their neighbours must get more candies.

The goal? Return the minimum number of candies you need to distribute while satisfying both conditions.

🧠 Why Is This Problem Interesting?

This problem, LeetCode #135: Candy, is not just about giving out sweets — it teaches us how to:

• Think greedily (optimise locally for a globally optimal result)

• Handle array relationships (each element compared to its neighbours)

• Ensure minimum compliance, not overgenerosity

💡 A Sample Scenario

Input: ratings = [1, 0, 2]

We must assign candies in such a way that:

• The second child (rating 0) gets fewer candies than both neighbours.

• Every child receives at least one candy.

✅ Expected Output:

Output: 5

✅ Distribution:

• First child: 2 candies

• Second child: 1 candy

• Third child: 2 candies

🛠 The Code Solution

Let’s write a clean and efficient Python solution using a two-pass greedy algorithm:

from typing import List

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n

        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

🔍 Code Explanation

Step 1: Initialise

We start by giving 1 candy to every child (since they all must receive at least one).

candies = [1] * n

Step 2: Left-to-Right Pass

We scan from left to right. A child gets 1 more candy if they have a higher rating than the previous one.

for i in range(1, n):
    if ratings[i] > ratings[i - 1]:
        candies[i] = candies[i - 1] + 1

Step 3: Right-to-Left Pass

We scan again, this time from right to left. If a child has a higher rating than the next, we update their candy count to be at least one more than the next, but preserve any previous increase using max().

for i in range(n - 2, -1, -1):
    if ratings[i] > ratings[i + 1]:
        candies[i] = max(candies[i], candies[i + 1] + 1)

Step 4: Return the Total

Sum the candies list:

return sum(candies)

🧠 Why This Works

The first pass ensures that each child satisfies the condition relative to their left neighbour, while the second pass fixes violations relative to the right neighbour, without undoing the earlier adjustments. This greedy approach ensures correctness while maintaining O(n) time and O(n) space complexity.

✅ Final Thoughts

This problem is a perfect example of how local decisions (greedy choices) can lead to a globally optimal outcome when done in multiple passes. It’s a useful pattern for many array-based optimisation problems.

If you enjoyed this walkthrough or have ideas for how to solve it differently (perhaps even in O(1) space?), drop a comment below or connect with me!