135: Candy #229
Description
Problem Number
135
Problem Title
Candy (Leetcode Hard)
LeetCode Link
https://leetcode.com/problems/candy/
Contribution Checklist
- I have written the Approach section.
- I have written the Intuition section.
- I have included a working C++ solution.
- I will raise a PR and ensure the filename follows the convention
[Number]. [Problem Title].cpp.
Approach
- Initialize a candies vector of size n with all values as 1 (each child gets at least 1 candy).
- Traverse the ratings from left to right, and if a child has a higher rating than the previous child, increment their candy count.
- Traverse from right to left, and if a child has a higher rating than the next child, update their candy count to max(current, next+1).
- Sum up all candies and return the total.
Data structures used:
vector for storing candies assigned to each child.
Time Complexity:
O(n), because we traverse the ratings array twice.
Space Complexity:
O(n), due to the candies vector.
Intuition
- Each child must get at least one candy.
- By scanning left-to-right and right-to-left, we ensure both neighbor conditions (higher rating → more candies) are satisfied.
- Using max prevents overwriting a higher candy count already assigned.
Solution in C++
class Solution {
public:
int candy(vector<int>& ratings, int cnt = 0) {
int n = ratings.size();
vector<int> candies(n, 1);
// Left to right pass
for (int i = 1; i < n; i++)
if (ratings[i] > ratings[i - 1])
candies[i] = candies[i - 1] + 1;
// Right to left pass
for (int i = n - 1; i > 0; i--) {
if (ratings[i - 1] > ratings[i])
candies[i - 1] = max(candies[i] + 1, candies[i - 1]);
cnt += candies[i - 1];
}
return cnt + candies[n - 1];
}
};