You are viewing a single comment's thread. Return to all comments →
I did it in same way, and this is my explanation :
consider two arrays 'stairr'(for stair right) and 'stairl'(for stair left). Initialize it by 1.
stairr[i] contains number of consecutive decreasing elements(or ratings) on the right side of element 'i'(inclusive of element itself. So value will be >= 1). Similarly, we can define stairl[i].
Now, the reason I am using word stairs is because If we notice a candy value of particular element(or rating), it will depend on how many consecutive decreasing elements(or ratings) are on its left and right side. This 'consecutiveness' is like steps of stairs. More precisely, candy value will be maximum of both of these values. But why is it so?
(i) suppose an element has stairr and stairl value 1. So we can comfortably assign its candy value as 1.
(ii) Otherwise, suppose and element 'i' has stairr[i] > stairl[i]. Now, bottom elements of both right stair and left stair will have value 1, using (i) part. We can observe that to minimize the no of candies given, each 'step up' on the stair should increase the value of candy number by 1, if possible. This can be achieved it candie value of element 'i' is stairr[i] and candy value of each element in right stair of 'i' will decrease by 1 as we go down untill it reaches the bottom, which will have value 1.
Similarly, if stairl[i] > stairr[i], then candy value of element 'i' will be stairl[i].
(iii) What if two consecutive elements have equal value(or rating) ?
If 'i' and 'i + 1' have equal rating, then element 'i' enforce no constraint on element 'i + 1', so it is just like as if there is no stair step on left of 'i + 1' or stairl[i + 1] = 1(just the element itself).
Similarly, stairr[i] = 1.