Introduction
The Candy problem is a classic greedy algorithm interview question frequently asked by companies such as NPCI, Amazon, Google, and Microsoft.
The challenge is to distribute candies among children according to their ratings while minimizing the total number of candies distributed.
Although the problem appears straightforward, finding an optimal solution with O(n) time complexity and O(1) auxiliary space requires careful observation.
In this article, we'll explore the intuition, derive the optimal greedy approach, and implement it in Java.
Problem Statement
There are n children standing in a line.
Each child has a rating represented by:
arr[i]
You must distribute candies according to the following rules.
Rule 1
Every child must receive at least one candy.
Rule 2
If a child has a higher rating than an adjacent neighbor, they must receive more candies than that neighbor.
Return the minimum number of candies required.
Example 1
Input
arr = [1, 0, 2]
Distribution
Ratings : 1 0 2
Candies : 2 1 2
Total
2 + 1 + 2 = 5
Output
5
Example 2
Input
arr = [1, 2, 2]
Distribution
Ratings : 1 2 2
Candies : 1 2 1
Total
1 + 2 + 1 = 4
Output
4
Understanding the Problem
Consider:
Ratings:
1 2 3 4
Since ratings continuously increase:
Candies:
1 2 3 4
Total:
10
Now consider:
Ratings:
4 3 2 1
Candies must become:
4 3 2 1
Total:
10
The problem becomes interesting when both increasing and decreasing sequences appear together.
Brute Force Approach
One approach is repeatedly updating candy counts until all constraints are satisfied.
Example:
1 3 2 4
Keep adjusting candies until valid.
Complexity
O(n²)
This is too slow for:
n = 100000
Better Observation
Every rating pattern consists of:
Increasing slopes
Decreasing slopes
Flat regions
Example:
1 2 3 2 1
Visualization:
3
/ \
2 2
1 1
This forms a mountain.
If we can count candies contributed by increasing and decreasing slopes, we can solve the problem efficiently.
Two-Pass Solution
A common solution uses two arrays.
Left to Right
If the current rating is greater than the previous rating:
left[i] = left[i - 1] + 1;
Right to Left
If the current rating is greater than the next rating:
right[i] = right[i + 1] + 1;
Final Candy Count
max(left[i], right[i])
This works in:
Time : O(n)
Space : O(n)
But the expected solution requires:
Space : O(1)
Optimal Greedy Idea
Instead of storing arrays, we track:
up = length of increasing slope
down = length of decreasing slope
peak = longest increasing slope before descent
The idea:
Increasing ratings form an arithmetic progression.
Decreasing ratings form an arithmetic progression.
The peak should not be counted twice.
Visual Example
Ratings
1 2 3 2 1
Increasing Slope
1 2 3
Candies
1 + 2 + 3 = 6
Decreasing Slope
2 1
Candies
2 + 1 = 3
Total
9
Greedy State Variables
We maintain:
up
down
peak
candies
up
Current increasing sequence length.
down
Current decreasing sequence length.
peak
Length of the latest increasing sequence.
candies
Total candies distributed.
Algorithm
Initialize:
candies = 1;
up = 0;
down = 0;
peak = 0;
Case 1: Increasing
arr[i] > arr[i - 1]
Increase:
up++;
peak = up;
down = 0;
Add:
1 + up
candies.
Case 2: Equal Ratings
arr[i] == arr[i - 1]
Reset all slopes:
up = 0;
down = 0;
peak = 0;
Give:
1
candy.
Case 3: Decreasing
arr[i] < arr[i - 1]
Increase:
down++;
Add candies according to the decreasing slope.
If:
down > peak
we need one extra candy for the peak child.
Dry Run
Input
[1,0,2]
Start:
candies = 1
i = 1
0 < 1
Down slope:
down = 1
Add:
1
Peak correction:
down > peak
Add:
1
Total:
3
i = 2
2 > 0
Up slope:
up = 1
Add:
2
Total:
5
Answer:
5
Java Solution (O(n) Time, O(1) Space)
class Solution {
public int minCandy(int[] arr) {
int n = arr.length;
if (n == 1)
return 1;
int candies = 1;
int up = 0;
int down = 0;
int peak = 0;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
up++;
peak = up;
down = 0;
candies += 1 + up;
}
else if (arr[i] == arr[i - 1]) {
up = 0;
down = 0;
peak = 0;
candies += 1;
}
else {
up = 0;
down++;
candies += down;
if (down > peak) {
candies += 1;
}
}
}
return candies;
}
}
Alternative Two-Array Solution
This solution is easier to understand.
class Solution {
public int minCandy(int[] arr) {
int n = arr.length;
int[] candies = new int[n];
Arrays.fill(candies, 1);
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
candies[i] = candies[i - 1] + 1;
}
}
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
candies[i] =
Math.max(candies[i],
candies[i + 1] + 1);
}
}
int total = 0;
for (int c : candies) {
total += c;
}
return total;
}
}
Complexity Analysis
Optimal Greedy Solution
Time Complexity
O(n)
Single traversal.
Space Complexity
O(1)
Only a few variables are used.
Two-Array Solution
Time Complexity
O(n)
Space Complexity
O(n)
An extra array is required.
Why the Greedy Solution Works
The algorithm treats ratings as a sequence of:
Ascending slopes
Descending slopes
Flat regions
Instead of storing candy counts for every child, it directly calculates how many candies each slope contributes.
By tracking:
up
down
peak
we ensure:
Higher-rated children always receive more candies.
Peak elements are counted correctly.
Minimum candies are distributed.
Thus, the solution achieves:
Time : O(n)
Space : O(1)
which matches the expected complexity.
Conclusion
The Candy problem is an excellent greedy algorithm challenge because a simple-looking requirement hides several edge cases involving increasing and decreasing rating sequences.
The key insight is to view ratings as mountains and valleys:
Increasing slopes contribute growing candy counts.
Decreasing slopes contribute descending candy counts.
Peak elements require special handling.
Using this approach, we obtain an optimal solution with:
Time Complexity: O(n)
Space Complexity: O(1)