We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

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.)

## Candies

You are viewing a single comment's thread. Return to all 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.)

Thanks. helped me a lot