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:
- Each child must get at least one candy.
- 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:
- Traverse left to right, and increase candy count if the current rating is higher than the previous.
- 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.
Top comments (6)
nice!
Thank you 😊
Could memoization further optimize the time complexity here?
Nope, it's the best possible way
Really love how you broke down both the O(n) and O(1) space solutions - so helpful to see the thinking behind handling plateaus and slopes.
How did you first figure out the trick with adjusting the peak during long decreasing runs?
Thank you so much! Really appreciate your kind words. 😊
The peak adjustment trick actually came from visualizing the array as a series of hills and valleys, once I noticed how long decreasing runs could misplace the peak, I started experimenting with how to shift it correctly while maintaining overall correctness and optimality. It took a bit of trial and error, but breaking the pattern into parts made it click! 🧠
Always love digging into these kinds of insights, feel free to check out more breakdowns on my blog anytime! 🚀