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.)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
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.)