🧒🍬 Beginner-Friendly Guide to Solving “Distribute Candies Among Children” | LeetCode 135 Explained (C++ | JavaScript | Python)

Posted on by — No Comments ↓

When it comes to greedy algorithms, LeetCode 135 – Candy is a textbook problem. It asks us to distribute candies to children standing in a line, such that two simple yet strict rules are followed. While the problem may sound innocent, the trick lies in optimizing both time and space.

In this guide, we’ll walk through:

  • 🔍 Understanding the problem
  • 🧠 A clean greedy strategy
  • 🚀 An optimized solution
  • 💻 Implementations in C++, JavaScript, and Python

🧩 Problem Statement

You are given an array ratings where ratings[i] represents the rating of the i-th child. You must distribute candies according to the following rules:

  1. Each child must get at least one candy.
  2. A child with a higher rating than an adjacent child must get more candies.

📥 Example 1

Input:  [1, 0, 2]
Output: 5
Explanation: Give 2, 1, and 2 candies => Total = 5

📥 Example 2

Input:  [1, 2, 2]
Output: 4
Explanation: Give 1, 2, and 1 candies => Total = 4

🧠 Intuition and Greedy Approach

We want to minimize the number of candies while still following the two rules. Let’s start with a naive but effective strategy:

🔁 Two-Pass Greedy:

  1. Traverse left to right, and increase candy count if the current rating is higher than the previous.
  2. Traverse right to left, and do the same check from the other direction.

We’ll track the minimum required candies for each child in an array and sum them up at the end.

🧮 Time Complexity: O(n)

📦 Space Complexity: O(n)

🚀 Optimized Greedy (Space-Efficient)

To reduce space usage from O(n) to O(1), we avoid using an extra array. Instead, we keep track of:

  • inc — length of last increasing sequence
  • dec — current decreasing slope
  • prev — candies given to previous child

If a decreasing slope becomes equal to the last increasing peak, we adjust the total candies to maintain the rules.

💻 Code Implementations

📘 C++ (Optimized)

int candy(vector<int>& ratings) {
    int n = ratings.size();
    int total = 1, inc = 1, dec = 0, prev = 1;

    for (int i = 1; i < n; ++i) {
        if (ratings[i] >= ratings[i - 1]) {
            dec = 0;
            prev = (ratings[i] == ratings[i - 1]) ? 1 : prev + 1;
            total += prev;
            inc = prev;
        } else {
            dec++;
            if (dec == inc) dec++;
            total += dec;
            prev = 1;
        }
    }

    return total;
}

📙 JavaScript (Optimized)

function candy(ratings) {
    let n = ratings.length;
    let total = 1, inc = 1, dec = 0, prev = 1;

    for (let i = 1; i < n; i++) {
        if (ratings[i] >= ratings[i - 1]) {
            dec = 0;
            prev = (ratings[i] === ratings[i - 1]) ? 1 : prev + 1;
            total += prev;
            inc = prev;
        } else {
            dec++;
            if (dec === inc) dec++;
            total += dec;
            prev = 1;
        }
    }

    return total;
}

📗 Python (Optimized)

def candy(ratings):
    n = len(ratings)
    total = 1
    inc = 1
    dec = 0
    prev = 1

    for i in range(1, n):
        if ratings[i] >= ratings[i - 1]:
            dec = 0
            prev = 1 if ratings[i] == ratings[i - 1] else prev + 1
            total += prev
            inc = prev
        else:
            dec += 1
            if dec == inc:
                dec += 1
            total += dec
            prev = 1

    return total

🧪 Test Cases

assert candy([1, 0, 2]) == 5
assert candy([1, 2, 2]) == 4
assert candy([1, 3, 2, 2, 1]) == 7

assert candy([100, 80, 70, 60, 70, 80, 90, 100, 90, 80, 70, 60, 60]) == 37
# Forms a "mountain" and then descends again with a flat ending.

assert candy([6, 7, 6, 5, 4, 3, 2, 1, 0, 0, 0, 1, 0]) == 46
# Sharp drop and multiple flats with only one rise.

assert candy([
    20000, 20000, 16001, 16001, 16002, 16002, 16003, 16003, 16004, 16004,
    16005, 16005, 16006, 16006, 16007, 16007, 16008, 16008, 16009, 16009,
    16010, 16010, 16011, 16011, 16012, 16012, 16013, 16013, 16014, 16014,
    16015, 16015, 16016, 16016, 16017, 16017, 16018, 16018, 16019, 16019,
    16020, 16020, 16021, 16021, 16022, 16022, 16023, 16023, 16024, 16024
]) == 101
# Many plateau pairs; 
# Must alternate 1s and 2s to satisfy neighbors with equal ratings.

🎯 Key Takeaways

  • The naive greedy approach is intuitive and works well, but consumes O(n) space.
  • The optimized approach cleverly tracks peaks and valleys using constant space.
  • Both methods run in O(n) time, but the space-efficient version is ideal for large datasets.

📌 Final Thoughts

This problem is a great introduction to greedy algorithms and optimizing for space. It’s widely asked in interviews to test how well you can think through edge cases and reduce auxiliary storage.

Whether you’re preparing for a coding interview or polishing your DSA skills, mastering this pattern sets the stage for more advanced greedy problems.

Leave a Reply