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

def candies(n, arr):
sum = 0
i = 0
pre = 1
while i < n:
j = i+1
l = []
no = 0
if j < n:
if arr[i] >= arr[j]:
no += 1
j += 1
while j < n:
if arr[j] < arr[j-1]:
no = no+1
elif arr[j] == arr[j-1]:
l.append(no)
else:
break
j += 1
if i+1 < n and arr[i] == arr[i+1] :
fi = no
elif i+1 < n:
fi = no+1
else :
fi = 0
sum += max(pre, fi)
sum1 = int((no*(no+1))/2)
for ite in l:
sum1 += no-ite+1
sum = sum+sum1
if i == j-1:
pre = pre+1
else:
pre = 2
i = j
return int(sum)

Not sure what you are trying to do above, but here is a python version of my original solution. It passes all test cases.

def candies(n, arr):
s = [0]*n
c = [0]*n
for i in range(len(arr)):
if i == 0 or s[i-1] == 1:
s[i] = get_num_descending(arr, i)
else:
s[i] = s[i-1] - 1
c[i] = s[i] if arr[i] <= arr[i-1] else max(s[i], c[i-1]+1)
return sum(c)
def get_num_descending(arr, i):
'''
Returns the length of decreasing sequence, starting at position i.
'''
ret = 1
while i + 1 < len(arr):
if arr[i] > arr[i+1]:
ret += 1
i += 1
else:
return ret
return ret

## 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

its not working for most of the cases

Not sure what you are trying to do above, but here is a python version of my original solution. It passes all test cases.