# My answer was accepted, but can it be more intuitive?

• My answer was accepted, but the code has been tweaked several times before it's accepted. I wonder is there a simple and neat way to solve this problem that is so intuitive that you don't even need to tweak so many times before it is accepted?

here is my code

``````class Solution {
public:
int candy(vector<int> &ratings) {
if (ratings.size() <= 1)
{
return ratings.size();
}
int diff = 0;
int fast = 1;
int slow = 0;
int extra = 0;
while(fast < ratings.size())
{
// go through the asccending ratings
while(fast < ratings.size() && ratings[fast-1] < ratings[fast])
{
++fast;
if (!(fast < ratings.size() && ratings[fast-1] < ratings[fast]))
{
extra += (0+fast-1-slow)*(fast-slow)/2;
diff = fast-1-slow;
slow = fast-1;
}
}
// go through the descending ratings
while(fast < ratings.size() && ratings[fast-1] > ratings[fast])
{
++fast;
if (!(fast < ratings.size() && ratings[fast-1] > ratings[fast]))
{
extra += (0+fast-1-slow-1)*(fast-slow-1)/2 + max(fast-1-slow-diff, 0);
slow = fast-1;
}
}
// go through the continuously equal ratings
while(fast < ratings.size() && ratings[fast] == ratings[fast-1])
{
++fast;
if (!(fast < ratings.size() && ratings[fast] == ratings[fast-1]))
{
slow = fast-1;
diff = 0;
}
}
}
return extra + ratings.size();
}
};``````

• I've got the solution with O(n) time complexity with O(constant) space in One pass with similar idea,

# Algorithm

Start having given one candy to each kid i.e. sum = N candies to N children, Now, adjusting the sum in single pass. Repeat until End of ratings sequence

candies
2. Check the decreasing of peak -> move to depression, add the
additional candies for only the decreasing sequence after the
peak
,
3. Then check the range of decreasing & previous increasing sequence,
only if the range of decreasing is > range of increasing and that would = (decreasing range - increasing range) [ otherwise, everything's in place, Note: you only need to adjust the peak if
depression range is greater than inclination range]
4. If it's flat [i.e adjacent ratings are same], just move on,
everything's in place. [Note: the case where adjacent rating is
same, it takes care of whether it's on top -peak or bottom, also
than initial allotted unless it's declination which is handled in
step 2] [i.e. example test case : [1, 3, 3, 2, 1] =>min no. candies
= [1, 2, 3, 2, 1] , sum = 9 ]

[PS: You need to know sum of numbers sequence 1 2, 3...n = (n * (n+1)) / 2, we need this when adjusting /adding number of candies in increasing or decreasing subsequence]

I hope my code is elegant & readable enough....

``````class Solution {
public:
int candy(vector<int> &ratings) {
int n = ratings.size();
int min_candies = n;

int range = 0;
for (size_t i = 0; i < n - 1; ) {
int start = i;
while (ratings[i] < ratings[i+1] && i < n-1) ++i;
range = i - start;
min_candies += (range * (range + 1)) / 2;
if (i == n-1) break;

start = i;
while (ratings[i] > ratings[i+1] && i < n-1) ++i;
int k = i - start - 1;
min_candies += (k * (k + 1)) / 2;
if (i - start > range) min_candies += (i - start - range);
if (ratings[i] == ratings[i+1]) ++i;
}
return min_candies;
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.