- Practice
- Algorithms
- Greedy
- Candies
- Discussions

# Candies

# Candies

+ 53 comments I solved it, but I have no idea how to prove my solution is correct. First I go left to right and set "next" candy value to either "previous+1" or "1". This way I get the up trends. Then I go right to left and do the same, this way getting the down trends. Very simple O(2xN) solution, but doesn't look like it's the intended one.

+ 6 comments What kind of class in the world would have 100000 kids.... LOL

+ 2 comments I don't see why this is listed under dynamic programming.

+ 3 comments Here is the way I approached this problem.

Let S[i] = The length of decreasing sequence that begins with the i-th element of the given ratings array. If there is no decreasing sequence beginning at i, S[i] = 1 by default.

Let C[i] = the minimum no. of candies given to the i-th student. The ultimate solution we want is sum(C[i]) for all i.

Key insight: C[i] = S[i] for all i, EXCEPT when ratings[i] > ratings[i-1], in which case C[i] = max(S[i], C[i-1]+1).

As an example, consider a ratings array like [4, 4, 2, 3, 4, 1]. The corresponding S array would be: S = [1, 2, 1, 1, 2, 1] The corresponding C array is: C = [1, 2, 1, 2, 3, 1] Solution: sum(C) = 10.

(Also note that it is not necessary to compute S[i] from scratch for every i. If S[i-1] > 1, then S[i] = S[i-1] - 1. This improves efficiency.)

+ 2 comments I used DP. The right to left and left to right solution works. But it is a lot fun if you use DP.

- Every student's candy value depends on their left and right student.
- So build the solution by calculating the neighbours value and then reccursing back to the top using:

func getMaxFromRight(int idx): //Handle base case and edge cases here if ranking[idx-1] < ranking[idx] > ranking[idx+1]; then candy[idx] = max(candy[idx-1], getMaxFromRight(idx+1))+1; else if (ranking[idx+1] < ranking[idx]) then candy[idx] = getMaxFromRight(idx+1)+1; else if (ranking[idx-1] < ranking[idx]) then candy[idx] = candy[idx-1]+1; getMaxFromRight(idx+1)+1; else candy[idx] = 1; getMaxFromRight(idx+1)+1; return candy[idx]

Note: You have to handle base case for return and also edge cases of idx-1 >=0 and idx+1 < candy.length

Sort 581 Discussions, By:

Please Login in order to post a comment