Click here to see the full article post
Inside of the for loop why not added by 1: candies += count(up) + count(down) + Math.max(up, down);
@ArthurTang Fixed. Thanks.
Why same rating got different candies? In Approach #2, "...34,34..." ratings got "...1,2..." candies, it's unreasonable! Hope to correct the problem.
Will an interviewer really expect someone to come up with the slope based solution during an interview?
The slope-based solution was my first idea after brute force, but implementing it correctly is a huge pain and I doubt I'd be able to do it correctly in an interview.
In the last figure, ratings at 13 and 14 are different but the candy counts are the same. So is 18 and 19. Candy at 19 and 20 should be one.
@vinod23 Should we assume that rating values are all positive?
The apparent difficulty is because of the biggish number of different cases
raised by the various interconnection of hills, valleys and plateaus.
By systematically writing out the cases upfront, one can reduce the
implementation difficulties significantly.
Make some initial observations:
Each kid can receive it's first candy initially
Create a 3 column x 9 row table:
Columns will be: currentSlope, newSlope, action
Slope can have 3 different values: decreasing, flat, increasing
Pairs of slopes (currentSlope, newSlope) can have 3*3=9 different values,
hance the 9 row.
For each slope combination write out the action that needs to be done:
currentSlope | newSlope | action
decr decr increase run length
decr flat add hill value to output, next run length is 0
decr incr add hill value to output, next run length is 1
flat decr increase run length
flat flat run length is 0
flat incr increase run length
incr decr first half of hill length computed, next run length is 1
incr incr increase run length
incr flat add run length to output, next run length is 0
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.